4 ms·

Hey everyone! Author here, just thought I'd let you know I'm currently working on a mobile app to automate this entire process through OCR. With a little bit of

Hey everyone! Author here, just thought I'd let you know I'm currently working on a mobile app to automate this entire process through OCR. With a little bit of luck I'll have a prototype ready this week. Thank you for sharing this asicsp. I actually made a submission to HN as soon as my post went up, but I think it was pretty late at night for most readers so maybe people missed it.

asicsp 6y ago
Yeah, I saw about your plans for mobile app on reddit[0]. You could do a Show HN after the app is ready. Good luck! [0] https://www.reddit.com/r/programming/comments/khgbsc/cyberpwned_beating_cyberpunk_2077s_hacking/ https://www.reddit.com/r/programming/comments/khgbsc/cyberpw...
- geoah 6y ago
  Yap please do. I tend to go for the last option as it has the biggest payout and I’m lazy :p
  - nicolas-siplis 6y ago
    Ask and you shall receive! https://news.ycombinator.com/item?id=25535434 https://news.ycombinator.com/item?id=25535434
- nicolas-siplis 6y ago
  Just posted it! https://news.ycombinator.com/item?id=25535434 https://news.ycombinator.com/item?id=25535434
scaramanga 6y ago
Nice work! Just from a quick glance, have you thought about optimising the search algorithm by either using branch and bound, or by doing depth first search? With a little play I managed to get a 15% performance increase with a few python micro-optimisation tricks: 1. I turned generate_paths() in to agenerator and turned the paths list comprehension in to a generator comprehension so we don't have to build large data-structures containing all paths, just to find a max (since you only need to keep the current max in memory at any given time). 2. I converted PathScore to be a function to avoid a lot of redundant object creations and destructions. This was a major speedup. 3. Finally, I just added __slots__ to the remaining classes, which was a very small win.
- scaramanga 6y ago
  Yeah, I solved it in a way that's almost instantaneous (0.060s after deciding not to use numpy). First I generate the list of all possible solution sequences (82 in your example) ordering them from shortest to longest. Then I search for that shorter list in the matrix. Enjoy: https://gist.github.com/giannitedesco/cc46c347c0337b10e24d009814509438 https://gist.github.com/giannitedesco/cc46c347c0337b10e24d00...
  - scaramanga 6y ago
    This doesn't actually work if there's no immediate solution and you have to pick duds before you can make progress. But I think the way to brute force that is by breadth-first search for dud-prefixes and ending with the specific sequence searches. For now I fixed it by just assuming we can always solve the puzzle with a single "leap of faith" pick at the start (seems so from my own anecdotal experience?) :) Note that the full puzzle isn't really solvable off-line (edit: I mean in a fully general sense) because of the case where you switch from solving one sequence to another and an extra prefix gets added by the game as a punishment!

asicsp 6y ago

Yeah, I saw about your plans for mobile app on reddit[0]. You could do a Show HN after the app is ready. Good luck! [0] https://www.reddit.com/r/programming/comments/khgbsc/cyberpwned_beating_cyberpunk_2077s_hacking/ https://www.reddit.com/r/programming/comments/khgbsc/cyberpw...

geoah 6y ago
Yap please do. I tend to go for the last option as it has the biggest payout and I’m lazy :p
- nicolas-siplis 6y ago
  Ask and you shall receive! https://news.ycombinator.com/item?id=25535434 https://news.ycombinator.com/item?id=25535434
nicolas-siplis 6y ago
Just posted it! https://news.ycombinator.com/item?id=25535434 https://news.ycombinator.com/item?id=25535434

scaramanga 6y ago

Nice work! Just from a quick glance, have you thought about optimising the search algorithm by either using branch and bound, or by doing depth first search? With a little play I managed to get a 15% performance increase with a few python micro-optimisation tricks: 1. I turned generate_paths() in to agenerator and turned the paths list comprehension in to a generator comprehension so we don't have to build large data-structures containing all paths, just to find a max (since you only need to keep the current max in memory at any given time). 2. I converted PathScore to be a function to avoid a lot of redundant object creations and destructions. This was a major speedup. 3. Finally, I just added __slots__ to the remaining classes, which was a very small win.

scaramanga 6y ago
Yeah, I solved it in a way that's almost instantaneous (0.060s after deciding not to use numpy). First I generate the list of all possible solution sequences (82 in your example) ordering them from shortest to longest. Then I search for that shorter list in the matrix. Enjoy: https://gist.github.com/giannitedesco/cc46c347c0337b10e24d009814509438 https://gist.github.com/giannitedesco/cc46c347c0337b10e24d00...
- scaramanga 6y ago
  This doesn't actually work if there's no immediate solution and you have to pick duds before you can make progress. But I think the way to brute force that is by breadth-first search for dud-prefixes and ending with the specific sequence searches. For now I fixed it by just assuming we can always solve the puzzle with a single "leap of faith" pick at the start (seems so from my own anecdotal experience?) :) Note that the full puzzle isn't really solvable off-line (edit: I mean in a fully general sense) because of the case where you switch from solving one sequence to another and an extra prefix gets added by the game as a punishment!