Advent of Code 2020: Day 15 in Python

Another quick one today for completeness

The Challenge Part 1

Link to challenge on Advent of Code 2020 website

The challenge is sequence building, using a relatively simple algorithm: take the previous number in the sequence, and see if it has occurred before. If it has, next number is how far back the next most recent occurrence was. If not, next number is 0. Find the 2020th number.

Quite simply:

data = [0, 3, 6]

for _ in range(len(data), 2020):
    *history, consider = data
    if consider in history:
        data.append(list(reversed(history)).index(consider)+1)
    else:
        data.append(0)
print("number", data[-1])

(replacing data with actual challenge input)

The Challenge Part 2

The second part asks for the 30000000th number. It's quite possible to run the Part 1 code, it would just take an inordinate amount of time and a fair chunk of RAM. A quick optimization is to realize that we don't need to store and search through the entire history of the data if we just make a lookup table for each number and when it last appeared, updating it as we go.

data = [0, 3, 6]
dictdata = {v:k for k, v in enumerate(data[:-1])}
consider = data[-1]

for idx in range(len(data), 30000000):
    if consider in dictdata:
        next_val = (idx-1) - dictdata[consider]
    else:
        next_val = 0

    dictdata[consider] = idx-1
    consider = next_val
print("number", next_val)

(replacing data with actual challenge input)

Done!

Onwards!