Omg, I finally solved this problem and gained access to Project Euler’s thread dedicated to its solutions. Apparently everybody came up with basically the same idea. The number of game states can be reduced to 438 (439 including the empty state). This way all 50 rounds can be simulated using dynamic programming. I’m not sure if I’m allowed to discuss the details here (also I don’t want to spoil it for those who are willing to take the challenge). Until I figure out the former I will just quote some numbers. During all the experiments I produced a file containing 574 lines of code in C. Among other cool stuff I implemented queues running on a single integer number. It seemed handy at the time when I thought I’d have to simulate over a billion states 😉 You’d just have to define some constants (masks, etc.) and it could provide you for example with a neat 8-slot queue that could handle numbers from 1 to 15 in each slot. Anyway, C code managed to produce the mentioned 438 states but there was something wrong with it. It had either to do with the expected value computation part or with floating-point precision (although very unlikely, because I had even resorted to libgmp at one moment). Anyway I kept getting 1.77038076 instead of the correct answer. The thing was always getting screwed up after 9th round or so when compared to the final, working version of my solution. The software was blazingly fast though, outputting an incorrect value almost instantaneously 😉 It took 65 lines of Python code, that runs in ~10 seconds on a Pentium M 1.7GHz CPU to produce the correct result. I’ve reimplemented states logic in a much cleaner and obviously more error-proof (and slower 😉 ) way, although it turned out that it was absolutely correct in the first place in C (up to every single state at every round). At the same time I figured out another way of computing the expected value without using floating-point numbers at all. I was really happy to finally see not only the correct result but also it’s über-precise version which looks like this: 1.768822942380110058425447937597155992859448857328000 😀 10 seconds on a 1.7GHz PentiumM giving 48 decimal places of precision vs. 3 hours on a 3.0GHz Core 2 Duo giving just three 😉 This is the power of intelligence ;D Phew…. Project Euler is a really nice page. I’m definitely having more of it and I recommend it to You as well 😀
