diff options
| -rw-r--r-- | 2024/08-Resonant_Collinearity/example | 12 | ||||
| -rw-r--r-- | 2024/08-Resonant_Collinearity/first.hs | 57 | ||||
| -rw-r--r-- | 2024/08-Resonant_Collinearity/input | 50 | ||||
| -rw-r--r-- | 2024/08-Resonant_Collinearity/second.hs | 59 |
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 |