Advent of Code: Day 1

I’ve heard about Advent of Code before, but I never looked into it. After an urge for some programming and no real direction for a side project, I decided I’d try my hand at Advent of Code. To make a hard task even harder, I decided I’d try to solve the problems in Haskell.

Problem

Essentially, Day 1 of AoC boiled down into parsing an input file of integers and finding two things:

1. The sum of all the numbers in the file.
2. The first duplicate sum value in the list. (I’ll explain more on this later)

The only gotcha was that the list looked something like:

+13
-7
-17
+12

Solving Day 1

Part 1

The first thing I was going to have to do was parse the input correctly. Since I’m not familiar with Haskell, I wasn’t sure how it was going to handle trying to parse an input like "+1", so I pulled up a REPL and decided to test this out:

Prelude> read "+1" :: Integer
*** Exception: Prelude.read: no parse

Hmm no luck. What about negative numbers though?

Prelude> read "-1" :: Integer
-1

Okay easy enough, I can just parse negative numbers as I read them and for positive values, just strip the + sign.

Since I come from the Elixir world, I know in Elixir I can do something like:

iex(1)> <<"+", val::binary>> = "+1"
"+1"
iex(2)> val
"1"

Turns out, Haskell has some similar pattern matching. To get an idea for this, I continued to test it out in the REPL

Prelude> let '+':val = "+1"
Prelude> val
"1"

Knowing this, I wrote my first function. The function parseIntPrefix would accept a String and return an Integer. Using pattern matching, I could make this function pretty simple.

parseIntPrefix :: String -> Integer
parseIntPrefix ('+' : num) = read num :: Integer
parseIntPrefix num = read num :: Integer

Now I’ll just have to read lines from the file and sum them up. To do that, I used the readFile function and lines to split that input into a list of lines. We can then simply map over this list to convert our frequencies from Strings to Integers. Finally, we can the use the sum function to add them all up.

Doing that, gives us

module Main where

parseIntPrefix :: String -> Integer
parseIntPrefix ('+' : num) = read num :: Integer
parseIntPrefix num = read num :: Integer

main = do
  content <- readFile "day1_input.txt"
  let sumFreq = sum $ map parseIntPrefix (lines content)

Part 2

I didn’t have a great summarization of Part 2 of Day 1 in the above section, so I’ll try to explain it more detail here. Essentially, we need to keep the accumlated value while we add up all the values in the list. We then need to find the first duplicate accumlated value. If you consider a list like

+2
+2
-4
+1

Then 2 would be the first duplicate value.

To make it a little more difficult, it could be that the value isn’t found the first time through the list.

When I first started to read about this problem, the first thing that came to mind was that I’d need a good way to find duplicates and membership. This immediately made me think of using a set.

My solution was to keep a set of all the accumlated values as we traversed through the list. If the new value was in the current set, then we found our frequency. If we made it through the entire set and we didn’t find our frequency, then we need to simply go through the whole list again until we do.

Thinking of this, our function would need a number of things:

• A list of the frequencies that we iterate through
• The same list of frequencies to re-use if we don’t find it through the first iteration through the list
• The lastFreq we calculated
• A set of all the accumlated frequencies we’ve seen so far

Our type signature then looks like this:

findDuplicateFrequency :: [Integer] -> [Integer] -> Integer -> Set Integer -> Integer

Usually with recursive functions, we define our base case first. Typically, the case is when we’ve gotten to the end of a list, but for this function that isn’t, ermm, the case. The base case would be if the next calculated frequency is in the set of previous frequencies, if not then we need to continue searching. Keeping that in mind, our base case looks like:

findDuplicateFrequency (freq:frequencies) freqs lastFreq freqSet =
  if Set.member nextFreq freqSet -- 3
    then nextFreq -- 4
    else findDuplicateFrequency frequencies freqs nextFreq updatedSet -- 5
  where nextFreq = lastFreq + freq -- 1
        updatedSet = Set.insert nextFreq freqSet -- 2

Let’s break down what’s going on here:

1. We calculate our next frequency nextFreq by adding the previous frequency (lastFreq) up with the current one thats the head of the list (freq).
2. We then add that new frequency to our set
3. We check to see if the new frequency is in the set of of our previous frequencies
4. Our base case, if the value is in the set, simply return it.
5. If the value isn’t in the set, recursively call our function with the tail of our set (frequencies), our new frequencey (newFreq), and our updated frequency set (updatedSet).

With this, we’re almost done. The last bit we need to handle is:

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.

To handle this case then we need to handle the case of when we’ve gone through the entire list of frequencies. At this point, we simply need to recursively call our function with our original list of frequencies, which looks like:

findDuplicateFrequency [] freqs lastFreq frequencySet =
  findDuplicateFrequency freqs freqs lastFreq frequencySet

Putting it all together, it looks like this:

module Main where

import qualified Data.Set as Set

parseIntPrefix :: String -> Integer
parseIntPrefix ('+' : num) = read num :: Integer
parseIntPrefix num = read num :: Integer

findDuplicateFrequency :: [Integer] -> [Integer] -> Integer -> Set Integer -> Integer
findDuplicateFrequency [] freqs lastFreq frequencySet =
  findDuplicateFrequency freqs freqs lastFreq frequencySet
findDuplicateFrequency (freq:frequencies) freqs lastFreq freqSet =
  if Set.member nextFreq freqSet
    then nextFreq
    else findDuplicateFrequency frequencies freqs nextFreq updatedSet
  where nextFreq = lastFreq + freq
        updatedSet = Set.insert nextFreq freqSet

main = do
  content <- readFile "day1_input.txt"
  let frequencies = map parseIntPrefix (lines content)
  let dupFreq = findDuplicateFrequency frequencies frequencies 0 Set.empty
  print dupFreq