Why is this Go faster than the equivalent Java?
The moment I saw the problem I started coding :-)<p><a href="https://gist.github.com/depp/3a6f0377284fbb9b33984063856051b1" rel="nofollow">https://gist.github.com/depp/3a6f0377284fbb9b33984063856051b...</a><p>Rather than brute forcing all possible permutations, we start from all possible final states and BFS backwards towards starting states.  There are probably tons of opportunities for further optimization, but this takes ~800 ms on my desktop, and it only uses one core.  We don't need to track the number of turns required to end each state, since the frontier will always consist of games which require the same number of turns to end.<p>Edit: Shrinking my data structures dropped runtime by 50%, and easy & cheap parallelism dropped runtime by another 75% on my four-core desktop.  New runtime: 110ms (Intel i5 6600k).  The key to the parallelism is that since the total amount of money never changes, we can assign a different total amount of money to each thread, and they'll never have to search the same states.