import numpy as np
from collections import defaultdict

def part_2():

  #no, I don't know why I made this a numpy array
  roll_counts = np.zeros([10])
  #count how many different ways there are to roll each possible value
  for x in range(1,4):
    for y in range(1,4):
      for z in range(1,4):
        roll_counts[x+y+z] += 1


  #same as part_1
  x = 1
  y = 10

  #so the basic idea is that there's a relatively small number of states the game
  #can be in, and we just need to count how many universes are in each possible state
  #then, when we go to take a turn, we can update them in batches

  #the dict will map a state tuple (x,y,x_score,y_score) to a count, where the
  #count says how many parallel universes (thx pannen) end up in that state
  #x y x_score y_score
  states = {(x,y,0,0): 1}
  x_turn = True #whose turn it is

  #how many times each player has won
  x_wins = 0
  y_wins = 0
  while len(states)>0:

    new_states = defaultdict(int)
    for s in states.keys(): #loop over the current valid states
      for roll in range(3,10): #loop over all possible rolls
        if x_turn: #check whose turn it is
          new_x = (s[0] + roll - 1)%10 + 1 #move the piece
          new_score = s[2] + new_x #updat the score
          if new_score >= 21:
            #if we won, the number of universes that reach this conclusion is
            #the number of ways we could have ended up in the state times the number
            #of ways we could have made the current roll
            x_wins += states[s]*roll_counts[roll]
          else:
            #otherwise, we didn't win, and we just update the count for the new state
            new_states[(new_x,s[1],new_score,s[3])]+=states[s]*roll_counts[roll]

        #same plan for y
        else:
          new_y = (s[1] + roll - 1)%10 + 1
          new_score = s[3] + new_y
          if new_score >= 21:
            y_wins += states[s]*roll_counts[roll]
          else:
            new_states[(s[0],new_y,s[2],new_score)]+=states[s]*roll_counts[roll]
    x_turn = not x_turn
    states = new_states

  print(max(x_wins,y_wins))



def part_1():

  #this is extremely boring and straight-forward, we just do the thing the
  #problem says to do until someone wins.

  global roll_counter
  #x and y will track the two players' positions
  x = 1
  y = 10

  #and scores
  x_score = 0
  y_score = 0
  while x_score<1000 and y_score<1000:
    x_move = roll() + roll() + roll()
    x += x_move
    x = (x-1)%10 + 1 #what sort of stupid game is 1-indexed?
    x_score += x

    #if x wins, y doesn't get a turn
    if x_score >= 1000:
      break

    y_move = roll() + roll() + roll()
    y += y_move
    y = (y-1)%10 + 1
    y_score += y

  #if x wins, we need to print y's score, otherwise x's score
  if x_score >= 1000:
    print(roll_counter*y_score)
  else:
    print(roll_counter*x_score)

#did you know that if you try to make a variable and function with the same name,
#things might go poorly?
rollz = 1 #track the next number to be rolled
roll_counter = 0 #track how many times we've rolled
def roll():
  #global variables are gross, but fast to write!
  global rollz
  global roll_counter
  roll_counter+=1
  result = rollz
  rollz+=1
  if rollz == 101:
    rollz = 1
  return result

part_1()
part_2()