zerosleeps

Since 2010

Advent of Code 2020 day 15

Tuesday 15 December 2020

Advent of Code 2020 day 15. Part one was simple but too slow for part two, so part two uses dictionary lookups. Couldn’t see a way of doing this without storing the last two times each number had been seen.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

def part_one(input, turns):
    memory = list(input)
    for turn in range(len(input), turns):
        if memory[-1] not in memory[0:-1]:
            memory.append(0)
        else:
            memory.append(
                (len(memory) + 1) - (len(memory) - list(reversed(memory[0:-1])).index(memory[-1]))
            )
    return memory[-1]

def part_two(input, turns):
    memory = {
        n: [t]
        for t, n
        in enumerate(INPUT)
    }

    last_number = input[-1]

    for turn in range(len(input), turns):
        if len(memory[last_number]) == 1:
            # Number not seen before
            this_number = 0
        else:
            this_number = memory[last_number][1] - memory[last_number][0]

        if this_number in memory:
            memory[this_number] = [memory[this_number][-1]] + [turn]
        else:
            memory[this_number] = [turn]

        last_number = this_number

    return last_number

if __name__ == '__main__':
    print(f'Part one: {part_one(INPUT, 2020)}')
    print(f'Part two: {part_two(INPUT, 30000000)}')