{-# Language QuasiQuotes, ImportQualifiedPost #-}
{-|
Module      : Main
Description : Day 1 solution
Copyright   : (c) Eric Mertens, 2018
License     : ISC
Maintainer  : emertens@gmail.com

<https://adventofcode.com/2018/day/1>

Day 1 gives us a list of differences to sum up. We compute the sum
of these differences, and we search for duplicates in the partial
sums of the differences list.

-}
module Main (main) where

import Advent (format, partialSums)
import Data.Maybe (fromJust)
import Data.Set qualified as Set

-- | Print the answers to the problem.
--
-- >>> :main
-- 474
-- 137041
main :: IO ()
IO ()
main =
  do [Integer]
inp <- [format|2018 1 ((%+|)%ld%n)*|]
     Integer -> IO ()
forall a. Show a => a -> IO ()
print ([Integer] -> Integer
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [Integer]
inp)
     Integer -> IO ()
forall a. Show a => a -> IO ()
print ([Integer] -> Integer
part2 [Integer]
inp)

-- | Given the list of differences, find the first partial sum
-- that repeats when we cycle the list of differences.
--
-- >>> part2 [1,-1]
-- 0
-- >>> part2 [3,3,4,-2,-4]
-- 10
-- >>> part2 [-6,3,8,5,-6]
-- 5
-- >>> part2 [7,7,-2,-7,-4]
-- 14
part2 :: [Integer] -> Integer
part2 :: [Integer] -> Integer
part2 = Maybe Integer -> Integer
forall a. HasCallStack => Maybe a -> a
fromJust (Maybe Integer -> Integer)
-> ([Integer] -> Maybe Integer) -> [Integer] -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Integer] -> Maybe Integer
forall a. Ord a => [a] -> Maybe a
firstDuplicate ([Integer] -> Maybe Integer)
-> ([Integer] -> [Integer]) -> [Integer] -> Maybe Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Integer] -> [Integer]
forall a. Num a => [a] -> [a]
partialSums ([Integer] -> [Integer])
-> ([Integer] -> [Integer]) -> [Integer] -> [Integer]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Integer] -> [Integer]
forall a. HasCallStack => [a] -> [a]
cycle

-- | Find the first duplicate element in a list.
firstDuplicate :: Ord a => [a] -> Maybe a
firstDuplicate :: forall a. Ord a => [a] -> Maybe a
firstDuplicate = Set a -> [a] -> Maybe a
forall {a}. Ord a => Set a -> [a] -> Maybe a
go Set a
forall a. Set a
Set.empty
  where
    go :: Set a -> [a] -> Maybe a
go Set a
_ [] = Maybe a
forall a. Maybe a
Nothing
    go Set a
seen (a
x:[a]
xs)
      | a
x a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
`Set.member` Set a
seen = a -> Maybe a
forall a. a -> Maybe a
Just a
x
      | Bool
otherwise           = Set a -> [a] -> Maybe a
go (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
Set.insert a
x Set a
seen) [a]
xs