Advent of Code 2020: Day 22 with Python

Another quick one today. Just some plain old python list manipulation and recursion

The Challenge Part 1

Link to challenge on Advent of Code 2020 website

The challenge involves playing out a card game, that has a simple set of rules. So involves keeping track of two stacks of cards. The rules are simple: both players play one card from the top of their deck, highest card wins, winning player keeps both cards.

The solution

Starting with a no-frills import: just splitting the data by hand to save time, and cast everything to ints

data = open("input.txt").read().splitlines()
player1 = list(map(int, data[1:26]))
player2 = list(map(int, data[28:54]))

Then, pretty much just loop until one player is empty, using .pop() to remove an item from the list

while player1 and player2:
    card1 = player1.pop(0)
    card2 = player2.pop(0)
    if card1 > card2:
        player1.extend([card1, card2])
    else:
        player2.extend([card2, card1])

Finally, calculate the sum according to the rules of the challenge: last card is worth 1, next is worth 2, etc.

win = player1 if player1 else player2
print("sum", sum((a+1) * b for a, b in enumerate(reversed(win))))

The full code for the solution to part 1:

data = open("input.txt").read().splitlines()
player1 = list(map(int, data[1:26]))
player2 = list(map(int, data[28:54]))

while player1 and player2:
    card1 = player1.pop(0)
    card2 = player2.pop(0)
    if card1 > card2:
        player1.extend([card1, card2])
    else:
        player2.extend([card2, card1])

win = player1 if player1 else player2
print("sum", sum((a+1) * b for a, b in enumerate(reversed(win))))

The Challenge Part 2

In the 2nd part of the challenge, the game rules are extended to involve a recursive challenge, where at certain points during the game, a subset of cards are used to play another, smaller game, to determine the winner. The sub-game can itself spawn further games.

There's also an added provision to record each hand of the sub-game, and abort if it starts to loop.

So..., we need to keep track of hands. Since dicts are O(1) lookup, we'll use that, and we'll just stringify the hards (since it's convenient).

Here, we return 0 for a player1 win (as required by the rules)

def game(player1, player2):
    records = {}

    while player1 and player2:
        key = str(player1)+str(player2)
        if key in records:
            return 0
        records[key] = None

        ...

Next, we add the extra game rule for recursing into subgames, and returning the winner. The subgame uses a subset of the cards, which is generated using the slice notation. This copies the list, so it leaves the original untouched, which is desired. The rest of the game rules are the same

    card1 = player1.pop(0)
    card2 = player2.pop(0)

    if len(player1) >= card1 and len(player2) >= card2:
        winner = game(player1[:card1], player2[:card2])
    else:
        winner = card2 > card1

    if winner:
        player2.extend([card2, card1])
    else:
        player1.extend([card1, card2])

The full loop looks like this:

def game(player1, player2):
    records = {}

    while player1 and player2:
        key = str(player1)+str(player2)
        if key in records:
            return 0
        records[key] = None

        card1 = player1.pop(0)
        card2 = player2.pop(0)

        if len(player1) >= card1 and len(player2) >= card2:
            winner = game(player1[:card1], player2[:card2])
        else:
            winner = card2 > card1

        if winner:
            player2.extend([card2, card1])
        else:
            player1.extend([card1, card2])

    return winner

winner = game(player1, player2)

Unfortunately this function only returns who won, but we actually need their hand, so let's make a small adjustment to output the last winning hand, and that's our solution.

The full code:

data = open("input.txt").read().splitlines()
player1 = list(map(int, data[1:26]))
player2 = list(map(int, data[28:54]))

def game(depth, player1, player2):
    records = {}

    while player1 and player2:
        key = str(player1)+str(player2)
        if key in records:
            return 0
        records[key] = None

        card1 = player1.pop(0)
        card2 = player2.pop(0)

        if len(player1) >= card1 and len(player2) >= card2:
            winner = game(depth+1, player1[:card1], player2[:card2])
        else:
            winner = card2 > card1

        if winner:
            player2.extend([card2, card1])
        else:
            player1.extend([card1, card2])

    if depth == 0:
        return (player2 if winner else player1)

    return winner

windeck = game(0, player1, player2)
print("sum", sum((a+1) * b for a, b in enumerate(reversed(windeck ))))

All done. Onward!