aboutsummaryrefslogtreecommitdiff
path: root/2020/15-Rambunctious_Recitation
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--2020/15-Rambunctious_Recitation/example1
-rw-r--r--2020/15-Rambunctious_Recitation/first.hs52
-rw-r--r--2020/15-Rambunctious_Recitation/input1
-rw-r--r--2020/15-Rambunctious_Recitation/second.hs52
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