commitae50a2184f97659c33b8f5fdf8c09fa3616a6ddeparent3f6cc45aa78990392a25e6dc7ff69e6b5070a82cAuthor:Eamon Caddigan <eamon.caddigan@gmail.com>Date:Wed, 22 Dec 2021 08:28:07 -0500 Solution to day 21, part 2Diffstat:

A | day21_part2.py | | | 188 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |

1 file changed, 188 insertions(+), 0 deletions(-)diff --git a/day21_part2.py b/day21_part2.py@@ -0,0 +1,188 @@ +#!/usr/bin/env python +"""Advent of Code 2021, day 21 (part 2): Dirac Dice +Simulating an Advent of Code board game (with a multiverse die!)""" + +# Well I'm glad I didn't overengineer part 1 because I didn't expect this. +# +# It's infeasible to enumerate all of the possible outcomes. I think the +# "trick" is to recognize that on each turn, a player can only advance 3, 4, +# ..., 9 spaces, but each of these outcomes is associated with a different +# number of "universes" (e.g., only one universe results in a move of 3 spaces, +# but 3 different universes are associated with a 4-space move). +# +# The state space is strictly less than 2 x 10 x 10 x 30 x 30 possible player +# turn / player 1 position / player 2 position / player 1 score / player 2 +# score combinations, as many of these are impossible (no score above 30 needs +# to be considered, because a winning score above 30 isn't possible). So we can +# recursively explore the number of universes that wind up at each possible +# winning condition. The number of universes at state n = the sum of the +# product of the number of universes from each previous state by the number of +# universes that arrive at _that_ state. The base condition is the starting +# state of the game: both players have a score of 0 and their pawn at their +# respective starting position, this state has exactly 1 universe (and +# "impossible" states have 0 universes). So this is a perfect application for +# memoization, which is fairly easy with functools.lru_cache. + +from typing import Tuple, Dict, cast +from functools import lru_cache +from itertools import product + +from day21_part1 import EXAMPLE_INPUT, parse_input +from utils import get_puzzle_input + +# I know globals are ugly but whatcha gonna do? +UNIVERSES_PER_MOVE = tuple((k + 3, v) for k, v in \ + enumerate([1, 3, 6, 7, 6, 3, 1])) + +@lru_cache(maxsize=None) +def count_universes_at(player_turn: int, + winning_score: int, + start_positions: Tuple[int, int], + positions: Tuple[int, int], + scores: Tuple[int, int]) -> int: + """Find the number of universes that lead to the current state recursively. + `player_turn` indicates which player just _finished_ their turn, and we're + treating the starting state of the game as a though player 2 just finished + (since player 1 goes first)""" + player_idx = player_turn - 1 + + # First, check if it's an "impossible" state + impossible_state = min(scores) > winning_score \ + or max(scores) > winning_score + 9 + for player in range(2): + # No player can have a score less than zero, and if the score _is_ + # zero, their position must be their starting position + impossible_state |= scores[player] < 0 + if scores[player] == 0: + impossible_state |= positions[player] != start_positions[player] + # Player 2 can't have points before player 1 + impossible_state |= scores[0] == 0 and scores[1] > 0 + # If both players have 0 points, then player 2 just "finished" + if scores == (0, 0): + impossible_state |= player_turn != 2 + + # The player's previous score was their current score minus their + # current position (e.g., if they're on space 4 with a score of 12, + # then their last score had to be 8) + scores_prev = list(scores) + scores_prev[player_idx] = scores[player_idx] - positions[player_idx] + + # If this is a winning score, the previous score could not also have been a + # winning score, which means that the previous score could never have been + # a winning score. + impossible_state |= scores_prev[player_idx] >= winning_score + + universes_at_this_state = 0 + if not impossible_state: + if scores == (0, 0): + # Base case + universes_at_this_state = 1 + else: + # We entered the current state following a move from the current + # player. + for die_roll, num_universes in UNIVERSES_PER_MOVE: + positions_prev = list(positions) + positions_prev[player_idx] = (positions[player_idx] - 1 + - die_roll) % 10 \ + + 1 + + universes_at_prev_state = count_universes_at( + (player_idx + 1) % 2 + 1, + winning_score, + start_positions, + tuple(positions_prev), + tuple(scores_prev) + ) + universes_at_this_state += num_universes \ + * universes_at_prev_state + return universes_at_this_state + +def count_winning_universes(start_positions: Tuple[int, int], + winning_score: int) -> \ + Tuple[int, int]: + """For the given pair of starting positions, count all of the winning + universes for player 1 and player 2 and return the results as a tuple""" + count_universes_at.cache_clear() # Shouldn't be necessary + player_1_wins = 0 + player_2_wins = 0 + for winner_score in range(winning_score, winning_score+10): + for loser_score in range(winning_score): + for player_positions in product(range(1, 11), repeat=2): + player_1_wins += count_universes_at(1, + winning_score, + start_positions, + player_positions, + (winner_score, + loser_score)) + player_2_wins += count_universes_at(2, + winning_score, + start_positions, + player_positions, + (loser_score, + winner_score)) + return (player_1_wins, player_2_wins) + +# The next two functions aren't part of the solution, but they did help me get +# there so I'm saving them. + +def step_simulation(game_state: Tuple[int, Tuple[int, int], + Tuple[int, int], Tuple[int, int]], + winning_score: int, + game_state_dict: Dict) -> Dict: + """Advance the game state through one player's turn""" + # Previous puzzles offered simpler input to facilitate debugging, but this + # one is trash, so this function brute forces a few steps of the game, + # counting the paths to each game state + player_turn, start_positions, positions, scores = game_state + + # `player_turn` indicates the player who just finished, so we advance that + # first + current_player = player_turn % 2 + 1 + + updated_game_state_dict = game_state_dict.copy() + if max(scores) >= winning_score: + return updated_game_state_dict + + universes_here = game_state_dict[game_state] + player_idx = current_player - 1 + new_positions = list(positions) + new_scores = list(scores) + + for die_roll, num_universes in UNIVERSES_PER_MOVE: + new_positions[player_idx] = (positions[player_idx] - 1 + die_roll) \ + % 10 + 1 + new_scores[player_idx] = scores[player_idx] + new_positions[player_idx] + new_game_state = (current_player, + start_positions, + cast(Tuple[int, int], + tuple(new_positions)), + cast(Tuple[int, int], + tuple(new_scores))) + if new_game_state not in updated_game_state_dict: + updated_game_state_dict[new_game_state] = 0 + updated_game_state_dict[new_game_state] += universes_here \ + * num_universes + updated_game_state_dict = step_simulation(new_game_state, winning_score, + updated_game_state_dict) + return updated_game_state_dict + +def run_simulation(start_positions: Tuple[int, int], winning_score: int) -> Dict: + """Initialize the simulation and run it""" + # A procedure like this _could_ be used to solve the puzzle, but it takes + # too long + initial_game_state = (2, start_positions, start_positions, (0, 0)) + return step_simulation(initial_game_state, winning_score, + {initial_game_state: 1}) + +def solve_puzzle(input_string: str) -> int: + """Return the numeric solution to the puzzle""" + return max(count_winning_universes(parse_input(input_string), 21)) + +def main() -> None: + """Run when the file is called as a script""" + assert solve_puzzle(EXAMPLE_INPUT) == 444356092776315 + print("Total universes for winner:", + solve_puzzle(get_puzzle_input(21))) + +if __name__ == "__main__": + main()