aboutsummaryrefslogtreecommitdiff
path: root/2024/08-Resonant_Collinearity
diff options
context:
space:
mode:
authorJulien Dessaux2024-12-08 16:10:32 +0100
committerJulien Dessaux2024-12-08 16:10:32 +0100
commit3e098a4eed96c031d335644e4b30608058ebb000 (patch)
tree62e2b7d71985d127e63ce983de318f218cbe20d6 /2024/08-Resonant_Collinearity
parent2024-02 in factor (diff)
downloadadvent-of-code-3e098a4eed96c031d335644e4b30608058ebb000.tar.gz
advent-of-code-3e098a4eed96c031d335644e4b30608058ebb000.tar.bz2
advent-of-code-3e098a4eed96c031d335644e4b30608058ebb000.zip
2024-08 in haskell
Diffstat (limited to '2024/08-Resonant_Collinearity')
-rw-r--r--2024/08-Resonant_Collinearity/example12
-rw-r--r--2024/08-Resonant_Collinearity/first.hs57
-rw-r--r--2024/08-Resonant_Collinearity/input50
-rw-r--r--2024/08-Resonant_Collinearity/second.hs59
4 files changed, 178 insertions, 0 deletions
diff --git a/2024/08-Resonant_Collinearity/example b/2024/08-Resonant_Collinearity/example
new file mode 100644
index 0000000..78a1e91
--- /dev/null
+++ b/2024/08-Resonant_Collinearity/example
@@ -0,0 +1,12 @@
+............
+........0...
+.....0......
+.......0....
+....0.......
+......A.....
+............
+............
+........A...
+.........A..
+............
+............
diff --git a/2024/08-Resonant_Collinearity/first.hs b/2024/08-Resonant_Collinearity/first.hs
new file mode 100644
index 0000000..5c611ef
--- /dev/null
+++ b/2024/08-Resonant_Collinearity/first.hs
@@ -0,0 +1,57 @@
+-- requires cabal install --lib megaparsec parser-combinators heap vector
+module Main (main) where
+
+import Control.Monad (void, when)
+import qualified Data.Set as S
+import Data.Void (Void)
+import Text.Megaparsec
+import Text.Megaparsec.Char
+
+exampleExpectedOutput = 14
+
+data Antenna = Antenna Char Int Int deriving Show
+type Input = [Antenna]
+type Input' = (Int, Input)
+
+type Parser = Parsec Void String
+
+parseAntenna :: Parser Antenna
+parseAntenna = do
+ (SourcePos _ y x) <- getSourcePos
+ c <- alphaNumChar
+ pure $ Antenna c (unPos x - 1) (unPos y - 1)
+
+skipDots :: Parser ()
+skipDots = skipMany (char '.' <|> char '\n')
+
+parseInput' :: Parser Input
+parseInput' = some (skipDots *> parseAntenna <* skipDots) <* 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 (length (lines input), input')
+
+type Antinodes = S.Set (Int, Int)
+
+compute :: Input' -> Int
+compute (size, input) = S.size . S.filter valid $ compute' input S.empty
+ where
+ valid (x, y) = x >= 0 && x < size && y >= 0 && y < size
+ compute' :: Input -> Antinodes -> Antinodes
+ compute' [_] acc = acc
+ compute' (x:xs) acc = compute' xs . S.unions $ acc : map (antinodes x) xs
+ antinodes :: Antenna -> Antenna -> Antinodes
+ antinodes (Antenna c1 x1 y1) (Antenna c2 x2 y2) | c1 /= c2 = S.empty
+ | otherwise = let (dx, dy) = (x2 - x1, y2 - y1)
+ in S.fromList [(x1 - dx, y1 - dy) , (x2 + dx, y2 + dy)]
+
+main :: IO ()
+main = do
+ example <- parseInput "example"
+ let exampleOutput = compute example
+ when (exampleOutput /= exampleExpectedOutput) (error $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput)
+ input <- parseInput "input"
+ print $ compute input
diff --git a/2024/08-Resonant_Collinearity/input b/2024/08-Resonant_Collinearity/input
new file mode 100644
index 0000000..5b15221
--- /dev/null
+++ b/2024/08-Resonant_Collinearity/input
@@ -0,0 +1,50 @@
+...............e...........j6.....................
+.....1...............................t.....i......
+.....4.......3..............x..tL......m..........
+.......L.....................Dxj..................
+4....X..................F.....................m...
+.............4.......x....F........k..............
+......3...................t..........i.........Z..
+....L..................y.....F..e.....Z...........
+X.............1........C..........i...D...........
+........4.....................D.....k.X...m.......
+...1...............D........e......6..............
+...3.Y...................................m8.......
+..OL.........................x....Z....g..........
+....3......5.........................6j...........
+...................J..5r.F..k...y.................
+.......................................Z..a.......
+...........................5........j.........a.u.
+...p..............Y....X..........................
+...O.........................kd...................
+........................t.................i.......
+..................J..............u...........z....
+.O.....9.............J..............p..u..........
+.....9............................................
+l...6.....1........e......I................a......
+...................................az.............
+........M.......J...................gI....z.......
+.......Y...l...........p......g....d.......W......
+........5l....9................d.....g............
+.A....9.l.Y............I..............B.......s...
+..................................K.....B.........
+....M.............7.......8..........h.....K......
+.......0f...oc..............G...d7.......z...s..yW
+...M........0...........Gf.....................T..
+................r......G..................w....h..
+...........cP................G.8.R..............T.
+.................A.............N............u..B..
+..H.c..b............................K...CB.....y..
+......c...bP...2............7..K..................
+......b.o....0.......P.............s........h.R...
+......2........f..S........8.....................R
+U....2..............p..............7..............
+.HE..b......A.............N..............w....C...
+................................N.............w...
+.........E...........M................W.......T...
+......E...rS2...........W....................N....
+.....SP..n.....r..0...............................
+.....H..............A............................w
+..........n..U....................s...............
+..n.So.....U................f.....................
+Ho................................................
diff --git a/2024/08-Resonant_Collinearity/second.hs b/2024/08-Resonant_Collinearity/second.hs
new file mode 100644
index 0000000..06ef31a
--- /dev/null
+++ b/2024/08-Resonant_Collinearity/second.hs
@@ -0,0 +1,59 @@
+-- requires cabal install --lib megaparsec parser-combinators heap vector
+module Main (main) where
+
+import Control.Monad (void, when)
+import qualified Data.Set as S
+import Data.Void (Void)
+import Text.Megaparsec
+import Text.Megaparsec.Char
+
+exampleExpectedOutput = 34
+
+data Antenna = Antenna Char Int Int deriving Show
+type Input = [Antenna]
+type Input' = (Int, Input)
+
+type Parser = Parsec Void String
+
+parseAntenna :: Parser Antenna
+parseAntenna = do
+ (SourcePos _ y x) <- getSourcePos
+ c <- alphaNumChar
+ pure $ Antenna c (unPos x - 1) (unPos y - 1)
+
+skipDots :: Parser ()
+skipDots = skipMany (char '.' <|> char '\n')
+
+parseInput' :: Parser Input
+parseInput' = some (skipDots *> parseAntenna <* skipDots) <* 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 (length (lines input), input')
+
+type Antinodes = S.Set (Int, Int)
+
+compute :: Input' -> Int
+compute (size, input) = S.size $ compute' input S.empty
+ where
+ valid (x, y) = x >= 0 && x < size && y >= 0 && y < size
+ compute' :: Input -> Antinodes -> Antinodes
+ compute' [_] acc = acc
+ compute' (x:xs) acc = compute' xs . S.unions $ acc : map (antinodes x) xs
+ antinodes :: Antenna -> Antenna -> Antinodes
+ antinodes (Antenna c1 x1 y1) (Antenna c2 x2 y2) | c1 /= c2 = S.empty
+ | otherwise = let (dx, dy) = (x2 - x1, y2 - y1)
+ in S.fromList $ [(x1, y1), (x2, y2)]
+ ++ takeWhile valid [(x1 - i*dx, y1 - i*dy)|i<-[1..]]
+ ++ takeWhile valid [(x2 + i*dx, y2 + i*dy)|i<-[1..]]
+
+main :: IO ()
+main = do
+ example <- parseInput "example"
+ let exampleOutput = compute example
+ when (exampleOutput /= exampleExpectedOutput) (error $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput)
+ input <- parseInput "input"
+ print $ compute input