Project Euler Problem 84 Solution

Project Euler Problem 84 Solution

Monopoly Odds

by {BetaProjects} | Project Euler & HackerRank
Difficulty: Hard

Project Euler Problem 84 Statement

In the game, Monopoly, the standard board is set up in the following way:

Project Euler 84

A player starts on the GO square and adds the scores on two 6-sided dice to determine the number of squares they advance in a clockwise direction. Without any further rules we would expect to visit each square with equal probability: 2.5%. However, landing on G2J (Go To Jail), CC (community chest), and CH (chance) changes this distribution.

In addition to G2J, and one card from each of CC and CH, that orders the player to go directly to jail, if a player rolls three consecutive doubles, they do not advance the result of their 3rd roll. Instead they proceed directly to jail.

At the beginning of the game, the CC and CH cards are shuffled. When a player lands on CC or CH they take a card from the top of the respective pile and, after following the instructions, it is returned to the bottom of the pile. There are sixteen cards in each pile, but for the purpose of this problem we are only concerned with cards that order a movement; any instruction not concerned with movement will be ignored and the player will remain on the CC/CH square.

The heart of this problem concerns the likelihood of visiting a particular square. That is, the probability of finishing at that square after a roll. For this reason it should be clear that, with the exception of G2J for which the probability of finishing on it is zero, the CH squares will have the lowest probabilities, as 5/8 request a movement to another square, and it is the final square that the player finishes at on each roll that we are interested in. We shall make no distinction between "Just Visiting" and being sent to JAIL, and we shall also ignore the rule about requiring a double to "get out of jail", assuming that they pay to get out on their next turn.

By starting at GO and numbering the squares sequentially from 00 to 39 we can concatenate these two-digit numbers to produce strings that correspond with sets of squares.

Statistically it can be shown that the three most popular squares, in order, are JAIL (6.24%) = Square 10, E3 (3.18%) = Square 24, and GO (3.09%) = Square 00. So these three most popular squares can be listed with the six-digit modal string: 102400.

If, instead of using two 6-sided dice, two 4-sided dice are used, find the six-digit modal string.

Solution

Project Euler Problem 84 overview:

The objective of the problem is to identify the top k most likely squares a player can land on in a game of Monopoly, given a specific number of dice sides (n). The solution employs Markov chain analysis to model the transitions between different squares on the Monopoly board, taking into account the probabilistic nature of dice rolls and the special rules associated with certain squares like "Go To Jail" (G2J), "Community Chest" (CC), and "Chance" (CH).

Core Components of the Solution
  1. State Representation

    The Monopoly board is represented as a list of square names in the names list. Each square corresponds to a unique state in the Markov chain. A dictionary squares maps each square name to its corresponding index, facilitating easy reference during transitions.

  2. Handling Special Squares
    • Go To Jail (G2J): Landing on G2J directs the player to the "JAIL" square with a probability of 1.
    • Community Chest (CC): Landing on a CC square involves drawing a Community Chest card, which has a \(\frac{1}{16}\) chance each to send the player to "GO" or "JAIL", and a \(\frac{14}{16}\) chance to remain on the current CC square.
    • Chance (CH): Landing on a CH square involves drawing a Chance card, which can direct the player to various squares such as "GO", "JAIL", "C1", "E3", "H2", "R1", the next "R" (Railroad) or "U" (Utility) square, or move the player back three squares. There are also probabilities associated with these transitions.
  3. Precomputing Next "R" and "U" Squares

    The find_next function determines the next square starting with a specified prefix ("R" for Railroads and "U" for Utilities) from any given square. This ensures accurate transitions when Chance cards direct players to the next "R" or "U" square. Lists next_r and next_u store the indices of the next "R" and "U" squares for each square on the board.

  4. Transition Probability Calculation

    The get_transitions function calculates the probability distribution of landing on each square after a specific dice roll. It accounts for the special behaviors of G2J, CC, and CH squares by updating the probabilities accordingly. The resolve function is a helper that recursively handles the distribution of probabilities when landing on special squares that may trigger further transitions.

  5. Building the Transition Matrix

    The solution constructs a transition matrix (p_matrix) where each entry p_matrix[i][j] represents the probability of moving from square i to square j based on all possible dice rolls. All possible dice rolls are generated using two nested loops, considering the number of sides on each die (n). The sum of the two dice (roll) determines the movement from the current square.

  6. Matrix Multiplication for Markov Chain Progression

    The mat_mult function performs matrix multiplication to simulate the progression of the Markov chain over multiple iterations. By repeatedly multiplying the transition matrix, the solution approximates the stationary distribution, which represents the long-term probabilities of being on each square. The number of iterations (iterations=150) is chosen to ensure convergence towards the stationary distribution, though this value can be adjusted based on desired precision.

  7. Extracting and Sorting Probabilities

    After matrix exponentiation, the first row of the resulting matrix (current[0]) approximates the stationary distribution starting from the "GO" square. The squares are then sorted in descending order based on their stationary probabilities, and the top k squares are selected as the most likely landing spots.

  8. Input and Output Handling

    The main function reads input values for the number of dice sides (n) and the number of top squares to output (k). It invokes the markov_chain_solver function with these parameters and prints the resulting top k square names.

