Ok, I've skipped straight from Day 17 to Day 21, because both 18 and 19 looks horrid and 20 looks like a fair amount of work (but I have good ideas for that one).
Day 21 requires us to track a pawns progress on a circular board (which means modular arithmatic) rolling a deterministic die.
So each roll of hte die will be a 1 then a 2 then a 3 and so on.
Each player gets 3 rolls, and then applies the rolls to their piece, and then adds the place they land on their score.
I'm going to use a combination of functional and pythonic programming here, using a generator for the die, and feeding that into an advance state function. The current game is going to be a deterministic state machine that keeps track of the scores, the current positions and gets fed with a die generator. It will end when the first player gets to 1000 and return the losing player and the current die roll.
Note that I suspect that part two will require implementing a new die that generates seemingly random numbers, so I want to push the die out to an externalised generator so that it's separate to the board
## Import ipytest and get it setup for use in Python Notebook
import pytest
import ipytest
ipytest.autoconfig()
import itertools
import more_itertools
from enum import Enum
from itertools import cycle
from more_itertools import always_iterable, take
def deterministic_die(rolls=100):
return cycle(always_iterable(range(1,rolls+1)))
def playgame(die, p1start, p2start, debug=False):
currentplayer = 0
currentroll = 0
totalrolls = 0
scores = [0,0]
location =[p1start, p2start]
for roll in die:
location[currentplayer] += roll
while location[currentplayer] > 10: location[currentplayer] -= 10
totalrolls += 1
currentroll += 1
if currentroll == 3:
scores[currentplayer] += location[currentplayer]
if debug: print(f"Roll {roll} - Player1@{location[0]}={scores[0]}, Player2@{location[1]}={scores[1]}")
if scores[currentplayer] >= 1000:
return scores,totalrolls
currentplayer = (currentplayer+1) % 2
currentroll = 0
return scores,totalrolls
assert ([10,0],3) == playgame(take(3,deterministic_die()), 4, 8)
assert ([10,3],6) == playgame(take(6,deterministic_die()), 4, 8)
assert ([14,3],9) == playgame(take(9,deterministic_die()), 4, 8)
assert ([14,9],12) == playgame(take(12,deterministic_die()), 4, 8)
assert ([20,9],15) == playgame(take(15,deterministic_die()), 4, 8)
assert ([26,22],24) == playgame(take(24,deterministic_die()), 4, 8)
assert ([1000,745],993) == playgame(deterministic_die(), 4, 8)
Ok, that was slightly more complex than I thought, but mostly because I had an off-by-one error.
Annoyingly, the test data covers the first 24 rolls, but doesn't make clear or give good tests for what happens at roll 100. By the time we get to roll 993, my off by one error was repeated 9 times, which is enough to completely throw everything out.
What was the off by one? cycle(always_iterable(range(1,100))) handles a range from 1 to 99, not 1 to 100!
Anyway, that done, lets see what the production data says
results = playgame(deterministic_die(), 7, 4)
print(results)
print(min(results[0])*results[1])
([1008, 784], 861) 675024
OMG, I was not expecting that! The first clue here is that we're talking thousands of trillions of answers, 10^15 or so more or less, which is a big enough number that brute force isn't going to help us.
We could create a generator and return multiple generators for each roll, and then advance them all, creating endless new generators and running them until we get to 21.
A better option might be to start thinking of the rolls as a tree structure. From the first node, at the starting positions, there's 3 onward nodes, one where p1 roles a 1, 2, or 3. Each tree node represents a game move. We can build this tree, and then traverse it. The problem is that if our order of magnitude calculations are right, it would be about a petabyte in size.
I suspect the answer is related to the fact that although there are thousand of billions of combiations, many of them are the same. After all, rolling a 1 and then a 2 is the same as rolling a 2 and then a 1. Caching is probably the solution, but I'd need to rewrite the first half significantly.
Might come back to this later