## Project Euler Problem #84

### April 9, 2010

Read the details of the problem here

Summary

In the game, Monopoly, find the three most popular squares when using two 4-sided dice.

Solution

When I first read this problem, I thought it was quite straightforward and just relied on the initial roll of the dice, starting from GO. However, assuming this approach for six-sided dice gave me completely different percentages to what were cited in the question. It became apparent to me that what was required was the long-term probabilities of landing on a specific square.

I considered extending my original approach using chains of probabilities but it quickly got out of hand once I considered how to incorporate the rolling of 3-doubles and the random events from the Community Chest and Chance cards. The search space that was required was becoming very large indeed. I had wondered why only some 1,960 or so people had solved this since it was posted on 3-Dec-2004 (it being 8-Apr-2010)and now it became apparent!

Not wanting to be beaten on this I decided to go for a simulation approach and hoped that the probabilities didn’t require too much accuracy. The question was just looking for an ordering rather than the probabilities themselves so a Monte Carlo technique might pay off.

Having decided this it was more straightforward to write than I thought it might be, although it did raise a few implementation questions that weren’t addressed in the problem statement. Specifically, when sent to Jail due to a random card event, or landing on the Go To Jail square, are your double counts reset? I always played that way so that’s how I coded it. Also, I assumed that the card packs remained in order and all the jump cards were essentially at the front of the pack. I didn’t shuffle them or pick cards at random which would have been alternative approaches. I also noted that it was possible, given a Go Back 3 Squares from Chance 3 (Square:CH3) that you’d land back on CC3 and have to also take a CC card – this therefore dictated the ordering of the card pack selections in the simulation.

```def ( GO, G2J, JAIL ) = [  0, 30, 10 ]
def ( R1, R2, R3 )    = [  5, 15, 25 ]
def ( U1, U2 )        = [ 12, 28 ]
def ( CC1, CC2, CC3 ) = [  2, 17, 33 ]
def ( CH1, CH2, CH3 ) = [  7, 22, 36 ]
def ( C1, E3, H2 )    = [ 11, 24, 39 ]

def counts = new int[40]
def ( location, cci, chi, dbls ) = [ GO, 0, 0, 0 ]

for (i in 1..1000000) {

def r1 = (int)(Math.random() * 4) + 1
def r2 = (int)(Math.random() * 4) + 1

dbls = (r1 == r2) ? dbls+1 : 0
location = (location + r1 + r2) % 40

if ((dbls == 3) || (location == G2J)) {
location = JAIL
dbls = 0
}

if (location in [ CH1, CH2, CH3 ]) {
switch (chi) {
case 0: location = GO; break
case 1:
location = JAIL
dbls = 0
break
case 2: location = C1; break
case 3: location = E3; break
case 4: location = H2; break
case 5: location = R1; break
case 6..7:
location = [(CH1):R2,(CH2):R3,(CH3):R1][location]
break
case 8:
location = [(CH1):U1,(CH2):U2,(CH3):U1][location]
break
case 9: location -= 3; break
}
chi = ++chi % 16
}

if (location in [ CC1, CC2, CC3 ]) {
switch (cci) {
case 0: location = GO; break
case 1:
location = JAIL
dbls = 0
break
}
cci = ++cci % 16
}

counts[location]++
}

def odds = []
counts.eachWithIndex { v, i -> odds << [ i, v/10000 ] }

def answer = odds.sort { -it[1] }[0..2].collect {
sprintf("%02d",it[0])
}.join()
```

I could have taken a much more OO approach to this simulation, modelling the dice, board, card packs (maybe with each card holding a Closure that transformed the position in a Command pattern approach), etc. but it would have been complete overkill for this solution.

As it is, this ran in 4.19 seconds, with simulation itself taking 4.16 seconds. Post-processing the results was quick to write and obviously ran sufficiently fast enough for the scale of this problem.

Note: The separation of 3rd and 4th rank elements is only something in the order of 0.06% – through numerous runs of the simulation I have found that one million iterations reliably makes this distinction but does, very rarely, transpose them. For reference, I make the first five probabilities as follows: 6.96%, 3.59%, 3.29%, 3.23%, 3.12%, but results can obviously differ slightly from run-to-run.

Having got the correct answer using this approach and so gained access to the Project Euler forum for the problem, I was interested to see most people had taken the simulation approach. A few brave souls had used Markov Chains and similar statistical approaches (sometimes just ignoring the inconvenient doubles and CH3->CC3 rules as these didn’t have any material effect on the ranking it seemed, though they would on the absolute probabilities). This sort of problem seems to come up in later Project Euler questions so I should spend some time in understanding this technique more.

Conclusion

I didn’t actually use too many Groovy specific features in this, apart from variable declarations, multiple assignment, the easy map lookups for the rail and utility jumps, and the listops to process the results array at the end of the simulation. So…maybe I did use quite a few features after all but it’s still very much like a standard Java program though somewhat too procedural perhaps!

Note: I’ve now completed 89/286 problems ranking me at 140/2245 members in England though I am still a n00b on the site! Only 11 more to solve before I get be included in the Novice category.