From 3ca5033e1ddd578dd5c6a3b0e8488751c879f10b Mon Sep 17 00:00:00 2001
From: Tom Smeding <tom.smeding@gmail.com>
Date: Sun, 13 Dec 2020 20:43:59 +0100
Subject: Day 9

---
 2020/9.hs | 40 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 40 insertions(+)
 create mode 100644 2020/9.hs

(limited to '2020/9.hs')

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)
-- 
cgit v1.2.3-54-g00ecf