Advent of Code day 1 [spoilers]

I'm doing Advent of Code in Haskell this year, as planned. I warmed up with one of last year's problems so I was able to get started right away at 11pm last night when the puzzle went live. It still took me about 40 minutes to do both parts of day 1.

Usually I avoid trying to make file I/O work and just include the problem input in my solution. In Haskell this turned out to be more difficult than expected, because it doesn't natively support multi-line strings. So I found a package that lets me do it:

import Text.RawString.QQ
input :: String
input = [r|input
goes
here.|]

http://hackage.haskell.org/package/raw-strings-qq-1.1/docs/Text-RawString-QQ.html

Day 1's input was a set of positive and negative numbers, one per line:

-1
-14
+2
-1
-16
+10
-5
...

I'm sure there's a better way to parse these, but what I ended up with was:

import Data.List.Split

offsetList :: [Int]

readInteger :: String -> Int
readInteger ('+':s) = read s
readInteger ('-':s) = -( read s )

offsetList = Prelude.map readInteger ( splitOn "\n" input )

All this pattern matching makes me feel a little bit like I'm writing Prolog.

That was sufficient for part 1, we just need to run sum over the list. For part 2 we need a data structure, so I found a Set implementation:

http://hackage.haskell.org/package/containers-0.6.0.1/docs/Data-Set.html

The method firstDuplicate walks the list, adding up the total, and checking each total in the set. To solve the problem we need to walk the list some unknown number of times, so I used cycle to turn the finite input into an infinite repeating stream.

firstDuplicate :: Int -> [Int] -> Set Int -> Maybe Int
firstDuplicate tot [] seen
  | member tot seen = Just tot
  | otherwise = Nothing
firstDuplicate tot (x:xs) seen
--  | trace ( "tot=" ++ (show tot) ++ " x=" ++ (show x ) ) False = undefined
  | member tot seen = Just tot
  | otherwise = (firstDuplicate (tot + x) xs ( insert tot seen ))

firstDup :: [Int] -> Maybe Int
firstDup x = firstDuplicate 0 (cycle x) empty

Complete solution: https://github.com/mgritter/aoc2018/blob/master/day1/day1.hs

Things I screwed up:

  • Trying to use Set instead of Set Int didn't complain, it just... did nothing?
  • I kept trying to use + to append lists (and strings) instead of ++
  • In GHCI (interactive) I could do sum map readInteger splitOn "\n" input or something close and right-associativity did everything I needed, I thought. This didn't work in the script version, probably because I was trying to print? I don't know, I need to understand the rules better, I seem to be using way more parentheses than experienced coders.
H2
H3
H4
3 columns
2 columns
1 column
Join the conversation now
Logo
Center