Sean McLemon | Advent of Code

Home | Czech | Blog | GitHub | Advent Of Code | Notes


2021-12-21 - Dirac Dice

(original .ipynb)

Day 21 puzzle input is just two players and their starting positions for a game involving dice (mine is here). Part 1 involves playing the game to completion and multiplying the score of the losing player by the number of dice rolls. Part 2 involves doing the same but with a special "quantum" die that simulates ever possible dice outcome. This was a weird one.

test_input_str = """Player 1 starting position: 4
Player 2 starting position: 8"""

puzzle_input_str = """Player 1 starting position: 8
Player 2 starting position: 1"""

def roller():
    n = 1
    while True:
        yield n
        n += 1
        if n > 100:
            n = 1
        

def score(position):
    return position + 1
        
    
def parse_player(line):
    # use 0-indexed positions, makes the moving + scoring a little easier
    return int(line[-1]) - 1


def next_position(p, move):
    return (p + move) % 10


def part_one(input_str):
    roll_count = 0
    p1, p2 = [parse_player(line) for line in input_str.split("\n")]
    
    p1_score, p2_score = 0,0
    dice = roller()
    
    while True:
        p1_move = next(dice) + next(dice) + next(dice)
        roll_count += 3
        p1 = next_position(p1, p1_move)
        p1_score += score(p1)
        
        if p1_score >= 1000:
            break
        
        p2_move = next(dice) + next(dice) + next(dice)
        roll_count += 3
        p2 = next_position(p2, p2_move)
        p2_score += score(p2)
        
        if p2_score >= 1000:
            break

    return min(p1_score, p2_score) * roll_count


assert 739785 == part_one(test_input_str)
print("part one:", part_one(puzzle_input_str))
part one: 518418
%%time
# Rob was curious how long it takes, so let's %%time it and see...

from functools import cache

def roll_sequences():
    sides = (1,2,3)
    for r1 in sides:
        for r2 in sides:
            for r3 in sides:
                yield r1, r2, r3

                
@cache
def play(p1_master, p1_score_master, p2_master, p2_score_master):
    p1_wins = 0 
    p2_wins = 0
    
    rolls = list(roll_sequences())
    
    for p1_roll in rolls:
        for p2_roll in rolls:
            p1,       p2       = p1_master,       p2_master
            p1_score, p2_score = p1_score_master, p2_score_master           
            
            p1_move = sum(p1_roll)
            p1 = next_position(p1, p1_move)
            p1_score += score(p1)
            if p1_score >= 21:
                p1_wins += 1
                break

            p2_move = sum(p2_roll)
            p2 = next_position(p2, p2_move)
            p2_score += score(p2)
            if p2_score >= 21:
                p2_wins += 1
                continue

            p1_rec_wins, p2_rec_wins = play(p1, p1_score, p2, p2_score)
            p1_wins += p1_rec_wins
            p2_wins += p2_rec_wins

    return p1_wins, p2_wins


def part_two(input_str):
    p1, p2 = [parse_player(line) for line in input_str.split("\n")]
    return max(play(p1, 0, p2, 0))


assert 444356092776315 == part_two(test_input_str)
print("part two:", part_two(puzzle_input_str))
part two: 116741133558209
CPU times: user 6.98 s, sys: 3.95 ms, total: 6.99 s
Wall time: 7.07 s