Rust:

Part 1 didn't have much of an opportunity for optimization, even the naive solution is pretty fast.

The main time saver for both Part 1 and Part 2 is to identify how to process all three die rolls per turn into a single step:

• Part 1a: noticed that since the board is 10 steps in a circle, we can ignore most of the 100 sided dice as rolling a 10, 20, 30, etc will just leads you back to the same position. similarly, rolling 12, 22, 32.. has the same effect as rolling a 2. We can essentially treat that 100 side die as a 10 sided die.
• Part 1b: noticed that when adding in blocks of 3 and removing the 10's component reveal a simple pattern: 1 + 2 + 3 = 6move, 4 + 5 + 6 = 15 = 5move, 7 + 8 + 9 = 24 = 4moves, 0 + 1 + 2 = 3moves. Notice that every succession, the die effective rolled value just keeps deceasing by 1. We can use this pattern to simplified the overall turn process.
• Part 2: Since now that the dice is independent from each turn, we can now use combinatorics to figure out how a player can move. for 3 x 3 sided dice, we have a total of 27 different rolls, which there is actually only 7 different moves amount ( between 3 to 9 )

With those attempt, you can solve both part 1 and 2 in a fairly quick time.

​

For Part 2, we can do much better.

First observation is that player 1 and player 2 does not interact, as now the die is not determinate, but fully probabilistic. So, it is actually possible to calculate every turn for player 1 and 2 separately.

Second observation is that the game must end in a finite number of turns. This is due to every turn, a player is guaranteed to increase their score. We can also observe a particular case where the player traverse from 2, +9 => 1, +3 => 4, +9 => 2 ... averaging 2 points minimum per turn. Because of this, it means for a 21 point game, we can expect it to last at most 11 turns.

With that, what we can do for Part 2 is to calculate how many win/lost condition for each player separately, and then combine them for the total win/lost

What we do is that at turn N, we figure out how many path for player 1 to win on that specific turn, and how many time player 2 reached turn N - 1, but not win. We can then multiply those two number to get number of winning path for player 1 on turn N. Similarly, we do with for player 2, but use winning paths of player 2 on turn N, and player 1 not winning paths on turn N (this is due to player 2 take their turn after player 1). We then sum up all possible steps (which we know is finite) and we get the total wins for both players.

As to calculate the win/lost path count, we just recursively simulate each step for both players, just like the naive method. The reason this is faster is a lot faster that we cut the recursion steps in half, as we can now compute both player 1 + 2's turns separately. Compared with my naive solution, it is around 3000 times faster

Bench:

• Part 1: [363.98 ns 365.13 ns 366.19 ns]
• Part 2: [116.94 us 117.18 us 117.48 us]

Code for Part 1 + 2