Advent of Code: Day 4 Solution

It gets harder

Today was the first day that was a little more difficult than a simple algorithm to solve a problem. I appreciate that the difficulty seems to be increasing this year over last.

The premise today was to take a line and iterate over the letters of an input and generate a checksum. If the checksum was correct, add some numbers to a running sum. This seemed simple enough but ended up taking a little longer than I anticipated when first starting today.

As always, the code for today is available on Github.

Part 1

import re

# Read in the input file.
with open ("input.txt", "r") as myfile:  
    data=myfile.readlines()

def makeChecksum(countLookup):  
    count = max(countLookup.keys(), key=int)
    checksumArray = []
    while count > 0:
        for letter in countLookup[count]:
            checksumArray.append(letter)
        count -= 1
    return "".join(checksumArray[:5])

validSum = 0  
for line in data:  
    letterDict = {}
    countLookup = {1: []}
    print line
    matchGroup = re.match('(.+?)-(\d+?)\[(.+?)\]', line)
    letters = matchGroup.group(1).replace('-', '')
    numbers = int(matchGroup.group(2))
    checksum = matchGroup.group(3)

    print "letters: " + letters
    print "numbers: " + str(numbers)
    print "checksum: " + checksum

    for letter in letters:
        if letter in letterDict:
            letterDict[letter] += 1
            letterCount = letterDict[letter]
            countLookup[letterCount - 1].remove(letter)
            if letterCount not in countLookup:
                countLookup[letterCount] = []
            countLookup[letterCount].append(letter)
            countLookup[letterCount].sort()
        else:
            letterDict[letter] = 1
            countLookup[1].append(letter)
            countLookup[1].sort()
    print letterDict
    print countLookup
    if makeChecksum(countLookup) == checksum:
        validSum += numbers
print validSum  

This code seemed easy when first starting but ended up being quite convoluted. The algorithm functions in the following steps:

  • Run a regex (.+?)-(\d+?)\[(.+?)\] to split the line into the letters, numbers, and checksum.
  • Iterate over the letters
  • If the current letter has been seen before, increment its count and move it to a higher count in the lookup dictionary
  • If the letter is new, add it to the count lookup dictionary as being seen once, and set its count to 1.
  • Make a checksum by taking the top 5 most commonly seen letters in alphabetic order
  • If the checksum matches the provided one, increment the sum by the numbers in the string.

Part 2:

import re  
import string

# Read in the input file.
with open ("input.txt", "r") as myfile:  
    data=myfile.readlines()

def caesar(plaintext, shift):  
    while shift > 26:
        shift -= 26
    alphabet = string.ascii_lowercase
    shifted_alphabet = alphabet[shift:] + alphabet[:shift]
    table = string.maketrans(alphabet, shifted_alphabet)
    return plaintext.translate(table)

for line in data:  
    print line
    matchGroup = re.match('(.+?)-(\d+?)\[(.+?)\]', line)
    letters = matchGroup.group(1)
    numbers = int(matchGroup.group(2))
    checksum = matchGroup.group(3)

    print "letters: " + letters
    print "numbers: " + str(numbers)
    print "checksum: " + checksum
    roomName = caesar(letters, numbers)

    if "north" in roomName:
        print numbers
        break

The second part of the day asked to treat each string as a Caesar Cipher, and find the one talking about North Pole Object Storage. Once finding and modifying a simple python Caesar Cipher function, this part was pretty simple.

For reference, my input file is available here. The answers I came up with were:

  • Part 1: 185371
  • Part 2: 984

This code took a bit of time to write and I'm sure it could be improved. Any tips? Reach out to me on Github or Twitter!