aoc2021-21.rb

def run input
  p search([input[0] - 1, 0], [input[1] - 1, 0]).max
end

$rolls = [1, 2, 3]
$rolls = $rolls.product($rolls, $rolls).map(&:sum)
$memo = {}

def search *players
  return $memo[players] if $memo[players]
  (position, score), (_, p2_score) = players
  return [0, 1] if p2_score >= 21
  
  wins = $rolls.map do |roll|
    _position = (position + roll) % 10
    search players.last, [_position, score + _position + 1]
  end
  
  $memo[players] = wins.transpose.reverse.map(&:sum)
end