diff options
Diffstat (limited to '2024/10-Hoof_It')
-rw-r--r-- | 2024/10-Hoof_It/example | 8 | ||||
-rw-r--r-- | 2024/10-Hoof_It/first.hs | 64 | ||||
-rw-r--r-- | 2024/10-Hoof_It/input | 40 | ||||
-rw-r--r-- | 2024/10-Hoof_It/second.hs | 63 |
4 files changed, 175 insertions, 0 deletions
diff --git a/2024/10-Hoof_It/example b/2024/10-Hoof_It/example new file mode 100644 index 0000000..cada9b3 --- /dev/null +++ b/2024/10-Hoof_It/example @@ -0,0 +1,8 @@ +89010123 +78121874 +87430965 +96549874 +45678903 +32019012 +01329801 +10456732 diff --git a/2024/10-Hoof_It/first.hs b/2024/10-Hoof_It/first.hs new file mode 100644 index 0000000..878a30a --- /dev/null +++ b/2024/10-Hoof_It/first.hs @@ -0,0 +1,64 @@ +-- 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 qualified Data.Vector as V +import qualified Data.Vector.Unboxed as VU +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char + +exampleExpectedOutput = 36 + +type Line = VU.Vector Int +type Input = V.Vector Line + +type Parser = Parsec Void String + +parseNumber :: Parser Int +parseNumber = read . pure <$> digitChar + +parseLine :: Parser Line +parseLine = do + line <- some parseNumber <* eol + return $ VU.generate (length line) (line !!) + +parseInput' :: Parser Input +parseInput' = do + line <- some parseLine <* eof + return $ V.generate (length line) (line !!) + +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 :: Input -> Int +compute input = sum $ V.imap scoreLine input + where + scoreLine :: Int -> VU.Vector Int -> Int + scoreLine y line = VU.sum $ VU.imap (\x c -> score x y c) line + score :: Int -> Int -> Int -> Int + score x y c | c == 0 = S.size $ reachableSummits 0 (x, y) + | otherwise = 0 + reachableSummits :: Int -> (Int, Int) -> S.Set (Int, Int) + reachableSummits h (x, y) | h == 9 = S.singleton (x, y) + | otherwise = S.unions $ map (reachableSummits (h+1)) succ + where + succ = filter valid [(x-1, y), (x+1, y), (x, y-1), (x, y+1)] + valid (x, y) = case input V.!? y of + Just line -> case line VU.!? x of + Just h' -> h+1 == h' + _ -> False + _ -> False + +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/10-Hoof_It/input b/2024/10-Hoof_It/input new file mode 100644 index 0000000..800a18c --- /dev/null +++ b/2024/10-Hoof_It/input @@ -0,0 +1,40 @@ +1098921121187650126589432104301010017898 +2347810030090543237676546765218921326323 +3256723345121789078545345896237635495410 +0189654656230650129454210910146546786898 +1018706787649843212323407893056544576781 +0123215498556764501012216324567033675410 +1054912389440189650983345413498122189323 +2367804322339218761874214102439232075014 +3494565011878307010965302101521001456985 +4583876910965498123434456517617652327876 +9672978894328767894525467898908543410434 +8701569765419456987616321010119654306523 +7616054100300345865407890121236701217810 +4567123231201210870301456290547896332912 +3258834998303456961210387787678987441003 +4109985867214327898341295689432196556764 +3457876754321016987654254776501001105895 +2568965698130123216510163897567232234996 +1077654147010154105425672198498143497887 +2089503056923269012334789010398056786546 +1123412147874678901109011001267049805430 +0109892130965165210278921123452121012321 +1236783021089014321367630038983430328901 +0345634569870156752456541127604589437610 +1267825478763247843898430934510678576523 +3216910089654130956707321874321987689430 +4505432198703021013210012365899654238321 +3699801789012982787309898456718723148980 +2789789678101276896456721032100210057671 +1008650521010345785454434549321321060362 +2210541430121289890365410678732639871250 +4341232510537656701274320521548747898341 +1056341423498545432789201230699656743432 +2967650345567230101687112345788745234569 +3878981236750121211096001296787230199678 +4589870109889032349125410187590123288767 +5679665010976541498934231095691054177678 +3038754129889650587432145654782567065549 +2125603236778765676501098723123478450030 +3034512345654656565410181010010989321121 diff --git a/2024/10-Hoof_It/second.hs b/2024/10-Hoof_It/second.hs new file mode 100644 index 0000000..91cff42 --- /dev/null +++ b/2024/10-Hoof_It/second.hs @@ -0,0 +1,63 @@ +-- requires cabal install --lib megaparsec parser-combinators heap vector +module Main (main) where + +import Control.Monad (void, when) +import qualified Data.Vector as V +import qualified Data.Vector.Unboxed as VU +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char + +exampleExpectedOutput = 81 + +type Line = VU.Vector Int +type Input = V.Vector Line + +type Parser = Parsec Void String + +parseNumber :: Parser Int +parseNumber = read . pure <$> digitChar + +parseLine :: Parser Line +parseLine = do + line <- some parseNumber <* eol + return $ VU.generate (length line) (line !!) + +parseInput' :: Parser Input +parseInput' = do + line <- some parseLine <* eof + return $ V.generate (length line) (line !!) + +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 :: Input -> Int +compute input = sum $ V.imap scoreLine input + where + scoreLine :: Int -> VU.Vector Int -> Int + scoreLine y line = VU.sum $ VU.imap (\x c -> score x y c) line + score :: Int -> Int -> Int -> Int + score x y c | c == 0 = length $ reachableSummits 0 (x, y) + | otherwise = 0 + reachableSummits :: Int -> (Int, Int) -> [(Int, Int)] + reachableSummits h (x, y) | h == 9 = [(x, y)] + | otherwise = concatMap (reachableSummits (h+1)) succ + where + succ = filter valid [(x-1, y), (x+1, y), (x, y-1), (x, y+1)] + valid (x, y) = case input V.!? y of + Just line -> case line VU.!? x of + Just h' -> h+1 == h' + _ -> False + _ -> False + +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 |