Advent of Code 2020: Python Solution Day 15

#adventofcode #algorithms #challenge #python

Now elves are causing our system to heat up. First part was easy because we only had to loop until 2021 but the second part is insanely huge. First I used normal dictionary and list for first part. And speed was not a problem for first part. But for second part, time we need is 14,851.485 more than for the first part. So after scrolling more and more reddit threads, I knew defaultdict and deque is the best option.

Part 1 and 2

from collections import *
def day15(filename, turns):
    with open(filename) as fp:
        lines = [l.rstrip() for l in fp.readlines()]
        lines = [int(l) for l in lines[0].split(",")]

    num_to_speak = lines[-1]
    turn_num = defaultdict(deque)

    for v, k in enumerate(lines):
        turn_num[k].append(v+1)

    turn = len(lines)+1
    while turn<=turns:
        l = len(turn_num[num_to_speak]) 
        if l>1:
            num_to_speak = turn_num[num_to_speak][-1] - turn_num[num_to_speak][-2]
            turn_num[num_to_speak].append(turn)
        elif l==1:
            num_to_speak = 0
            turn_num[num_to_speak].append(turn)
        else:
            num_to_speak = 0
            turn_num[num_to_speak].append(turn)

        turn+=1
    print(num_to_speak)

day15("day15.txt", 2020)
day15("day15.txt", 30000000)