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.

Advertisements

3 Responses to “Project Euler Problem #84”

  1. M. Says:

    go read
    https://projecteuler.net/about

    “I learned so much solving problem XXX so is it okay to publish my solution elsewhere?
    It appears that you have answered your own question. There is nothing quite like that “Aha!” moment when you finally beat a problem which you have been working on for some time. It is often through the best of intentions in wishing to share our insights so that others can enjoy that moment too. Sadly, however, that will not be the case for your readers. Real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery. Please do not deny others what you have so richly valued yourself.”


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: