Advent of Code 2020: Day 22

, 11 min read
advent of code 2020

Part 1

It only takes a few hours of sailing the ocean on a raft for boredom to sink in. Fortunately, you brought a small deck of space cards! You’d like to play a game of Combat, and there’s even an opponent available: a small crab that climbed aboard your raft before you left.

Fortunately, it doesn’t take long to teach the crab the rules.

Before the game starts, split the cards so each player has their own deck (your puzzle input). Then, the game consists of a series of rounds: both players draw their top card, and the player with the higher-valued card wins the round. The winner keeps both cards, placing them on the bottom of their own deck so that the winner’s card is above the other card. If this causes a player to have all of the cards, they win, and the game ends.

For example, consider the following starting decks:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
Player 1:
9
2
6
3
1

Player 2:
5
8
4
7
10

Once the game ends, you can calculate the winning player’s score. The bottom card in their deck is worth the value of the card multiplied by 1, the second-from-the-bottom card is worth the value of the card multiplied by 2, and so on. With 10 cards, the top card is worth the value on the card multiplied by 10.

Play the small crab in a game of Combat using the two decks you just dealt. What is the winning player’s score?

You can read the full text here. This problem makes a nice change from the previous days. This puzzle is more of the style: here are the inputs, here are some rules and now figure out what should happen.

We all love board games
We all love board games

First of all we need to parse the input into data containers. Since we are going to be dynamically moving cards from one player to another, quite regularly, we’re going to represent each players decks with lists. Fortunately, parsing today’s input is quite easy,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
std::list<int> deck1;
std::list<int> deck2;

std::fstream myfile("input", std::ios_base::in);
std::string line;
std::getline(myfile, line);
while (std::getline(myfile, line)) {
    if (line == "") {
        std::getline(myfile, line);
        break;
    }
    deck1.push_back(std::stoi(line));
}
while (std::getline(myfile, line)) {
    deck2.push_back(std::stoi(line));
}
myfile.close();

In the above code we just have two while loops which grab every number in each of the two players decks, convert them to integers and store them. Awesome, we are ready to play the game!

I’ve written a short function which plays the game, I’ll drop the code below it and then we can walk through it.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
int play_game1(std::list<int> deck1, std::list<int> deck2) {
    while ((deck1.size() > 0) && (deck2.size() > 0)) {
        int v1 = deck1.front();
        int v2 = deck2.front();
        deck1.pop_front();
        deck2.pop_front();

        if (v1 > v2) {
            deck1.push_back(v1);
            deck1.push_back(v2);
        } else if (v2 > v1) {
            deck2.push_back(v2);
            deck2.push_back(v1);
        }
    }

    if (deck1.size() > 0)
        return calculate_score(deck1);
    else
        return calculate_score(deck2);
}

We start off with a while loop such that we continue to play the game until one of the players has run out of cards. Every loop represents a round in the game. Under the current rules, we take the top cards on each deck, which is the first value in the list, and then we compare the value of the cards for each player. The player with the highest value of the two cards gets both cards, and they place them at the back of their deck, highest value first. Then we play again!

Finally, once a player runs out of cards, we need to find their score. We do this by looping through every card in the deck. The score is calculated by summing the index multiplied by the face value of every card. Note: we always know which player will win, the player with the highest value card. Thus, if the score was independent of the deck order, this whole game would be pointless, and we could just read off the winner and score.

The calculate_score function is quite simple,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int calculate_score(std::list<int> &deck) {
    int score = 0;
    int i = 1;
    std::list<int>::reverse_iterator it = deck.rbegin();
    while (it != deck.rend()) {
        score += (i++) * (*it);
        it = std::next(it);
    }
    return score;
}

where I’m going through the deck in reverse order using a reverse_iterator. Putting all of this together earns us our first ⭐!

The full code can be found on github

Part 2

You lost to the small crab! Fortunately, crabs aren’t very good at recursion. To defend your honor as a Raft Captain, you challenge the small crab to a game of Recursive Combat.

Recursive Combat still starts by splitting the cards into two decks (you offer to play with the same starting decks as before - it’s only fair). Then, the game consists of a series of rounds with a few changes:

  1. Before either player deals a card, if there was a previous round in this game that had exactly the same cards in the same order in the same players' decks, the game instantly ends in a win for player 1. Previous rounds from other games are not considered. (This prevents infinite games of Recursive Combat, which everyone agrees is a bad idea.) Otherwise, this round’s cards must be in a new configuration; the players begin the round by each drawing the top card of their deck as normal.
  1. If both players have at least as many cards remaining in their deck as the value of the card they just drew, the winner of the round is determined by playing a new game of Recursive Combat (see below). Otherwise, at least one player must not have enough cards left in their deck to recurse; the winner of the round is the player with the higher-value card.

During a round of Recursive Combat, if both players have at least as many cards in their own decks as the number on the card they just dealt, the winner of the round is determined by recursing into a sub-game of Recursive Combat. (For example, if player 1 draws the 3 card, and player 2 draws the 7 card, this would occur if player 1 has at least 3 cards left and player 2 has at least 7 cards left, not counting the 3 and 7 cards that were drawn.)

To play a sub-game of Recursive Combat, each player creates a new deck by making a copy of the next cards in their deck (the quantity of cards copied is equal to the number on the card they drew to trigger the sub-game). During this sub-game, the game that triggered it is on hold and completely unaffected; no cards are removed from players' decks to form the sub-game. (For example, if player 1 drew the 3 card, their deck in the sub-game would be copies of the next three cards in their deck.)

Defend your honor as Raft Captain by playing the small crab in a game of Recursive Combat using the same two decks as before. What is the winning player’s score?

You can read the full text here. Nice - some enforced recursion. I sort of tend to avoid recursion, but in this case, it is much easier to just implement a recursive function.

Other than recursion, this problem got slightly more complicated because now we care about our decks' history. One of the new rules is designed to prevent an infinite loop. It states that if we a reach a state where both players have the same deck, including ordering, that they have both had before, player 1 wins the subgame.

How are we going to store the history? Well, we’re going to be a little lazy and just make a hashmap out of our sets which we use for the decks. However, this is not an optimal type for hashing. In general, if this was production code, then it would be useful attempt to reduce the deck into just a few small numbers which uniquely order the deck. Or at least, sort the history by the size of the deck.

We keep the same rules as before, that is the player with the largest value will win. Unless, we need to recurse. To split the winners we store a positive score for player 1 winning and a negative score when player 2 wins, that way we don’t need any extra variables. The new game can be written like this,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int play_recursive_combat(std::list<int> deck1, std::list<int> deck2) {
    std::map<std::list<int>, int> deck1_history = {};
    std::map<std::list<int>, int> deck2_history = {};

    while ((deck1.size() > 0) && (deck2.size() > 0)) {
        if ((deck1_history.find(deck1) != deck1_history.end()) &&    
            (deck2_history.find(deck2) != deck2_history.end())) {
            return calculate_score(deck1);
        }
        deck1_history.insert({deck1, 1});
        deck2_history.insert({deck2, 1});

        int v1 = deck1.front();
        int v2 = deck2.front();
        deck1.pop_front();
        deck2.pop_front();

        if ((v1 <= int(deck1.size())) && (v2 <= int(deck2.size()))) {
            std::list<int> new_deck1 = {};
            std::list<int> new_deck2 = {};

            int max_val = 0;
            int max_holder = 0;
            std::list<int>::iterator it = deck1.begin();
            for (int i = 0; i < v1; i++) {
                new_deck1.push_back(*it);
                max_val = std::max(*it, max_val);
                it = std::next(it);
            }

            it = deck2.begin();
            for (int i = 0; i < v2; i++) {
                new_deck2.push_back(*it);
                if (*it > max_val){
                    max_holder = 1;
                }
                it = std::next(it);
            }

            int winner = play_recursive_combat(new_deck1, new_deck2);

            if (winner >= 0) {
                deck1.push_back(v1);
                deck1.push_back(v2);
            } else {
                deck2.push_back(v2);
                deck2.push_back(v1);
            }
            ...

We recursively play the game, making new decks as the rules state. This code can be optimised because if player 1 has the highest value card, there is no way they can possibly lose a subgame. Thus,

1
2
3
int winner = 0;
if (max_holder == 1)
    winner = play_recursive_combat(new_deck1, new_deck2);

However, we cannot say the same about player 2. Even if player 2 has the highest value card, they can lose due to the infinite loop rule.

1
2
3
4
5
ans1 = std::abs(play_game1(deck1, deck2));
ans2 = std::abs(play_recursive_combat(deck1, deck2));

std::cout << "Answer 1: " << ans1 << std::endl;
std::cout << "Answer 2: " << ans2 << std::endl;

We just run this code, and we have a full house ⭐⭐!

The full code can be found on github

Reflections

I really enjoyed the game today. It was slightly more straightforward than the previous days, but that was certainly a welcome change. I think the code we’ve written is comparatively readable, but I think it could be optimised further.

I suspect that it should be possible to predict whether a game will lead to recursion. If we can tell ahead of time which subgames will produce recursion, we can avoid many of the subgames as we already know player 1 will win. Similarly, if player 2 has the highest value card, and recursion isn’t possible, player 2 must win. However, I don’t currently know how to predict recursion apriori.

In the first part of this problem the complexity of the solution will scale as O(N)-time and space, where N is total the number of cards in the decks.

In part 2 of the puzzle we recurse. Every time we recurse we reduce the number of cards in the decks by 1. Assuming that both decks have N/2 cards then we can recurse at most N/2-1 times. The memory useage will grow like, N, N-2, N-4, … etc. Thus, this is similar to a sum of natural numbers, and thus will roughly scale as O(N^2)-space. Since we can never revisit the same configuration of cards more than once, the time complexity of part 2 will also scale (roughly) as O(N^2)-time.

Anyway, if I do investigate the possible recursion triggers, I’ll add an update. As always, thanks for reading and see you tomorrow!

. . . .

I have no affiliation with AoC. I’m just a fan of the programming puzzles. If you enjoy them too, please feel free to join in and support the creators

Back to my advent calendar

Comments

Back to all posts