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 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 is therefore

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