Problem #84 concerns simulations of the game Monopoly. The question reads:
I apologize for not embedding this problem in WordPress. I felt it would be much simpler if I just added a screenshot due to the long list of instructions. Regardless, this is one of the more intimidating early questions of Project Euler. My solution still has some bugs, and I had to guess and check my way to the answer for this problem. Here’s my solution:
Solution #1: Experimental Approach
We simply simulate a large number of moves around the Monopoly board and record the number of times each square is landed on. Then we sort the squares based on their frequency and list the most frequent squares. The annoying part is simulating the game. Here is an implementation of this solution in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Simulation Approach to Project Euler Problem #84
'''
import time
import random
def randomRoll():
a = random.randint(1,5)
b = random.randint(1,5)
if(a==b):
return [a+b,True]
else:
return [a+b,False]
def chance(p):
n = random.randint(0,10)
if(n==0):
return 0
if(n==1):
return 10
if(n==2):
return 11
if(n==3):
return 24
if(n==4):
return 39
if(n==5):
return 5
if(n==6 or n==7):
return ((p-1)-(p-1)%10 + 15)%40
if(n==8):
if(12<=p<28):
return 28
return 12
return (p-3)%40
def uniqueString(n):
if(n<10):
return "0"+str(n)
return str(n)
def projectEulerProblemEightyFour(n):
communityCards = 1
board = ["G","G","CC","G","G","G","G","CH","G","G","J","G","G","G","G","G","G","CC","G","G","G","G","CH","G","G","G","G","G","G","G","G2J","G","G","CC","G","G","CH","G","G","G"]
position = 0
first = False
second = False
third = False
totals = [0]*40
for c in range(n):
move = randomRoll()
position = (position+move[0])%40
third = second
second = first
first = move[1]
if first and second and third:
position = 10
else:
v = board[position]
if v=="CC":
a = random.randint(1,5)
if(a==1):
while(v=="CC"):
position = chance(position)
v = board[position]
if(v=="CC"):
a = random.randint(1,5)
if(a!=1):
break
elif v == "CH":
a = random.randint(1,9)
if(a==1):
if communityCards == 0:
position = 0
else:
position = 10
communityCards = (communityCards+1)%2
elif v == "G2J":
position = 10
totals[position]+=1
indexList = []
for x in range(40):
indexList.append(x)
final = sorted(indexList, key = lambda x: totals[x])[::-1]
return uniqueString(final[0])+uniqueString(final[1])+uniqueString(final[2])
start = time.time()
print projectEulerProblemEightyFour(10**6)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
101615
--- 2.08807682991 seconds ---
for input of n = 10**6. (It prints this ~80% of the time)
Actual answer is 101524.
There must be some small error in my simulation that caused this result to
be so consistent. The way I solved this was by listing the 10 most frequent
squares from my simulation and then guessing and checking until I got it.
'''
As noted in the comments in my code, this program does not give the correct answer. While it is impossible to get a consistent experimental answer due to the random nature of Monopoly games, the most common answer should still coincide with the expected answer for a correct simulation. Thus, there is some unknown error in my simulation that I am too lazy to find at this point. To get the answer, I listed the 10 most common squares with my program and guess and checked until I found the right triple. I definitely want to come back to this problem to find an actual solution at some point.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 