Project Euler #298

I’ve recently discovered Project Euler site – www.projecteuler.net and found one of its most recent puzzles quite a fun to solve 🙂 I mean project #298 – Selective Amnesia. It’s a cache hit/miss problem although formulated using different terms.

Larry and Robin play a memory game involving a sequence of random numbers between 1 and 10, inclusive, that are called out one at a time. Each player can remember up to 5 previous numbers. When the called number is in player’s memory, that player is awarded a point. If it’s not, the player adds the called number to his memory, removing another number if his memory is full.

Both players start with empty memories. Both players always add new missed numbers to their memory but use a different strategy in deciding which number to remove:
Larry’s strategy is to remove the number that hasn’t been called in the longest time.
Robin’s strategy is to remove the number that’s been in the memory the longest time.

Denoting Larry’s score by L and Robin’s score by R, what is the expected value of |L-R| after 50 turns? Give your answer rounded to eight decimal places using the format x.xxxxxxxx .

There is also an example game log for better understanding on Project Euler site – http://projecteuler.net/index.php?section=problems&id=298.

Now how do you solve a problem like this? Monte Carlo? I gave it a shot and got quite close. 1.76834950 (10M iterations) vs. 1.76855156 (100M iterations) vs. 1.76882294 (which is supposed to be the correct answer). The problem is that calculations took over 19 minutes on my Pentium M 1.7GHz CPU. Project Euler’s tasks are supposed to be solvable in less than 1 minute so I guess my approach is not optimal. I gave it a try on 3.0GHz C2Duo at the same time increasing the number of simulation steps from 100M to 1000M. I parallelized it using OpenMP. Unfortunately the second core isn’t much of a bargain when you increase the number of steps by an order of magnitude. It took over 90 minutes. 10 cores would probably do much better 😉 Not to mention that I got incorrect result once again – 1.7688070 this time which is a bit closer but still I would need a lot more iterations just to get another order of magnitude closer :(. Now where do I get a 10-core CPU huh? I obviously have a GeForce GT 220 with 48 vertex shaders, 16 geometry shaders and 8 pixel shaders which could come in handy in this case. Going CUDA? Why not 😉

The histogram received after 1000M Monte Carlo iterations looked like this:
{0: 178014772, 1: 322702294, 2: 239032256, 3: 143680703, 4: 70656447, 5: 29370263, 6: 10894577, 7: 3806843, 8: 1278188, 9: 406187, 10: 118334, 11: 30516, 12: 6923, 13: 1400, 14: 257, 15: 33, 16: 7, 17: 0, 18: 0, 19: 0, ... more zeros ...}

or if you like charts better:

I started by reading through http://www.drdobbs.com/high-performance-computing/207200659 really quickly and managed to code the problem using CUDA. Unfortunately the improvement in speed was less than spectacular. Perhaps if I could code the game rules without using conditional statements… OK – this helped a little bit. Now what is this blockSize parameter? 😀 Oh, this helped A LOT. Now I can simulate it using 10 000 000 000 iterations and it will take the same amount of time or less than simulating 1000M iterations using just CPU ;D Ten times faster that is, quite cool 🙂 It’s so brute force that I feel almost like a Neanderthal ;D Just so that you know – I _will_ approach this problem mathematically, just not today ;D

Chute, after 158 minutes (!) and 10 billion iterations all I got is Sum = 9999997952.000000 (!!!) Expected value = 1.76876247 and in this painful manner I relearned that float is not good enough for some computations 😉

The double-based version didn’t do much better Sum = 10000000000.000000 Expected value = 1.76876256 (!!!) Damn it’s still not even close! Actually if it wasn’t Monte Carlo I could say it was a regression ;]

OK, enough with this brute force horse sh*t 😉 It’s time for some maths!

1 Comment

  • Hello Stanislaw
    I’m trying to solve this problem and after some findings I’ve found your web
    this is similar to anothe Project Euler problem related to an ant and 5 seeds in a 5×5 square I mean Markov chains

    I’m not an expert in Markov chains, in fact, I have heard for fist time on Project Euler web page.

    anyway, I’m not able to model “amnesia strategy” using Markov chains and the transition matrix

    I have also tried Montecarlo aproach but I’m far for the solution
    and test all the 10^50 different configurations seems to be imposible

    I’ll keep trying let you know
    Regards !


Leave a Reply

Your email address will not be published. Required fields are marked *