Advent of Code 2020: Day 23

, 10 min read
advent of code 2020

Part 1

The small crab challenges you to a game! The crab is going to mix up some cups, and you have to predict where they’ll end up.

The cups will be arranged in a circle and labeled clockwise (your puzzle input). For example, if your labeling were 32415, there would be five cups in the circle; going clockwise around the circle from the first cup, the cups would be labeled 3, 2, 4, 1, 5, and then back to 3 again.

Before the crab starts, it will designate the first cup in your list as the current cup. The crab is then going to do 100 moves.

Each move, the crab does the following actions:

  1. The crab picks up the three cups that are immediately clockwise of the current cup. They are removed from the circle; cup spacing is adjusted as necessary to maintain the circle.
  1. The crab selects a destination cup: the cup with a label equal to the current cup’s label minus one. If this would select one of the cups that was just picked up, the crab will keep subtracting one until it finds a cup that wasn’t just picked up. If at any point in this process the value goes below the lowest value on any cup’s label, it wraps around to the highest value on any cup’s label instead.
  1. The crab places the cups it just picked up so that they are immediately clockwise of the destination cup. They keep the same order as when they were picked up. 4) The crab selects a new current cup: the cup which is immediately clockwise of the current cup.

For example, suppose your cup labeling were 389125467. If the crab were to do merely 10 moves, the following changes would occur:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
    -- move 1 --
    cups: (3) 8  9  1  2  5  4  6  7
    pick up: 8, 9, 1
    destination: 2


    -- move 2 --
    cups:  3 (2) 8  9  1  5  4  6  7
    pick up: 8, 9, 1
    destination: 7

    -- move 3 --
    cups:  3  2 (5) 4  6  7  8  9  1
    pick up: 4, 6, 7
    destination: 3

    ...

After the crab is done, what order will the cups be in? Starting after the cup labeled 1, collect the other cups' labels clockwise into a single string with no extra characters; each number except 1 should appear exactly once. In the above example, after 10 moves, the cups clockwise from 1 are labeled 9, 2, 6, 5, and so on, producing 92658374. If the crab were to complete all 100 moves, the order after cup 1 would be 67384529.

Using your labeling, simulate 100 moves. What are the labels on the cups after cup 1?

You can read the full text here. I initially thought that this puzzle would be quite trivial.

I thought all I would need to do is pop the numbers into a list and then implement the game rules. But, after some thought I changed strategy. In part 2 this change of strategy turned out to be incredibly beneficial. As the numbers in the list are moving around so often I came to the conclusion that using a std::list would be too slow due too much memory reallocation. Thus, I instead decide to make a class of Cups. In this class each cup stores a pointer to the next cup in the sequence, along with the current value of the cup.

Cup switcharoo
How will the cups end up?
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Cup {
    public:
        Cup * next;
        int value;

        Cup (int v) : value(v) {};
        void set_next(Cup * n){
            next = n;
        };
};

Now we store the cups in a vector where the cups never move, we just change their pointers, so they point to a different next cup. We start by allocating our vector of cups. Initially, our cups start in the following order,

1
2
3
4
 std::vector<int> order = {1, 9, 3, 4, 6, 7, 2, 5, 8};
 std::vector<Cup> cups;
 for(int i=1; i<num_cups; i++)
     cups.push_back(Cup(i));

each cup will point to the next cup in the vector except the final cup which points back to the beginning.

We initialise the pointers as so,

1
2
3
4
5
6
7
// Set up pointers to match initial order
Cup * temp;
for(int i=0; i<order.size()-1; i++){
    temp = &cups[order[i]-1];
    temp->set_next(&cups[order[i+1]-1]);
}
cups[order[order.size()-1]-1].set_next(&cups[order[0]-1]);

Great, we have our initial configuration of cups. So now we implement the rules of the game. I’ll drop the code below 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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
Cup * curr = &cups[0];
Cup * start, * end, * destination;
for(int i=0; i<reps; i++){
    start = curr->next;
    int target = curr->value - 1;
    if (target == 0)
        target = cups.size();

    // Select pickup
    end = curr;
    for(int j=0; j<3; j++){
        end = end->next;
    }

    // Find destination cup by ensuring our target is not in the pickup
    bool found = false;
    Cup * temp;
    while (!found){
        temp = start;
        found = true;
        for(int j=0; j<3; j++){
            if (temp->value == target){
                target--;
                if (target == 0)
                    target = cups.size();
                found = false;
                break;
            }
            temp = temp->next;
        }
    }
    // Every cup is in order!
    destination = &cups[target-1];

    // Remove the elements
    curr->next = end->next;

    // Reinsert after destination
    temp = destination->next;
    destination->next = start;
    end->next = temp;

    // Move to next cup
    curr = curr->next;
}

