diff options
Diffstat (limited to '2020/9.hs')
-rw-r--r-- | 2020/9.hs | 40 |
1 files changed, 40 insertions, 0 deletions
diff --git a/2020/9.hs b/2020/9.hs new file mode 100644 index 0000000..d593681 --- /dev/null +++ b/2020/9.hs @@ -0,0 +1,40 @@ +module Main where + +import Data.List (find) +import Data.Maybe (fromJust) +import qualified Data.Set as Set +import qualified Data.Map.Strict as Map +import Data.Map.Strict (Map) + +import Input + + +preludeLen :: Int +preludeLen = 25 + +findRun :: Int -> [Int] -> (Int, Int) +findRun target input = go input 0 0 mempty + where + go :: [Int] -> Int -> Int -> Map Int Int -> (Int, Int) + go (x:xs) index beforeTotal prevs + | Just index' <- Map.lookup (beforeTotal + x - target) prevs + , index - index' >= 2 + = (index', index) + | otherwise + = go xs (index + 1) (beforeTotal + x) (Map.insert (beforeTotal + x) index prevs) + go [] _ _ _ = error "Run not found" + +main :: IO () +main = do + input <- map read <$> getInput 9 :: IO [Int] + let (prelude, rest) = splitAt preludeLen input + sets = scanl (\s (i1, i2) -> Set.insert i2 (Set.delete i1 s)) + (Set.fromList prelude) + (zip input rest) + isValid s i = any (`Set.member` s) [i - n | n <- Set.toList s, n /= i - n] + weakness = snd (fromJust (find (not . uncurry isValid) (zip sets rest))) + print weakness + + let (index1, index2) = findRun weakness input + run = drop (index1 + 1) (take index2 input) + print (minimum run + maximum run) |