Advent of Code 2018 - Day 1

Day 1: Chronal Calibration

Useful Links

• 2018 Main Page
• My solution code

Concepts and Packages Demonstrated

itertools.cycleSets

Problem Intro

It’s 2018, and we’re fixing time anomalies! We’re 500 years in the past, and our device needs calibration. It’s showing us a sequence of frequency changes.

The input looks like this:

+1
-2
+3
+1

Each line represents a change in frequency (delta). We start at 0.

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 simply need to add up all the numbers in the input.

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

We can iterate through the list of strings, convert each to an int, and add it to our running total. Note that int() in Python handles the + sign correctly (e.g., int("+1") is 1), so we don’t need any special parsing.

Part 2

What is the first frequency your device reaches twice?

Now we need to keep applying the frequency changes over and over again until we land on a frequency that we have seen before.

• We need to store the frequencies we have visited. A set is perfect for this because it offers O(1) lookup time.
• We need to loop through the input data indefinitely, because we might need to process the list of frequency changes many times before we find a repeat. itertools.cycle is ideal for this. It takes our input list and creates an infinite iterator that repeats the list elements over and over. This saves us from having to write a while loop with index management (e.g. index = (index + 1) % len(data)).

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}
    for freq_chg in cycle(data):
        freq += int(freq_chg)
        if freq in seen:
            break
        
        seen.add(freq)
    
    return freq

We iterate through the cycled data. Note that we initialize seen with {0} because we start at frequency 0, and we need to catch if the frequency drift brings us back to 0.

For each change:

1. Update the current frequency.
2. Check if this new frequency is in our seen set.
   • If yes, we found our answer! Break the loop.
   • If no, add it to the set and continue.

Results

The output looks like this:

Part 1 soln=433
Part 2 soln=256