2024-14 in haskell

4 files changed, 624 insertions, 0 deletions

diff --git a/2024/14-Restroom_Redoubt/example b/2024/14-Restroom_Redoubt/example
new file mode 100644
index 0000000..2455da4
--- /dev/null
+++ b/2024/14-Restroom_Redoubt/example
@@ -0,0 +1,12 @@
+p=0,4 v=3,-3
+p=6,3 v=-1,-3
+p=10,3 v=-1,2
+p=2,0 v=2,-1
+p=0,0 v=1,3
+p=3,0 v=-2,-2
+p=7,6 v=-1,-3
+p=3,0 v=-1,-2
+p=9,3 v=2,3
+p=7,3 v=-1,2
+p=2,4 v=2,-3
+p=9,5 v=-3,-3
diff --git a/2024/14-Restroom_Redoubt/first.hs b/2024/14-Restroom_Redoubt/first.hs
new file mode 100644
index 0000000..6518125
--- /dev/null
+++ b/2024/14-Restroom_Redoubt/first.hs
@@ -0,0 +1,58 @@
+-- requires cabal install --lib megaparsec parser-combinators heap vector
+module Main (main) where
+
+import           Control.Monad        (void, when)
+import qualified Data.List            as L
+import           Data.Void            (Void)
+import           Text.Megaparsec
+import           Text.Megaparsec.Char
+
+exampleExpectedOutput = 12
+
+type Pair = (Int, Int)
+type Robot = (Pair, Pair)
+type Input = [Robot]
+
+type Parser = Parsec Void String
+
+parseNumber :: Parser Int
+parseNumber = read <$> some (digitChar <|> char '-')
+
+parsePair :: Parser Pair
+parsePair = (,) <$> parseNumber <* char ','
+                <*> parseNumber
+
+parseRobot :: Parser Robot
+parseRobot = (,) <$> (string "p=" *> parsePair)
+                 <*> (string " v=" *> parsePair)
+
+parseInput' :: Parser Input
+parseInput' = some (parseRobot <* eol) <* eof
+
+parseInput :: String -> IO Input
+parseInput filename = do
+  input <- readFile filename
+  case runParser parseInput' filename input of
+    Left bundle  -> error $ errorBundlePretty bundle
+    Right input' -> return input'
+
+compute :: Int -> Int -> Input -> Int
+compute width height input = product $ L.foldl' safety [0, 0, 0, 0] input'
+  where
+    mx = width `div` 2
+    my = height `div` 2
+    input' = map step input
+    step ((x, y), (v, w)) = (((x + v * 100) `mod` width), ((y + w * 100) `mod` height))
+    safety acc@[a, b, c, d] (x, y) | x < mx && y < my = [a+1, b, c, d]
+                                   | x > mx && y < my = [a, b+1, c, d]
+                                   | x < mx && y > my = [a, b, c+1, d]
+                                   | x > mx && y > my = [a, b, c, d+1]
+                                   | otherwise = acc
+
+main :: IO ()
+main = do
+  example <- parseInput "example"
+  let exampleOutput = compute 11 7 example
+  when  (exampleOutput /= exampleExpectedOutput)  (error $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput)
+  input <- parseInput "input"
+  print $ compute 101 103 input
diff --git a/2024/14-Restroom_Redoubt/input b/2024/14-Restroom_Redoubt/input
new file mode 100644
index 0000000..c7d0438
--- /dev/null
+++ b/2024/14-Restroom_Redoubt/input
@@ -0,0 +1,500 @@
+p=46,91 v=80,-6
+p=89,91 v=-69,68
+p=61,39 v=-75,66
+p=8,63 v=48,-75
+p=58,76 v=-18,19
+p=99,14 v=-92,-85
+p=80,66 v=-3,-13
+p=15,1 v=-11,30
+p=52,79 v=93,81
+p=81,44 v=24,99
+p=6,41 v=-12,61
+p=40,14 v=-47,-85
+p=53,30 v=-52,-78
+p=2,53 v=-97,-33
+p=25,75 v=79,44
+p=77,17 v=-30,-21
+p=41,41 v=93,-99
+p=95,98 v=-49,43
+p=52,56 v=-88,-55
+p=99,20 v=-64,-53
+p=9,7 v=-56,-26
+p=18,0 v=87,-77
+p=90,95 v=-51,72
+p=25,81 v=20,-39
+p=94,79 v=-12,68
+p=58,88 v=-88,6
+p=31,99 v=-11,-85
+p=99,79 v=33,-46
+p=86,25 v=97,-17
+p=79,73 v=-35,-4
+p=20,52 v=17,63
+p=65,65 v=-98,-34
+p=34,31 v=33,-49
+p=14,21 v=17,54
+p=71,16 v=29,42
+p=63,53 v=-41,44
+p=59,78 v=-44,-92
+p=44,96 v=88,93
+p=88,70 v=-38,36
+p=78,78 v=16,11
+p=12,35 v=27,21
+p=45,77 v=-65,-10
+p=80,87 v=31,89
+p=31,2 v=-68,59
+p=24,64 v=-6,3
+p=28,34 v=54,-98
+p=99,61 v=-71,-21
+p=11,84 v=-37,60
+p=14,14 v=-68,-57
+p=97,12 v=-92,58
+p=25,69 v=39,-61
+p=72,34 v=60,-62
+p=15,84 v=-10,14
+p=96,57 v=-56,15
+p=76,55 v=-33,98
+p=23,97 v=56,60
+p=34,30 v=-68,76
+p=14,2 v=-68,22
+p=8,8 v=5,46
+p=16,38 v=-71,-21
+p=62,91 v=21,72
+p=67,75 v=-23,-96
+p=28,69 v=-79,31
+p=17,71 v=-81,36
+p=98,62 v=-43,-59
+p=61,92 v=-79,7
+p=55,26 v=-81,55
+p=97,18 v=66,-32
+p=93,33 v=92,-78
+p=29,53 v=54,70
+p=49,100 v=45,-43
+p=63,13 v=52,38
+p=13,49 v=9,-64
+p=73,37 v=46,7
+p=86,56 v=63,-50
+p=0,2 v=43,-61
+p=57,96 v=-96,74
+p=84,63 v=-66,-26
+p=25,94 v=-86,68
+p=6,72 v=82,40
+p=49,5 v=15,-20
+p=52,28 v=-28,-63
+p=17,99 v=56,-31
+p=42,85 v=13,44
+p=12,33 v=99,-19
+p=97,16 v=19,-69
+p=44,29 v=-99,-59
+p=30,15 v=36,-81
+p=58,42 v=-62,33
+p=32,36 v=28,-41
+p=34,97 v=-29,2
+p=21,61 v=86,-44
+p=27,94 v=-49,13
+p=60,74 v=-72,85
+p=32,81 v=-42,93
+p=46,37 v=37,16
+p=78,25 v=-49,-8
+p=72,76 v=-88,97
+p=21,59 v=-2,89
+p=1,16 v=-79,-24
+p=34,55 v=54,-50
+p=34,36 v=46,37
+p=99,29 v=-71,-42
+p=83,50 v=-24,19
+p=51,65 v=-12,13
+p=9,41 v=74,70
+p=38,34 v=-65,29
+p=8,22 v=-79,-66
+p=76,77 v=83,-13
+p=41,15 v=67,17
+p=46,51 v=85,78
+p=14,99 v=-33,39
+p=49,33 v=-93,-90
+p=5,102 v=74,-28
+p=27,7 v=22,37
+p=80,80 v=-87,-83
+p=21,73 v=-76,2
+p=59,63 v=-76,-91
+p=36,60 v=-34,-46
+p=84,89 v=99,-35
+p=53,89 v=24,-67
+p=17,57 v=39,31
+p=86,60 v=-11,-93
+p=58,5 v=11,49
+p=35,82 v=-91,-10
+p=8,38 v=-48,-74
+p=69,58 v=34,-38
+p=26,17 v=-94,-40
+p=66,77 v=-10,64
+p=18,7 v=-14,43
+p=67,71 v=78,11
+p=84,67 v=-7,-1
+p=67,54 v=-54,-38
+p=38,30 v=-83,82
+p=9,19 v=-4,-32
+p=34,61 v=-11,65
+p=8,60 v=-63,64
+p=11,45 v=-75,-29
+p=80,26 v=-92,20
+p=24,18 v=98,-73
+p=63,6 v=86,-53
+p=10,60 v=7,69
+p=76,47 v=34,-93
+p=98,9 v=-17,46
+p=65,19 v=11,-73
+p=54,51 v=-14,-67
+p=74,56 v=-82,40
+p=43,74 v=-78,19
+p=46,38 v=-83,62
+p=51,3 v=28,-19
+p=75,47 v=-8,85
+p=40,43 v=-94,-42
+p=99,48 v=27,-54
+p=16,55 v=-48,-62
+p=82,79 v=-34,58
+p=9,52 v=-53,12
+p=53,91 v=34,-48
+p=98,68 v=-17,-39
+p=30,38 v=-58,17
+p=95,87 v=36,-57
+p=97,43 v=-69,74
+p=70,46 v=65,41
+p=14,52 v=30,-21
+p=51,77 v=20,-47
+p=19,38 v=22,33
+p=32,22 v=96,17
+p=91,38 v=15,14
+p=13,98 v=43,80
+p=31,98 v=-1,59
+p=14,39 v=40,-29
+p=58,32 v=87,-89
+p=52,42 v=78,-21
+p=24,13 v=-97,-3
+p=23,26 v=33,-49
+p=6,10 v=-97,-77
+p=59,7 v=43,-47
+p=89,98 v=-30,6
+p=29,65 v=-3,-17
+p=85,95 v=94,72
+p=54,14 v=80,52
+p=85,83 v=-68,65
+p=60,22 v=-44,5
+p=91,67 v=-25,69
+p=90,81 v=-76,99
+p=22,92 v=-6,2
+p=37,59 v=-73,7
+p=37,37 v=-26,-46
+p=78,74 v=45,73
+p=94,57 v=38,-60
+p=62,88 v=-49,56
+p=62,29 v=96,37
+p=76,71 v=-3,-38
+p=6,94 v=-51,8
+p=95,64 v=95,50
+p=76,90 v=99,-93
+p=38,93 v=95,-23
+p=62,76 v=-62,60
+p=70,61 v=94,-18
+p=85,29 v=-61,50
+p=11,75 v=-27,56
+p=35,51 v=43,13
+p=14,74 v=61,52
+p=30,15 v=-55,-28
+p=18,69 v=-97,-58
+p=98,33 v=53,-70
+p=30,61 v=-45,-14
+p=77,102 v=16,-15
+p=93,87 v=92,83
+p=23,10 v=20,-98
+p=75,48 v=86,-9
+p=6,57 v=51,-48
+p=39,35 v=80,91
+p=84,70 v=63,81
+p=5,40 v=-44,-79
+p=38,81 v=2,52
+p=91,73 v=50,-55
+p=55,101 v=95,-22
+p=12,13 v=4,-73
+p=34,25 v=-39,-37
+p=80,5 v=-2,-44
+p=85,75 v=-54,65
+p=36,37 v=-47,-78
+p=7,18 v=79,92
+p=79,101 v=-59,-81
+p=15,42 v=43,74
+p=23,4 v=85,-64
+p=95,10 v=-95,30
+p=23,96 v=-94,88
+p=57,45 v=26,8
+p=63,37 v=-91,83
+p=73,0 v=-15,10
+p=44,3 v=-39,-52
+p=17,90 v=94,88
+p=63,65 v=17,21
+p=9,32 v=58,-66
+p=57,37 v=8,-5
+p=86,17 v=89,-65
+p=65,81 v=-26,73
+p=63,56 v=80,9
+p=69,33 v=29,-85
+p=81,0 v=-92,23
+p=97,44 v=45,-63
+p=42,85 v=-83,18
+p=36,90 v=12,79
+p=52,59 v=-75,-83
+p=25,72 v=76,83
+p=19,81 v=22,77
+p=31,35 v=-59,-38
+p=59,49 v=18,73
+p=52,24 v=31,-8
+p=65,34 v=-5,4
+p=69,95 v=-41,-93
+p=17,94 v=-19,-68
+p=90,99 v=-87,-85
+p=30,74 v=-94,-96
+p=13,40 v=2,13
+p=100,3 v=40,-77
+p=84,6 v=-72,21
+p=51,43 v=-26,74
+p=5,82 v=84,89
+p=28,63 v=90,-5
+p=28,17 v=90,-24
+p=98,70 v=40,23
+p=39,75 v=82,-19
+p=3,56 v=-35,-13
+p=46,8 v=-39,-40
+p=28,28 v=64,50
+p=25,70 v=54,31
+p=1,79 v=27,-47
+p=35,56 v=90,-5
+p=19,23 v=-58,46
+p=31,90 v=67,59
+p=30,53 v=-89,59
+p=56,23 v=-21,-73
+p=75,4 v=-72,-23
+p=48,1 v=88,-85
+p=37,13 v=36,51
+p=68,66 v=-41,-67
+p=29,2 v=64,-52
+p=16,57 v=17,32
+p=78,22 v=-10,-40
+p=36,52 v=-11,49
+p=25,43 v=95,-54
+p=11,62 v=87,95
+p=67,59 v=91,7
+p=30,20 v=77,54
+p=31,15 v=33,87
+p=75,37 v=72,73
+p=95,30 v=-50,38
+p=95,54 v=40,49
+p=42,93 v=38,85
+p=40,78 v=41,-60
+p=33,64 v=42,-48
+p=36,62 v=72,-55
+p=13,29 v=12,-65
+p=77,54 v=-10,-54
+p=67,70 v=96,-92
+p=4,39 v=-69,-9
+p=65,97 v=-47,-62
+p=40,97 v=26,41
+p=21,69 v=35,56
+p=100,4 v=-56,13
+p=19,57 v=88,-66
+p=93,96 v=13,-86
+p=14,37 v=-53,4
+p=55,58 v=-35,-79
+p=35,44 v=10,-27
+p=63,65 v=-36,-17
+p=69,8 v=60,67
+p=0,22 v=66,48
+p=13,47 v=-24,16
+p=66,17 v=-62,-98
+p=93,14 v=-51,1
+p=44,45 v=23,33
+p=92,10 v=63,-73
+p=47,81 v=54,-30
+p=64,43 v=90,-92
+p=0,23 v=14,4
+p=49,57 v=75,61
+p=80,42 v=-90,-21
+p=61,99 v=-5,-60
+p=61,98 v=93,-89
+p=79,7 v=-90,-7
+p=83,14 v=-20,-53
+p=22,72 v=17,35
+p=51,56 v=-69,-49
+p=76,13 v=25,2
+p=55,18 v=47,-3
+p=61,93 v=-15,51
+p=21,81 v=-45,-6
+p=84,42 v=-2,-5
+p=20,46 v=-1,57
+p=62,62 v=-75,65
+p=80,25 v=65,-20
+p=20,35 v=64,91
+p=78,25 v=68,-45
+p=50,21 v=-78,-57
+p=47,34 v=-83,-41
+p=19,33 v=43,-82
+p=42,99 v=-21,-97
+p=95,44 v=-90,-66
+p=39,62 v=60,-80
+p=49,87 v=18,93
+p=68,43 v=-83,-98
+p=36,64 v=-19,-67
+p=88,7 v=14,-77
+p=93,32 v=-12,-16
+p=59,78 v=-88,56
+p=17,87 v=2,-93
+p=39,90 v=-22,23
+p=58,41 v=-65,54
+p=100,47 v=-35,-91
+p=10,38 v=-27,74
+p=93,90 v=89,85
+p=37,64 v=54,77
+p=4,5 v=69,-61
+p=17,69 v=69,-1
+p=91,40 v=-56,-42
+p=12,33 v=22,97
+p=39,7 v=-57,-15
+p=50,25 v=-48,13
+p=37,60 v=-79,-47
+p=79,26 v=42,-57
+p=92,1 v=42,-60
+p=65,29 v=-23,-4
+p=41,26 v=75,8
+p=58,65 v=-83,86
+p=54,98 v=-19,36
+p=41,18 v=93,13
+p=3,81 v=-89,47
+p=70,95 v=-36,-1
+p=50,24 v=28,-91
+p=24,21 v=-19,-42
+p=64,20 v=62,62
+p=86,52 v=81,53
+p=28,24 v=7,-43
+p=2,63 v=-97,98
+p=91,55 v=14,-79
+p=52,92 v=83,31
+p=86,93 v=-38,-37
+p=70,52 v=12,99
+p=14,47 v=-48,23
+p=99,58 v=-61,-79
+p=20,19 v=74,33
+p=33,73 v=-41,80
+p=94,12 v=-43,84
+p=0,39 v=66,-60
+p=76,8 v=-41,-72
+p=15,99 v=-97,6
+p=13,24 v=93,-21
+p=88,96 v=32,-64
+p=98,29 v=-74,12
+p=20,79 v=48,14
+p=69,78 v=36,-66
+p=99,25 v=37,-33
+p=59,88 v=80,6
+p=45,47 v=-83,-25
+p=61,15 v=-31,-3
+p=83,71 v=-64,-14
+p=5,43 v=62,-75
+p=98,71 v=84,-10
+p=45,72 v=45,31
+p=23,34 v=-63,62
+p=44,101 v=-52,-57
+p=43,99 v=98,-80
+p=12,42 v=-71,-25
+p=74,99 v=16,-93
+p=36,19 v=15,42
+p=17,55 v=-22,81
+p=91,94 v=50,72
+p=81,42 v=11,-83
+p=39,33 v=-11,-39
+p=78,58 v=81,98
+p=62,94 v=-5,-96
+p=9,68 v=-21,-15
+p=54,84 v=-26,97
+p=67,45 v=97,9
+p=94,69 v=45,7
+p=13,18 v=-97,83
+p=33,53 v=67,12
+p=49,79 v=67,-22
+p=15,90 v=-32,-27
+p=89,54 v=50,28
+p=11,6 v=87,96
+p=89,58 v=19,-59
+p=95,1 v=27,-68
+p=5,71 v=-6,90
+p=36,71 v=-19,-67
+p=18,92 v=8,76
+p=25,23 v=18,-38
+p=81,36 v=-46,-25
+p=50,21 v=23,5
+p=41,67 v=-52,-44
+p=3,50 v=22,41
+p=67,47 v=93,23
+p=88,79 v=89,10
+p=27,35 v=-19,62
+p=37,1 v=15,22
+p=90,0 v=29,39
+p=74,22 v=-33,-57
+p=13,95 v=74,-15
+p=9,8 v=84,10
+p=78,87 v=52,18
+p=67,3 v=73,84
+p=30,97 v=76,60
+p=17,68 v=-65,7
+p=72,51 v=7,28
+p=85,69 v=-51,81
+p=18,98 v=95,-27
+p=62,48 v=-52,82
+p=37,5 v=-16,-69
+p=27,19 v=90,91
+p=95,76 v=-97,85
+p=55,89 v=-33,-33
+p=49,89 v=-39,-19
+p=79,76 v=-62,-8
+p=29,77 v=-24,97
+p=82,53 v=-51,86
+p=94,45 v=76,-99
+p=91,39 v=-35,-86
+p=10,51 v=-97,8
+p=10,45 v=52,-10
+p=100,17 v=17,22
+p=71,50 v=-50,-21
+p=10,66 v=-4,98
+p=53,13 v=-78,51
+p=0,92 v=-5,83
+p=70,59 v=-67,-5
+p=34,29 v=54,-86
+p=99,84 v=-71,-80
+p=37,21 v=72,-86
+p=98,16 v=69,57
+p=81,64 v=37,-10
+p=92,22 v=-74,-40
+p=27,78 v=51,-18
+p=99,63 v=-74,40
+p=35,36 v=40,10
+p=58,35 v=57,62
+p=57,33 v=-34,-53
+p=94,72 v=-12,56
+p=3,24 v=-49,-25
+p=53,87 v=-96,-22
+p=26,82 v=-37,48
+p=56,31 v=75,25
+p=72,99 v=1,82
+p=70,60 v=-92,15
+p=46,47 v=41,-99
+p=8,31 v=74,-66
+p=97,71 v=-74,-84
+p=8,91 v=4,-93
+p=62,20 v=42,17
+p=17,83 v=-9,-19
+p=18,82 v=-58,-63
+p=24,4 v=82,2
+p=42,59 v=-21,40
+p=94,86 v=-46,80
+p=58,62 v=5,-52
+p=77,6 v=73,30
+p=35,46 v=-78,-66
+p=44,59 v=7,-22
diff --git a/2024/14-Restroom_Redoubt/second.hs b/2024/14-Restroom_Redoubt/second.hs
new file mode 100644
index 0000000..cc23ce4
--- /dev/null
+++ b/2024/14-Restroom_Redoubt/second.hs
@@ -0,0 +1,54 @@
+-- requires cabal install --lib megaparsec parser-combinators heap vector
+module Main (main) where
+
+import           Control.Monad        (void, when)
+import qualified Data.List            as L
+import           Data.Void            (Void)
+import           Text.Megaparsec
+import           Text.Megaparsec.Char
+
+type Pair = (Int, Int)
+type Robot = (Pair, Pair)
+type Input = [Robot]
+
+type Parser = Parsec Void String
+
+parseNumber :: Parser Int
+parseNumber = read <$> some (digitChar <|> char '-')
+
+parsePair :: Parser Pair
+parsePair = (,) <$> parseNumber <* char ','
+                <*> parseNumber
+
+parseRobot :: Parser Robot
+parseRobot = (,) <$> (string "p=" *> parsePair)
+                 <*> (string " v=" *> parsePair)
+
+parseInput' :: Parser Input
+parseInput' = some (parseRobot <* eol) <* eof
+
+parseInput :: String -> IO Input
+parseInput filename = do
+  input <- readFile filename
+  case runParser parseInput' filename input of
+    Left bundle  -> error $ errorBundlePretty bundle
+    Right input' -> return input'
+
+compute :: Int -> Int -> Input -> Int -- the minimum safety score is the answer
+compute width height input = fst $ L.foldl' (\acc@(_, a) n@(_, b) -> if a > b then n else acc) (0, 1000000000) safeties
+  where
+    safeties = [(i, safety i)|i<-[0..width*height]]
+    mx = width `div` 2
+    my = height `div` 2
+    safety i = product $ L.foldl' score [0, 0, 0, 0] $ map (step i) input
+    step i ((x, y), (v, w)) = (((x + v * i) `mod` width), ((y + w * i) `mod` height))
+    score acc@[a, b, c, d] (x, y) | x < mx && y < my = [a+1, b, c, d]
+                                  | x > mx && y < my = [a, b+1, c, d]
+                                  | x < mx && y > my = [a, b, c+1, d]
+                                  | x > mx && y > my = [a, b, c, d+1]
+                                  | otherwise = acc
+
+main :: IO ()
+main = do
+  input <- parseInput "input"
+  print $ compute 101 103 input