2020-15 in haskell

4 files changed, 106 insertions, 0 deletions

diff --git a/2020/15-Rambunctious_Recitation/example b/2020/15-Rambunctious_Recitation/example
new file mode 100644
index 0000000..c84ffe7
--- /dev/null
+++ b/2020/15-Rambunctious_Recitation/example
@@ -0,0 +1 @@
+0,3,6
diff --git a/2020/15-Rambunctious_Recitation/first.hs b/2020/15-Rambunctious_Recitation/first.hs
new file mode 100644
index 0000000..65bfbec
--- /dev/null
+++ b/2020/15-Rambunctious_Recitation/first.hs
@@ -0,0 +1,52 @@
+-- requires cabal install --lib megaparsec parser-combinators
+module Main (main) where
+import Control.Monad (void, when)
+import Data.List (foldl')
+import Data.Map qualified as M
+import Data.Void (Void)
+import Text.Megaparsec
+import Text.Megaparsec.Char
+import System.Exit (die)
+
+exampleExpectedOutput = 436
+
+type Input = [Int]
+
+type Parser = Parsec Void String
+
+parseInt :: Parser Int
+parseInt = do
+  n <- some digitChar
+  void $ optional (char ',')
+  return $ read n
+
+parseOps :: Parser Input
+parseOps = some parseInt <* char '\n' <* eof
+
+parseInput :: String -> IO Input
+parseInput filename = do
+  input <- readFile filename
+  case runParser parseOps filename input of
+    Left bundle -> die $ errorBundlePretty bundle
+    Right ops -> return ops
+
+compute :: Input -> Int
+compute input = compute'  (length input)  (foldl' prepare M.empty $ zip (init input) [1..])  (last input)
+  where
+    compute' :: Int -> M.Map Int (Int, Int) -> Int -> Int
+    compute' 2020 _ n = n
+    compute' t m n = case M.lookup n m of
+      Just (t', i) -> compute'  (t+1)  (M.insert n (t, i+1) m)  (t - t')
+      Nothing -> compute'  (t+1)  (M.insert n (t, 0) m)  0
+    prepare :: M.Map Int (Int, Int) -> (Int, Int) -> M.Map Int (Int, Int)
+    prepare acc (n, t) = case M.lookup n acc of
+      Just (_, i) -> M.insert n (t, i+1) acc
+      Nothing -> M.insert n (t, 0) acc
+
+main :: IO ()
+main = do
+  example <- parseInput "example"
+  let exampleOutput = compute example
+  when  (exampleOutput /= exampleExpectedOutput)  (die $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput)
+  input <- parseInput "input"
+  print $ compute input
diff --git a/2020/15-Rambunctious_Recitation/input b/2020/15-Rambunctious_Recitation/input
new file mode 100644
index 0000000..909319b
--- /dev/null
+++ b/2020/15-Rambunctious_Recitation/input
@@ -0,0 +1 @@
+19,20,14,0,9,1
diff --git a/2020/15-Rambunctious_Recitation/second.hs b/2020/15-Rambunctious_Recitation/second.hs
new file mode 100644
index 0000000..eeac0d8
--- /dev/null
+++ b/2020/15-Rambunctious_Recitation/second.hs
@@ -0,0 +1,52 @@
+-- requires cabal install --lib megaparsec parser-combinators
+module Main (main) where
+import Control.Monad (void, when)
+import Data.List (foldl')
+import Data.Map qualified as M
+import Data.Void (Void)
+import Text.Megaparsec
+import Text.Megaparsec.Char
+import System.Exit (die)
+
+exampleExpectedOutput = 175594
+
+type Input = [Int]
+
+type Parser = Parsec Void String
+
+parseInt :: Parser Int
+parseInt = do
+  n <- some digitChar
+  void $ optional (char ',')
+  return $ read n
+
+parseOps :: Parser Input
+parseOps = some parseInt <* char '\n' <* eof
+
+parseInput :: String -> IO Input
+parseInput filename = do
+  input <- readFile filename
+  case runParser parseOps filename input of
+    Left bundle -> die $ errorBundlePretty bundle
+    Right ops -> return ops
+
+compute :: Input -> Int
+compute input = compute'  (length input)  (foldl' prepare M.empty $ zip (init input) [1..])  (last input)
+  where
+    compute' :: Int -> M.Map Int (Int, Int) -> Int -> Int
+    compute' 30_000_000 _ n = n
+    compute' t m n = case M.lookup n m of
+      Just (t', i) -> compute'  (t+1)  (M.insert n (t, i+1) m)  (t - t')
+      Nothing -> compute'  (t+1)  (M.insert n (t, 0) m)  0
+    prepare :: M.Map Int (Int, Int) -> (Int, Int) -> M.Map Int (Int, Int)
+    prepare acc (n, t) = case M.lookup n acc of
+      Just (_, i) -> M.insert n (t, i+1) acc
+      Nothing -> M.insert n (t, 0) acc
+
+main :: IO ()
+main = do
+  example <- parseInput "example"
+  let exampleOutput = compute example
+  when  (exampleOutput /= exampleExpectedOutput)  (die $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput)
+  input <- parseInput "input"
+  print $ compute input