We initially start with the first cup and we loop through rep times emulating the actions of the crab.

In each loop, the first thing we do is identify the 3 cups that will be moved. We do this by just looping through the next pointers. Thus, we now have the 3 cups which are going to move. More specifically, we have pointers to the first and last numbers which will move.

Next we need to identify the destination which they are going to end up in. As our cups are in order, we just need to select the Cup at index target-1 in the vector of cups.

Now we have the destination cup and the three cups which move, we can modify our pointers to construct the new ordering. I will give an example of this below,

1
2
3
4
5
6
7
2->3->7->9->1->8
...
2->3->7->9->1->8
MOVE: 3->7->9
INSERT: 1->
....
2->1->3->7->9->8

Great! We can now run 100 of these moves on the cup configuration and produce the final cup layout.

In summary, we are “moving” the cups by just changing the pointers, but cup X is always stored in the vector at index X-1. Please take time to read the code if this seems confusing.

The final code looks like:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int main (int argc, char *argv[]){
    long int ans1 = 0, ans2 = 1;
    std::vector<int> order = {1, 9, 3, 4, 6, 7, 2, 5, 8};
    std::vector<Cup> cups1 = solve(order, 10, 100);
    /* Print all the numbers after cup 1 */
    Cup * start = &cups1[0];
    std::cout << "Answer 1: ";
    start = start->next;
    for(int j=0; j<8; j++){
        std::cout << start->value;
        start = start->next;
    }
    std::cout << std::endl;
    return 0;
}

And there we go, that’s the first ⭐!

The full code can be found on github

Part 2

Due to what you can only assume is a mistranslation (you’re not exactly fluent in Crab), you are quite surprised when the crab starts arranging many cups in a circle on your raft - one million (1000000) in total.

Your labeling is still correct for the first few cups; after that, the remaining cups are just numbered in an increasing fashion starting from the number after the highest number in your list and proceeding one by one until one million is reached. (For example, if your labeling were 54321, the cups would be numbered 5, 4, 3, 2, 1, and then start counting up from 6 until one million is reached.) In this way, every number from one through one million is used exactly once.

After discovering where you made the mistake in translating Crab Numbers, you realize the small crab isn’t going to do merely 100 moves; the crab is going to do ten million (10000000) moves!

The crab is going to hide your stars - one each - under the two cups that will end up immediately clockwise of cup 1. You can have them if you predict what the labels on those cups will be when the crab is finished.

Determine which two cups will end up immediately clockwise of cup 1. What do you get if you multiply their labels together?

You can read the full text here. Wow! These are some big numbers. However, in theory, the changes from part 1 should be fairly straightforward.

We already set up an integer number of cups, so we just increase that value to 1 million. However, we now need to initialise the initial pointers in two steps.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
std::vector<Cup> cups;
for(int i=1; i<num_cups; i++)
    cups.push_back(Cup(i));
// Set up pointers to match initial order
Cup * temp;
for(int i=0; i<order.size()-1; i++){
    temp = &cups[order[i]-1];
    temp->set_next(&cups[order[i+1]-1]);
}
cups[order[order.size()-1]-1].set_next(&cups[order[0]-1]);
// Add pointers between extra values
if (num_cups > order.size()+1){
    int last = order[order.size()-1]-1;
    cups[last].set_next(&cups[order.size()]);
    for(size_t i=order.size(); i<cups.size()-1; i++)
        cups[i].set_next(&cups[i+1]);
    cups[cups.size()-1].set_next(&cups[order[0]-1]);
}

This code is similar to before. We first set up the first 10 cups which are not in order. Then we add the extra values up to 1 million and set their pointers to point to the next cup. The last cup points back to the very first cup.

That’s the only change we need to make. Fortunately we implemented a fast solution which can perform the ten million iterations quite quickly ⭐⭐.

The full code can be found on github

Reflections

I think my code for today’s solution is very readable. I was pleasantly surprised to find that my choice of data abstraction made part 2 incredibly straightforward. However, I don’t always make the right decisions in Advent of Code; I got lucky.

In terms of algorithm I think the code plays the game in a fairly optimal way. In general the bulk allocation of our memory is static, e.g. we are not modifying our vector. Thus, I think our solution will scale as both O(M)-time and O(N)-space, where N is the number of cups, and M is the number of iterations.

I don’t believe it is possible to get the final configuration of cups without playing the game. But maybe it is?

Anyway, thanks for reading, I hope you enjoyed it. I thought today’s puzzle seemed very straightforward but turned out to be secretly quite complicated. 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