Sean McLemon | Advent of Code

2020-12-22 - Crab Combat

(original .ipynb)

Day 22 input is a listing of the cards two players have (mine is here). Part 1 involves applying the rules of a game until one player has no more cards left. Part 2 playing the game with a small modification - it can recurse into many sub-games.

puzzle_input_str = open("puzzle_input/day22.txt", "r").read()

test_input_str = """Player 1:
9
2
6
3
1

Player 2:
5
8
4
7
10"""

def parse_player(player_str):
    return [int(card) for card in player_str.split("\n")[1:]]

def calc_score(player):
    return sum((1+i) * card for i,card in enumerate(reversed(player)))

def play_combat(player1, player2):    
    while len(player1) != 0 and len(player2) != 0:
        card1 = player1.pop(0)
        card2 = player2.pop(0)
        
        if card1 > card2:
            player1 += [card1, card2]
        else:
            player2 += [card2, card1]

    return calc_score(player1), calc_score(player2)

def part1(input_str):
    player1, player2 = [parse_player(player_str) for player_str in input_str.split("\n\n")]
    return max(play_combat(player1, player2))

assert 306 == part1(test_input_str)

print(part1(puzzle_input_str))

31957

%%time
# ^^ turning on timing so we can see that this is NOT a fast solution

def serialize_hands(player1, player2):
    player1_str = ",".join(str(card) for card in player1)
    player2_str = ",".join(str(card) for card in player2)
    return ":".join([player1_str,player2_str])

def play_recursive_combat(player1, player2):
    previous_hands = set()
    while len(player1) != 0 and len(player2) != 0:
        card1 = player1.pop(0)
        card2 = player2.pop(0)
        
        serialized_hands = serialize_hands(player1, player2)
        if serialized_hands in previous_hands:
            return 1, 0
        elif len(player1) >= card1 and len(player2) >= card2:
            score1, score2 = play_recursive_combat(player1[:card1], player2[:card2])
            if score1 > score2:
                player1 += [card1, card2]
            else:
                player2 += [card2, card1]
        else:
            if card1 > card2:
                player1 += [card1, card2]
            else:
                player2 += [card2, card1]
                
        previous_hands.add(serialized_hands)

    return calc_score(player1), calc_score(player2)

def part2(input_str):
    player1, player2 = [parse_player(player_str) for player_str in input_str.split("\n\n")]
    return max(play_recursive_combat(player1, player2))

assert 291 == part2(test_input_str)

potentially_infinite_game = """Player 1:
43
19

Player 2:
2
29
14"""

# it'll terminate with whatever we determine to be the player1 score
# for an infinite loop - which I have set as 1
assert 1 == part2(potentially_infinite_game)

print(part2(puzzle_input_str))

33212
CPU times: user 12.2 s, sys: 35.8 ms, total: 12.3 s
Wall time: 12.5 s