1  from lib import *
 2  
 3  input = read_input(2021, 21)
 4  
 5  lines = input.splitlines()
 6  
 7  
 8  players = [int(line.split()[-1]) for line in lines]
 9  scores = [0, 0]
10  die = 0
11  k = 0
12  while max(scores) < 1000:
13      x = sum((die + i) % 100 + 1 for i in range(3))
14      die += 3
15      players[k] = (players[k] - 1 + x) % 10 + 1
16      scores[k] += players[k]
17      k = (k + 1) % 2
18  
19  print(scores[k] * die)
20  
21  
22  @functools.cache
23  def dirac(p1, p2, s1, s2, k):
24      if s1 >= 21:
25          return 1, 0
26  
27      if s2 >= 21:
28          return 0, 1
29  
30      p = [p1, p2][k]
31      s = [s1, s2][k]
32      out = [0, 0]
33      for x in map(sum, itertools.product([1, 2, 3], repeat=3)):
34          q = (p - 1 + x) % 10 + 1
35          if k == 0:
36              res = dirac(q, p2, s + q, s2, 1)
37          else:
38              res = dirac(p1, q, s1, s + q, 0)
39          for i in range(2):
40              out[i] += res[i]
41  
42      return tuple(out)
43  
44  
45  dirac.cache_clear()
46  players = [int(line.split()[-1]) for line in lines]
47  print(max(dirac(*players, 0, 0, 0)))