Project Euler Solution 84: Monopoly Odds

Code & Zahlen

In Problem 84: Monopoly Odds we are asked to compute the odds for the fields of a Monopoly board.

In the problem statement the rules for Monopoly are given. We are asked to find the three most likely fields to end a move on. For two six-sided dice these are given as the fields Jail, E3 and Go. We need to compute the same thing with two four-sided dice.

At the university I did a bunch of Monte Carlo simulation stuff. We could of course try to compute the probabilities by observing the rules carefully and creating a transition graph. Then we could try to diagonalize it to find the liklihoods of the states.

Or we just simulate it. That's what I have chosen to do. First we implement the board, that's rather boring, though.

board = [
    "GO",
    "A1",
    "CC1",
    "A2",
    "T1",
    "R1",
    "B1",
    "CH1",
    "B2",
    "B3",
    "JAIL",
    "C1",
    "U1",
    "C2",
    "C3",
    "R2",
    "D1",
    "CC2",
    "D2",
    "D3",
    "FP",
    "E1",
    "CH2",
    "E2",
    "E3",
    "R3",
    "F1",
    "F2",
    "U2",
    "F3",
    "G2J",
    "G1",
    "G2",
    "CC3",
    "G3",
    "R4",
    "CH3",
    "H1",
    "T2",
    "H2",
]

Then we need special movements for the community and chance cards. They either seek up to the next instance of some field, don't move you, or move you three steps backward. We implement these as classes and use the null pattern to simulate the cards which don't move the player.

class Movement:
    def seek(self, position: int) -> int:
        raise NotImplementedError()


class ForwardMovement(Movement):
    def __init__(self, prefix: str) -> None:
        self._prefix = prefix

    def seek(self, position: int) -> int:
        while not board[position].startswith(self._prefix):
            position += 1
            position %= len(board)
        return position


class BackwardMovement(Movement):
    def seek(self, position: int) -> int:
        return (position - 3 + len(board)) % len(board)


class NullMovement(Movement):
    def seek(self, position: int) -> int:
        return position

Then we can implement the two stacks of cards that hand out movements:

def card_stack(cards: list[Movement]) -> Iterator[Movement]:
    random.shuffle(cards)
    for card in itertools.cycle(cards):
        yield card


def chance_cards() -> Iterator[Movement]:
    cards = [
        ForwardMovement("GO"),
        ForwardMovement("JAIL"),
        ForwardMovement("C1"),
        ForwardMovement("E3"),
        ForwardMovement("H2"),
        ForwardMovement("R1"),
        ForwardMovement("R"),
        ForwardMovement("R"),
        ForwardMovement("U"),
        BackwardMovement(),
    ] + [NullMovement()] * 6
    yield from card_stack(cards)


def community_chest_cards() -> Iterator[Movement]:
    cards = [ForwardMovement("GO"), ForwardMovement("JAIL")] + [NullMovement()] * 14
    yield from card_stack(cards)

We need something for the dice rolls:

def dice_pair(eyes: int) -> Iterator[tuple[int, bool]]:
    first = random.randint(1, eyes)
    second = random.randint(1, eyes)
    return first + second, first == second

Finally we can assemble this into the solution. We create iterators for the two cards, and then just simulate 4,000,000 runs.

def solution() -> int:
    position = 0
    visited_fields = collections.defaultdict(lambda: 0)
    chance_cards_iter = chance_cards()
    community_chest_cards_iter = community_chest_cards()
    steps = 4000000
    for i in range(steps):
        eyes, is_double = dice_pair(4)
        position += eyes
        position %= len(board)

        if board[position].startswith("CC"):
            movement = next(community_chest_cards_iter)
            position = movement.seek(position)
        elif board[position].startswith("CH"):
            movement = next(chance_cards_iter)
            position = movement.seek(position)
        elif board[position] == "G2J":
            position = board.index("JAIL")

        visited_fields[board[position]] += 1

    results = sorted(
        [
            (100 * count / steps, field, board.index(field))
            for field, count in visited_fields.items()
        ],
        reverse=True,
    )
    return "".join(f"{index:02d}" for percentage, field, index in results[:3])

This gives the correct solution in 5.5 s, so that's fine.

There are a couple of things which are not implemented:

  • If one has three doubles in a row, one goes to jail directly.
  • If one moves backwards and then hits the community chest or the chance field, one has to draw another card.

It turns out that these edge cases are not needed to get the three most likely fields out of there. So this solution is not perfect, but it is sufficient for the task at hand.