In today's puzzle "Rambunctious Recitation" we check in with our elf friends at the North Pole and learn about the game they're playing:

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:

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.

This turns out to be Van Eck's sequence. That doesn't help you much with the solution (at least it didn't help me), but it's fun to know.

To solve Part 1 -- what will be the 2020th number spoken -- I set up a dictionary to keep track of the number of turns since the last time a number was seen. This worked really well for the test cases and part 1.

For Part 2 we need to find the 30000000th number spoken and my routine bogs down -- probably because of the “update” function where I add 1 to all the counters.

I think about some other possible solutions:

• I could use a list and search for the last time the number was used, but that would be very slow.

• What if I use a list but remove earlier numbers when they’re used again. So in the example we have: 0, 3, 6, 0, 3, 3, 1, 0, 4, 0 But at this point all we really need are: 6, 3, 1, 4, 0 -- problem is that by removing the earlier 3s and 0s we lose information we need. Counting back to the last 1 would give 3 instead of 4.

These don't seem viable. I still think a dictionary is the best bet.

I check some other solutions on reddit and find they look almost exactly the same as mine, but run fast. Wait a minute! Instead of saving the count since last seeing the number (and updating all counts at every step) I should just save the step each was last updated, then subtract! So obvious. It's still a bit slow, but reasonable. And Part 2 is done. See the full solution on Github.