Advent of Code 2018 Day 1: Chronal Calibration

This post originally appeared on steadbytes.com

Complete solution can be found on GitHub

Part One

From the puzzle input of frequency changes, we are asked to calculate the resulting frequency after all such changes have occured. This involves two steps:

1. Parse the puzzle input into a sequence of numeric values
2. Add them up!

Parsing Input

Inspecting the puzzle input, we see that each frequency is a positive or negative integer separated by a newline. For example:

+12
-10
-4
-8
+18

To parse this into a sequence of numeric values, we need to:

1. Split the input on newlines
2. Parse a string of the form <sign><value> into a signed integer
   • Regular expression [\+|-]\d+

Splitting a Python file object on newlines is directly supported in the file API:

with open("input.txt") as puzzle_input:
    lines = puzzle_input.readlines()

Parsing each frequency into a signed integer can be achieved using Python's builtin int function directly. When given a string (such as our frequencies) it will coerce the value to an integer, taking into account a sign if present:

>>> int("+15)
15
>>> int("-15")
-15

Wrapping this up in a function, we get:

def parse_frequencies(puzzle_input):
    return [int(f) for f in puzzle_input.readlines()]

Summing Frequencies

Since our frequencies are a list of integers, Python makes this part easy with a call to sum:

def part_1(frequencies):
    return sum(frequencies)

Part Two

Next, we are asked to find the first frequency that occurs twice during sequential application of the frequency changes in the puzzle input. The puzzle description gives an import hint:

Note that your device might need to repeat its list of frequency changes many times before a duplicate frequency is found, and that duplicates might be found while in the middle of processing the list.

With this we can break down the problem:

1. Begin with a frequency of 0
2. Repeatedly iterate over the sequence of frequency changes, applying each change to the current frequency value.
3. Keep track of the frequency value at each iteration.
4. If a frequency is encountered that has been seen previously, return it.

def part_2(frequencies):
    frequency_memo = {0}
    current_frequency = 0
    while True:
        for f in frequencies:
            current_frequency += f
            if current_frequency in frequency_memo:
                return current_frequency
            frequency_memo.add(current_frequency)

Summary

Advent of Code draws us in with a gentle introduction, demonstrating the general puzzle structure:

1. Read some input from a text file.
2. Use it to solve 2 (usually related) puzzles.

Resources

• File objects
• List comprehensions
• Sets