Advent of Code 2018 day 1 part 2: find the first repeated number after some increases and decreases

Question

Here is the problem:

Part Two

You notice that the device repeats the same frequency change list over and over. To calibrate the device, you need to find the first frequency it reaches twice.

For example, using the same list of changes above, the device would loop as follows:

Current frequency 0, change of +1; resulting frequency 1.

Current frequency 1, change of -2; resulting frequency -1.

Current frequency -1, change of +3; resulting frequency 2.

Current frequency 2, change of +1; resulting frequency 3.

(At this point, the device continues from the start of the list.)

Current frequency 3, change of +1; resulting frequency 4.

Current frequency 4, change of -2; resulting frequency 2, which has already been seen.

In this example, the first frequency reached twice is 2. 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.

Here are other examples:

+1, -1 first reaches 0 twice.

+3, +3, +4, -2, -4 first reaches 10 twice.

-6, +3, +8, +5, -6 first reaches 5 twice.

+7, +7, -2, -7, -4 first reaches 14 twice.

What is the first frequency your device reaches twice?

And here is my solution:

module Main where

import           Data.List.Split

parseString :: Integer -> String -> Integer
parseString acc s =
  let num = read $ tail s :: Integer
      operator = head s
  in if operator == '+'
       then acc + num
       else acc - num

findFreq :: Integer -> [Integer] -> [String] -> (Integer, Integer, [Integer])
findFreq curr acc [] = (0, curr, acc)
findFreq curr acc (x:xs) =
  let next = parseString curr x
  in if next `elem` acc
       then (next, 0, [])
       else let f = acc ++ [next]
            in findFreq next f xs

findRepeatingFrequency :: Integer -> [Integer] -> [String] -> Integer
findRepeatingFrequency init nums xs =
  let (found, acc, lst) = findFreq init nums xs
  in if found > 0
       then found
       else findRepeatingFrequency acc lst xs

main :: IO ()
main = do
  file <- readFile "input.txt"
  let input = filter (not . null) $ splitOn "\n" file
  print (findRepeatingFrequency 0 [] input)

This is seriously slow.

Can anyone give me pointes as to how this can be done better?

I'm also keen to know specifically why this is so slow.

Answer 1

Small things

Data.List.Split

I don't see the need for this module. I see what you're going for with splitOn "\n", however Haskell has a function in Prelude called lines:

words :: String -> [String]

Prelude> lines "test\nphrase, please\nignore"
["test","phrase, please","ignore"]

parseString

I think it's cleaner to instead first parse your input into an Integer format and then use [Integer] everywhere instead of [String]. This simplifies your parsing and also gives you a more general function. Note that my implementation is a partial function.

parseInt :: String -> Integer
parseInt (op:s) =
  case op of
    '+' -> read s
    '-' -> (-1) * read s
    -- There is a hole here: this will error if 'op'
    -- (the first character) isn't '+' or '-'

Return values

The type of findFreq is

findFreq :: Integer -> [Integer] -> [String] -> (Integer, Integer, [Integer])

I see no reason why it can't return a single Integer. Perhaps you returned all values to debug initially, but once that's done you should switch back.

It also seems to me like you were using 0 as an "error value," which is appropriate in other languages but generally frowned upon in Haskell. In this case, you can instead use Maybe to indicate failure and change your type signature to

findFreq :: Integer -> [Integer] -> [String] -> Maybe Integer

Like I mention later, this isn't necessary since we can condense and fix some logic, but I would recommend using Maybe instead in the future.

curr and acc

You do some switching around with your variables curr and acc which confused me a bit. I'd keep acc as the accumulation value for your frequency everywhere and call the list of visited values something like seenFreqs or prevFreqs.

Correctness

Repeating frequencies of 0

Your code currently assumes the repeated frequency is the first nonzero repeated frequency. Thus, it fails for the +1, -1 test case. You could change the code to

findRepeatingFrequency :: Integer -> [Integer] -> [String] -> Integer
findRepeatingFrequency init nums xs =
  let (found, acc, lst) = findFreq init nums xs
  in found

to accommodate that.

This breaks your way of going through the list again if you don't find a repeat the first time, but fortunately there's a less obfuscated way to avoid your checking and continue: you can use cycle, which creates an infinite list consisting of the input list repeated infinitely.

cycle :: [a] -> [a]

Prelude> take 20 $ cycle [1,2,3,4]
[1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4]

You can call findRepeatingFrequency on cycle input to prevent having to do the cycling yourself in the function.

Efficiency

Things go wrong for efficiency in findFreq. There are two problem points that make your code asymptotically inefficient.

First, in the following line

  in if next `elem` acc

elem is an O(n) operation. You're calling it for each of the n elements in your input list, meaning that your function is at least O(n^2) (and it turns out that this is the final complexity).

I checked the number of iterations required for my sample input and it took 142991 iterations to find a repeated frequency. An O(n^2) runtime is going to require about 10 billion iterations for the lookups alone. Ouch.

Second is a more insidious mistake that is easy to overlook. In this line,

   else let f = acc ++ [next]

Appending to a list is an O(n) operation. Lists in Haskell are implemented as linked lists, and appending to the back of one cannot be amortized to O(1) like one might in Python's list or Java's ArrayList. You need to travel all the way to the back to add in a link.

Fixing the second issue actually isn't very hard since you don't care about the ordering of the list. You can switch it to

   else let f = next : acc

to return to O(1) inserts.

Fixing the lookups, however, requires a change of data structure.

Introducing Data.Set

Data.Set provides unordered sets with O(log n) lookup and insert time. Yeah, it's O(log n), but the total runtime for me when I checked the implementation was less than a second.

I'm including a sample implementation of day 1 below that I've tested and confirmed on my inputs if you want to compare. However, you said you wanted pointers, so here's the pointers I'll give.

• You can keep your code mostly the same (although I'd recommend making the style changes I suggested)
• You will want to use two functions from Data.Set: member and insert.
• Your end result will look a lot like a fold but with some differences in end conditions (kind of like findFreq)

Sample implmentation

Finally, here's a sample implementation.

module Main where

import Data.Set (Set)
import qualified Data.Set as S

-- This is a partial function
parseInt :: String -> Integer
parseInt (op:s) =
  case op of
    '+' -> read s
    '-' -> (-1) * read s
    -- There is a hole here, assuming valid input

findRepeatingFrequency :: Integer -> Set Integer -> [Integer] -> Integer
findRepeatingFrequency acc seen (x:xs) =
  if acc `S.member` seen
     then acc
     else findRepeatingFrequency (acc + x) (S.insert acc seen) xs

partOne :: [Integer] -> Integer
partOne = sum

partTwo :: [Integer] -> Integer
partTwo ints = findRepeatingFrequency 0 S.empty $ cycle ints

main :: IO ()
main = do
  file <- readFile "input.txt"
  let input = filter (not . null) $ words file
  let ints = map parseInt input
  print $ partOne ints
  print $ partTwo ints