4 ms·
The moment I saw the problem I started coding :-) https://gist.github.com/depp/3a6f0377284fbb9b33984063856051b1 https://gist.github.com/depp/3a6f0377284fbb9b33
by dietrichepp 10y ago
The moment I saw the problem I started coding :-)
https://gist.github.com/depp/3a6f0377284fbb9b33984063856051b1 https://gist.github.com/depp/3a6f0377284fbb9b33984063856051b...
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.
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.
- deleted 10y ago[deleted]
- boyter 10y agoHah I knew there was a better way to solve it! I was sort of sick of the problem by this point and didn't feel like picking it up again :) Glad to see someone else found it and implemented as well and proved that it produces a much faster calculation. I added this at the end with a link to your solution and your post. Honestly I never expected this post to make it to the front page so thank you so much for taking some time out to do so.
- dietrichepp 10y agoTrouble sleeping, so... rev #3: tighter packing of states -> ~25% run time reduction.
- tboerstad 10y agoWow, this is beautiful C++ code! High level abstractions, not hiding any of the nitty gritty details, parallelism and all, yet very readable. Well done!
- swah 10y agoI felt the same - not that worse than in a modern language (of course someone should rewrite in Go with the new algorithm so we can decide if it would be good enough :)
- Exuma 10y agoI feel retarded now. So if the players are randomly chosen according to the rules, doesn't that change the possible solutions? Edit: Is it because each solution must take into account every possible permutation of gameplay?
- dietrichepp 10y agoA solution is "no matter what randomly happens, the game will last at least 12 turns".
- ggggtez 10y agoBefore I read the post I thought how I would solve it. Dynamic programming starting from end states should avoid lots of redundant work. Also making sure to sort the players by money, to reuse symmetries.