# Advent of Code 2020: Day 15

## 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.

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 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 history; std::unordered_map::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