Advent of Code 2020: Day 15

, 5 min read
advent of code 2020

Part 1

You catch the airport shuttle and try to book a new flight to your vacation island. Due to the storm, all direct flights have been cancelled, but a route is available to get around the storm. You take it.

While you wait for your flight, you decide to check in with the Elves back at the North Pole. They’re playing a memory game and are ever so excited to explain the rules!

In this game, the players take turns saying numbers. They begin by taking turns reading from a list of starting numbers (your puzzle input). Then, each turn consists of considering the most recently spoken number:

1
2
3
4
5
6
    If that was the first time the number has been spoken,
    the current player says 0.

    Otherwise, the number had been spoken before; the
    current player announces how many turns apart the
    number is from when it was previously spoken.

So, after the starting numbers, each turn results in that player speaking aloud either 0 (if the last number is new) or an age (if the last number is a repeat).

Given your starting numbers, what will be the 2020th number spoken?

You can read the full text here. The elves have certainly invented a fun game to pass the time. I might propose this game to my friends for our next zoom call.

The game in action
The game in action

For once we don’t need to do any file reading and text parsing! This puzzle gives us a small input, (the starting numbers),

1
0, 8, 15, 2, 12, 1, 4

which we just throw straight into a vector,

1
std::vector<int> starting = {0, 8, 15, 2, 12, 1, 4};

Now, how do we remember when the last time we saw each value was? We could use an array but this would require us either knowing the maximum value that may occur in the sequence apriori, or force us to reallocate the array several times during the run. Instead, we are going to our good old friend, the hashmap. Particularly, I’m using the unordered_map which is a part of the C++ standard library. This map has good look up complexity, and is generally quite fast. The map declaration looks like this:

1
2
std::unordered_map<int, int> history;
std::unordered_map<int, int>::iterator it;

Where we have also declared an iterator which we use to access elements in the map map.

All we need to do now, is set the first number and start looping through the game following the rules that the elves have laid out,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
int index = 0;
int num = starting[0];
while (index < 2020 - 1){
    it = history.find(num);
    if (it == history.end()){
        history.insert({num, index});
        num = 0;
    }
    else{
        num = (index - it->second);
        it->second = index;
    }
    index++;
    // Use the next starting number
    if (index < max_starting) num = starting[index];
}
ans1 = num;

The code snippet above searches our history to see if we have seen a number before. If we haven’t, then the iterator points to the end of the map. In this case, we set the next number to be zero and store the current index in our history for when we see the number in future.

If we have seen the number before then, we just find out how long ago this was, and then update our history to store the new index. Then we increase the index and move on. We also have a small if statement which makes sure we use the starting numbers at small indices.

That’s all we need to do, ⭐!

The full code can be found on github

Part 2

Impressed, the Elves issue you a challenge: determine the 30000000th number spoken.

You can read the full text here. Well, today we don’t really have to do too much, I just modify the code from part 1 to run for longer,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
while (index < 30000000 - 1){
    it = history.find(num);
    if (it == history.end()){
        history.insert({num, index});
        num = 0;
    }
    else{
        num = (index - it->second);
        it->second = index;
    }
    index++;

    if (index < max_starting) num = starting[index];
    if (index == 2019) ans1 = num;
}
ans2 = num;

There we go, ⭐⭐!

The full code can be found on github

Reflections

Today’s puzzle involved us looping through numbers, generating the next number in the sequence N times, where N is the number in the sequence we want to find.

For each value we perform a look up using our unordered_map to see if we seen that number previously. We then insert the current index into the map. For this container type the insertion and lookup should be on average O(1), but at worst O(M) where M is the number of elements stored.

Thus, I think our solution should scale as both O(N)-time and space complexity, but at worst it could scale as O(N^2)-time.

I’m not sure if there is much we can do to improve this complexity. I guess this sequence doesn’t have a closed-form solution. Moreover, I can’t think of a container which has a better complexity for both lookup and insertion.

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