Advent of Code 2018 - Day 1

Useful Links

Concepts and Packages Demonstrated

Problem Intro

We’ve time-travelled 500 years into the past to fix some temporal anomalies. But our device needs calibrating. It shows us a sequence of frequency changes, e.g. +1, -2, +3, +1.

The input data looks like this:

+14
-10
+12
+2
...

Part 1

Starting with a frequency of zero, what is the resulting frequency after all of the changes in frequency have been applied?

This is a straightforward summation problem. We start at 0 and apply each change in the list.

def part1(data):
    """ Calculate the resulting frequency after applying all the deltas in the input data. """
    freq = 0
    for freq_chg in data:
        freq += int(freq_chg)
        
    return freq

Part 2

What is the first frequency your device reaches twice?

Now we need to apply the changes repeatedly, looping through the list of changes as many times as necessary, until we land on a frequency we’ve seen before.

To handle the looping, itertools.cycle is perfect. It takes an iterable (like our list of changes) and returns an iterator that repeats the elements indefinitely.

To keep track of the frequencies we’ve visited, a set is the ideal data structure because it provides $O(1)$ average time complexity for lookups and insertions. We initialize the set with 0 since that’s our starting frequency.

from itertools import cycle

def part2(data):
    """ Apply the deltas in the input data and loop the input indefinitely.
    Exit when we see a frequency we've seen before and return that frequency. """
    freq = 0
    seen = {0} # Initialize with the starting frequency
    
    # cycle() repeats the input data indefinitely
    for freq_chg in cycle(data):
        freq += int(freq_chg)
        if freq in seen:
            break
        
        seen.add(freq)
    
    return freq

Using cycle simplifies the code significantly compared to writing a while True loop with a manual index reset.

Results

The output looks something like this:

Part 1 soln=437
Part 2 soln=655

›