HackerRank version

HackerRank logo

Solves all test cases for Hackerrank Project Euler Problem 84

HackerRank Project Euler 84: If, instead of using two 6-sided dice, two N-sided dice are used, find the $K$ most popular squares in order.

Python Source Code

def markov_chain_solver(dice, k, iterations=150):
    names = ["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"]
    squares = {name: i for i, name in enumerate(names)}
    
    def find_next(current, prefix):
        for step in range(1, len(names) + 1):
            nxt = (current + step) % len(names)
            if names[nxt].startswith(prefix):
                return nxt
        return current
    
    next_r = [find_next(i, 'R') for i in range(len(names))]
    next_u = [find_next(i, 'U') for i in range(len(names))]
    
    def resolve(square, prob, probs):
        s = names[square]
        if s == "G2J":
            probs[squares["JAIL"]] += prob
        elif s.startswith("CC"):
            probs[squares["GO"]] += prob / 16
            probs[squares["JAIL"]] += prob / 16
            probs[square] += 14 * prob / 16
        elif s.startswith("CH"):
            moves = [
                squares["GO"], squares["JAIL"], squares["C1"], squares["E3"],
                squares["H2"], squares["R1"], next_r[square], next_r[square],
                next_u[square], (square - 3) % len(names)
            ]
            for move in moves:
                if names[move].startswith("CC") or names[move].startswith("CH"):
                    resolve(move, prob / 16, probs)
                else:
                    probs[move] += prob / 16
            probs[square] += 6 * prob / 16
        else:
            probs[square] += prob
    
    def get_transitions(square, roll):
        new = (square + roll) % len(names)
        probs = [0] * len(names)
        resolve(new, 1, probs)
        return [p / (dice ** 2) for p in probs]
    
    rolls = [d1 + d2 for d1 in range(1, dice +1) for d2 in range(1, dice +1)]
    size = len(names)
    p_matrix = [[0]*size for _ in range(size)]
    for i in range(size):
        for roll in rolls:
            transitions = get_transitions(i, roll)
            for j in range(size):
                p_matrix[i][j] += transitions[j]
    
    def mat_mult(m1, m2):
        return [[sum(m1[i][k] * m2[k][j] for k in range(size)) for j in range(size)] for i in range(size)]
    
    current = p_matrix
    for _ in range(iterations):
        current = mat_mult(current, p_matrix)
    
    stationary = current[0]
    sorted_squares = sorted([(prob, i) for i, prob in enumerate(stationary)], reverse=True)
    return [names[i] for _, i in sorted_squares[:k]]

n, k = map(int, input().split())
print(" ".join(markov_chain_solver(n, k)))