adventofcode-2021-day-21-part-2.sage

P.<x,y> = ZZ[]
R = P.quo((x^10 - 1, y^22 - y^21))
​
die = x + x^2 + x^3
f = P.hom([x*y, y])
​
def reduce(f):
	return R.cover()(f).lift()
​
def next_move(p):
	p = p - p.coefficient(y^21) * y^21 # Remove the already-won games
	return reduce(y*f( reduce(p * die^3) ))
​
# You can’t win in fewer than 3 moves, because you
# score at most 10 points per move
#
# After 10 moves, your score will always be ≥ 21, because
# the lowest-scoring nine-move sequence is
# 3 + 2 + 1 + 4 + 2 + 1 + 4 + 2 + 1 = 20.
#
# So the winning player must play between 3 and 10 moves (inclusive).
​
from itertools import accumulate, repeat
def player(starting_position):
	polynomials = accumulate(
		repeat(x^(starting_position - 1), 11),
		lambda p, _: next_move(p)
	)
​
	# Return a list of pairs (# wins, # non-wins)
	return [
		(f.coefficient(y^21).subs(x=1), f.subs(x=1, y=1) - f.coefficient(y^21).subs(x=1))
		for f in polynomials
	]
​
player_1 = player(4)
player_2 = player(8)
​
player_1_wins = sum([ player_1[i][0] * player_2[i-1][1] for i in (3..10) ])
player_2_wins = sum([ player_1[i][1] * player_2[i][0] for i in (3..10) ])
​
print(max(player_1_wins, player_2_wins))