day21_part2.py (8992B)
1 #!/usr/bin/env python 2 """Advent of Code 2021, day 21 (part 2): Dirac Dice 3 Simulating an Advent of Code board game (with a multiverse die!)""" 4 5 # Well I'm glad I didn't overengineer part 1 because I didn't expect this. 6 # 7 # It's infeasible to enumerate all of the possible outcomes. I think the 8 # "trick" is to recognize that on each turn, a player can only advance 3, 4, 9 # ..., 9 spaces, but each of these outcomes is associated with a different 10 # number of "universes" (e.g., only one universe results in a move of 3 spaces, 11 # but 3 different universes are associated with a 4-space move). 12 # 13 # The state space is strictly less than 2 x 10 x 10 x 30 x 30 possible player 14 # turn / player 1 position / player 2 position / player 1 score / player 2 15 # score combinations, as many of these are impossible (no score above 30 needs 16 # to be considered, because a winning score above 30 isn't possible). So we can 17 # recursively explore the number of universes that wind up at each possible 18 # winning condition. The number of universes at state n = the sum of the 19 # product of the number of universes from each previous state by the number of 20 # universes that arrive at _that_ state. The base condition is the starting 21 # state of the game: both players have a score of 0 and their pawn at their 22 # respective starting position, this state has exactly 1 universe (and 23 # "impossible" states have 0 universes). So this is a perfect application for 24 # memoization, which is fairly easy with functools.lru_cache. 25 26 from typing import Tuple, Dict, cast 27 from functools import lru_cache 28 from itertools import product 29 30 from day21_part1 import EXAMPLE_INPUT, parse_input 31 from utils import get_puzzle_input 32 33 # I know globals are ugly but whatcha gonna do? 34 UNIVERSES_PER_MOVE = tuple((k + 3, v) for k, v in \ 35 enumerate([1, 3, 6, 7, 6, 3, 1])) 36 37 @lru_cache(maxsize=None) 38 def count_universes_at(player_turn: int, 39 winning_score: int, 40 start_positions: Tuple[int, int], 41 positions: Tuple[int, int], 42 scores: Tuple[int, int]) -> int: 43 """Find the number of universes that lead to the current state recursively. 44 `player_turn` indicates which player just _finished_ their turn, and we're 45 treating the starting state of the game as a though player 2 just finished 46 (since player 1 goes first)""" 47 player_idx = player_turn - 1 48 49 # First, check if it's an "impossible" state 50 impossible_state = min(scores) > winning_score \ 51 or max(scores) > winning_score + 9 52 for player in range(2): 53 # No player can have a score less than zero, and if the score _is_ 54 # zero, their position must be their starting position 55 impossible_state |= scores[player] < 0 56 if scores[player] == 0: 57 impossible_state |= positions[player] != start_positions[player] 58 # Player 2 can't have points before player 1 59 impossible_state |= scores[0] == 0 and scores[1] > 0 60 # If both players have 0 points, then player 2 just "finished" 61 if scores == (0, 0): 62 impossible_state |= player_turn != 2 63 64 # The player's previous score was their current score minus their 65 # current position (e.g., if they're on space 4 with a score of 12, 66 # then their last score had to be 8) 67 scores_prev = list(scores) 68 scores_prev[player_idx] = scores[player_idx] - positions[player_idx] 69 70 # If this is a winning score, the previous score could not also have been a 71 # winning score, which means that the previous score could never have been 72 # a winning score. 73 impossible_state |= scores_prev[player_idx] >= winning_score 74 75 universes_at_this_state = 0 76 if not impossible_state: 77 if scores == (0, 0): 78 # Base case 79 universes_at_this_state = 1 80 else: 81 # We entered the current state following a move from the current 82 # player. 83 for die_roll, num_universes in UNIVERSES_PER_MOVE: 84 positions_prev = list(positions) 85 positions_prev[player_idx] = (positions[player_idx] - 1 86 - die_roll) % 10 \ 87 + 1 88 89 universes_at_prev_state = count_universes_at( 90 (player_idx + 1) % 2 + 1, 91 winning_score, 92 start_positions, 93 tuple(positions_prev), 94 tuple(scores_prev) 95 ) 96 universes_at_this_state += num_universes \ 97 * universes_at_prev_state 98 return universes_at_this_state 99 100 def count_winning_universes(start_positions: Tuple[int, int], 101 winning_score: int) -> \ 102 Tuple[int, int]: 103 """For the given pair of starting positions, count all of the winning 104 universes for player 1 and player 2 and return the results as a tuple""" 105 count_universes_at.cache_clear() # Shouldn't be necessary 106 player_1_wins = 0 107 player_2_wins = 0 108 for winner_score in range(winning_score, winning_score+10): 109 for loser_score in range(winning_score): 110 for player_positions in product(range(1, 11), repeat=2): 111 player_1_wins += count_universes_at(1, 112 winning_score, 113 start_positions, 114 player_positions, 115 (winner_score, 116 loser_score)) 117 player_2_wins += count_universes_at(2, 118 winning_score, 119 start_positions, 120 player_positions, 121 (loser_score, 122 winner_score)) 123 return (player_1_wins, player_2_wins) 124 125 # The next two functions aren't part of the solution, but they did help me get 126 # there so I'm saving them. 127 128 def step_simulation(game_state: Tuple[int, Tuple[int, int], 129 Tuple[int, int], Tuple[int, int]], 130 winning_score: int, 131 game_state_dict: Dict) -> Dict: 132 """Advance the game state through one player's turn""" 133 # Previous puzzles offered simpler input to facilitate debugging, but this 134 # one is trash, so this function brute forces a few steps of the game, 135 # counting the paths to each game state 136 player_turn, start_positions, positions, scores = game_state 137 138 # `player_turn` indicates the player who just finished, so we advance that 139 # first 140 current_player = player_turn % 2 + 1 141 142 updated_game_state_dict = game_state_dict.copy() 143 if max(scores) >= winning_score: 144 return updated_game_state_dict 145 146 universes_here = game_state_dict[game_state] 147 player_idx = current_player - 1 148 new_positions = list(positions) 149 new_scores = list(scores) 150 151 for die_roll, num_universes in UNIVERSES_PER_MOVE: 152 new_positions[player_idx] = (positions[player_idx] - 1 + die_roll) \ 153 % 10 + 1 154 new_scores[player_idx] = scores[player_idx] + new_positions[player_idx] 155 new_game_state = (current_player, 156 start_positions, 157 cast(Tuple[int, int], 158 tuple(new_positions)), 159 cast(Tuple[int, int], 160 tuple(new_scores))) 161 if new_game_state not in updated_game_state_dict: 162 updated_game_state_dict[new_game_state] = 0 163 updated_game_state_dict[new_game_state] += universes_here \ 164 * num_universes 165 updated_game_state_dict = step_simulation(new_game_state, winning_score, 166 updated_game_state_dict) 167 return updated_game_state_dict 168 169 def run_simulation(start_positions: Tuple[int, int], winning_score: int) -> Dict: 170 """Initialize the simulation and run it""" 171 # A procedure like this _could_ be used to solve the puzzle, but it takes 172 # too long 173 initial_game_state = (2, start_positions, start_positions, (0, 0)) 174 return step_simulation(initial_game_state, winning_score, 175 {initial_game_state: 1}) 176 177 def solve_puzzle(input_string: str) -> int: 178 """Return the numeric solution to the puzzle""" 179 return max(count_winning_universes(parse_input(input_string), 21)) 180 181 def main() -> None: 182 """Run when the file is called as a script""" 183 assert solve_puzzle(EXAMPLE_INPUT) == 444356092776315 184 print("Total universes for winner:", 185 solve_puzzle(get_puzzle_input(21))) 186 187 if __name__ == "__main__": 188 main()