Project Euler/227

Problem Statement

Game with 2 dice, even number of players

Players sit around a table, game begins with 2 opposite players, 1 die each.

On each turn, the two players with the die roll it.

If the player rolls 1, they pass the die to their left neighbor

If the player rolls 6, they pass sthe die to their right neighbor

Otherwise, they keep the die for the next turn

The game ends when one player has both dice after they have been rolled and passed. That player loses.

In a game with 100 players, what is expected number of turns the game lasts?

Analysis

Since this is a large-numbered PE problem, we can start with a brute force solution and explore a small part of the problem space, and then get an estimate for whether we are even in the neighborhood of possibility to do the calculation.

The Chase Simulator

I started by writing a simple script to simulate the game. I used two pointers, and in each round of the game, incremented or decremented the pointers based on the outcome of two random integers (the dice).

Estimating Brute Force Solution Time

Based on the fact that each simulation is independent, there is a linear relationship between number of simulations and computational cost. If I want 4 decimal places of accuracy, it will cost at least 1000 simulations. To get to 10 decimal places of accuracy, we will need to run billions of simulations.

The relationship bettween number of players and computational cost is more complicated. Based on running the numbers with 5, 10, 15, 20, and 25 players, the relationship looks to be quadratic, meaning the computational cost increases with the number of players squared.

The execution time in terms of the number of players N and number of simulations S is therefore

$ T(N, S) = c \times S \times N^2 $

If I use the simple Python program to measure computational cost for smaller N and S, and extrapolate to 100 players and 9 billion simulations, I esimated a solution time of 7 x 10^6 seconds, or 80+ days.

Hmmm.

We should expect PE solutions to complete in a reasonable amount of time - say 100 seconds. That means the code needs to get 10,000x faster for a brute force solution to be feasible.

Switching to a compiled language like Java should help, as should implementing multi-threading. But because the game is so simple - just modular arithmetic with pointers - it doesn't seem like there is a whole lot of places to look for other optimizations.