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)