## DEV Community is a community of 617,782 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Advent of Code 2020: Day 15 in Python

Yuan Gao Updated on ・1 min read

Another quick one today for completeness

# The Challenge Part 1

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!