From cb296e77b94207b4a089207169bebb6850168b1e Mon Sep 17 00:00:00 2001 From: Julien Dessaux Date: Tue, 16 Jan 2024 01:21:20 +0100 Subject: 2023-16 part 1 in haskell --- 2023/16-The_Floor_Will_Be_Lava/example | 10 +++ 2023/16-The_Floor_Will_Be_Lava/first.hs | 116 ++++++++++++++++++++++++++++++++ 2023/16-The_Floor_Will_Be_Lava/input | 110 ++++++++++++++++++++++++++++++ 3 files changed, 236 insertions(+) create mode 100644 2023/16-The_Floor_Will_Be_Lava/example create mode 100644 2023/16-The_Floor_Will_Be_Lava/first.hs create mode 100644 2023/16-The_Floor_Will_Be_Lava/input (limited to '2023') diff --git a/2023/16-The_Floor_Will_Be_Lava/example b/2023/16-The_Floor_Will_Be_Lava/example new file mode 100644 index 0000000..d6805ce --- /dev/null +++ b/2023/16-The_Floor_Will_Be_Lava/example @@ -0,0 +1,10 @@ +.|...\.... +|.-.\..... +.....|-... +........|. +.......... +.........\ +..../.\\.. +.-.-/..|.. +.|....-|.\ +..//.|.... diff --git a/2023/16-The_Floor_Will_Be_Lava/first.hs b/2023/16-The_Floor_Will_Be_Lava/first.hs new file mode 100644 index 0000000..7824f92 --- /dev/null +++ b/2023/16-The_Floor_Will_Be_Lava/first.hs @@ -0,0 +1,116 @@ +-- requires cabal install --lib megaparsec parser-combinators +module Main (main) where + +import Control.Applicative.Permutations +import Control.Monad (void, when) +import Data.Char qualified as C +import Data.Either +import Data.Functor +import Data.List qualified as L +import Data.Map qualified as M +import Data.Maybe +import Data.Set qualified as S +import Data.Vector qualified as V +import qualified Data.Vector.Unboxed as VU +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char + +import Debug.Trace + +exampleExpectedOutput = 46 + +data Tile = Backslash | Empty | Horizontal | Slash | Vertical deriving Eq +instance Show Tile where + show Backslash = "\\" + show Empty = "." + show Horizontal = "-" + show Slash = "/" + show Vertical = "|" +type Line = V.Vector Tile +type Input = V.Vector Line + +type Parser = Parsec Void String + +parseTile :: Parser Tile +parseTile = char '\\' $> Backslash + <|> char '.' $> Empty + <|> char '-' $> Horizontal + <|> char '/' $> Slash + <|> char '|' $> Vertical + +parseLine :: Parser Line +parseLine = do + line <- some parseTile <* eol + return $ V.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' + +type LineOutput = VU.Vector Bool +type Output = V.Vector LineOutput +data Heading = N | S | E | W deriving (Eq, Ord, Show) +data Cursor = Cursor Int Int Heading deriving (Eq, Ord, Show) + +type Visited = M.Map Cursor () + +next :: Cursor -> Cursor +next (Cursor x y N) = Cursor x (y-1) N +next (Cursor x y S) = Cursor x (y+1) S +next (Cursor x y W) = Cursor (x-1) y W +next (Cursor x y E) = Cursor (x+1) y E + +compute :: Input -> Int +compute input = V.foldl' count 0 . fst $ walk startingOutput M.empty startingCursor + where + count :: Int -> LineOutput -> Int + count i l = i + VU.length (VU.filter id l) + size = V.length input + startingCursor = Cursor (-1) 0 E + startingOutput = V.replicate size $ VU.replicate size False + walk :: Output -> Visited -> Cursor -> (Output, Visited) + walk output v c | isNothing nextTile = (output, v) + | justNextTile == Empty = walk output' v c' + | visited = (output, v) + | justNextTile == Horizontal = if h == W || h == E then walk output' v c' + else let (output'', v'') = walk output' v' (Cursor x y E) in walk output'' v'' $ Cursor x y W + | justNextTile == Vertical = if h == N || h == S then walk output' v c' + else let (output'', v'') = walk output' v' (Cursor x y N) in walk output'' v'' $ Cursor x y S + | justNextTile == Backslash = case h of + N -> walk output' v' $ Cursor x y W + S -> walk output' v' $ Cursor x y E + W -> walk output' v' $ Cursor x y N + E -> walk output' v' $ Cursor x y S + | justNextTile == Slash = case h of + N -> walk output' v' $ Cursor x y E + S -> walk output' v' $ Cursor x y W + W -> walk output' v' $ Cursor x y S + E -> walk output' v' $ Cursor x y N + where + c'@(Cursor x y h) = next c + nextTile = case input V.!? y of + Just l -> l V.!? x + Nothing -> Nothing + justNextTile = fromJust nextTile + line = output V.! y + visited = M.member c' v + v' = M.insert c' () v + output' = if visited then output + else output V.// [(y, line VU.// [(x, True)])] + +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/2023/16-The_Floor_Will_Be_Lava/input b/2023/16-The_Floor_Will_Be_Lava/input new file mode 100644 index 0000000..2b0a13f --- /dev/null +++ b/2023/16-The_Floor_Will_Be_Lava/input @@ -0,0 +1,110 @@ +\..|...................|........\..............\.................-......./........./...\..........-......./... +........../...-/......\.|............../.................\...........\........-.........|.....\.-.|........... +...............-...........|......|...|......../.......\............../.................................../... +..................................|............../..|.|.../............./..\\........|...|..............\..|.. +...........................-...-...-.......................-.....-.-....\.......-............................/ +........-...|.......|./../......................./.........................\.................../.....\........ +\..\............-.\.........|../................................\....\......................./.............-.. +|\...|....\................\...|........\-..............|............\.........\.\..|.|....................... +.....\.........\......|...-...............................-.............-../.../..--......\.....\............. +................|...........................|..........\...........././.................../............../.... +.............................\......\.../..|................---................-......\....|...-............-. +..........|........./......\|...|.......|........\......\....-....\...-...../................/..-..../......-. +...|............./.................\../....|...\../.................|...|..|......|........................... +..................................-......../.....|............................................................ +...................-.............|...-.........../...........................-..............-...............|. +..-.............../.............................-......-.....-.............|-...../....................../.... +....||...../.........................................-...........................................--./-.......\ +...................\..........-......./..............|\........................../.-.|..............-..-/...|. +.-............-............../..-........../.......................\...-...||........./.-.....-....../........ +.......-.......-........................................../\\.......|......./../..\........\..-.........../../ +....../../.......................\.........\-....\.|..................\......................./...-\.......... +\.......-........\...-.....................\....-........./-...|......|.......-........................\...\.. +...|\.................................../..../..........|......-......../-..|......./..........\../..|......-\ +..........\...........................|..-........-/-......../....|...............................\.....|..... +..............\......-............................-.../........|........................./........-........... +.............-..\.//.....................-....-......|....../....-............................/..............| +\........../....|................./.....\......\.../.................|........\............../................ +.....-........-/|.........\.....-./............|...\.|......|.......|...................\\.....\.............- +................|.-...-.....................|..........-....\....\......../...............................././ +...........|.......\..............\......................................./........-.......................... +...........................-..../............|............................|...........\....................... +....................|..........|..................../...........\.....|.........-............\.\...-..\....... +................................-......-......\.....-/......\...\................/................-........... +..|.....\..\......|../....................................................\\......-...../..../..............// +.........\.................\..\..-.-..................\.....\..\.....\..........-............................. +...................\............/..\............|.............../..\............................|\.\...../.... +......|...............\.......|......|/........|....-.......|...........-.../.\....\.....|./.......|.......... +....\/|................-.-..........|.................../..............|../-...|/..........|.................. +..|........./-\.............|...|............|......\...................\..../.........|...............|.-.... +...................-................\....|/....-...|......./....../..........-|............/......\../..\\.... +...........................-..........................................-...|.|................\../...........-. +......../.....|.........-.......|........./-............|../.......|......-.-.-.......................-..|-... +.........|-...............|............./.....|........../..|........\..........|/.............../-........... +...\.....|..|...........\....-...\/.........................................|...................\......-.-.... +.../...-...|.............|.....\...|.................................../..............\.................../... +..........-.........../....|.....|..-.........../.................................-..................\....\/.. +....../..............\../......../.....-./....|../.\....-.................../............................../.\ +......-.|..........................\...............|.......-...-....../.............//...\|................/.. +................/.........|........................|......./..|......../-...........................\....|.... +........../...|.........\...........-./......\\...........\......|-......|...\...............\................ +../.........................|.................-/...........--.........\.../........................\.........\ +........\..|...|.............../...................-.........|.................\..|......./.........-.....-|.. +\.../.......|.............|-.../.................\...\..........\...|..........\....../......-................ +............|.|....\..--............-/-..................../........................-../..\..-................ +.....................................|.................../.................................|..../..-......\... +....|..............|..-.....|../.........................................|........\.................|......... +..............\..|...............\....||........../................................\................./.\...... +.....................-../......./....../.................................-............\........../............ +.....|.............../......-.\.|........-...................|.....-........\...-.............-....-.......-.. +..../.....|..............\../..............................\........|....................|..............\..... +....\................-........\../......|..../......................-.....|............../.../........../..... +....-...........................-.............|...........\..|........|.......\././.....|./..........\........ +/....................\..............\.............................-......................../\......../....-... +......\..................-............................................./.\...../.............\....-....\.\.... +..................................\-............................/.......|........................-|........... +.................../.../.......|./............\.........\....-.-....-../\.........|........./...\............. +......./.../....|...../|......................|.....|.....|.........|...........\......-.\..................|. +..././...........................|.......\.|......-........./................................................. +........|.|.......................-....................././.......||...........|/....-....\.......|......\/... +.\.\.....|....\......-....|...|.....//........|..-.........-.................-........./...................... +.|.....................\............-.................................|..../.............-....../.........../. +.|..\..../...............\..................../...\............................-....../................../.|.. +./.\............................/.............-...../-................\.........\.............|...../......... +..........\...............................\............../.........\.....-/........./|........................ +.............\..|....|..................................\.........|./......................\.........-........ +../.....|-............|...\................|...-....-........./........|.-..........\......................... +........-............./...........--................../...............................|..|.\....\............. +\.............-\.........................-|......|/.........\............/...........-.../.\........\..\.../.. +......................|........\....-../.............|......|.-...................................-|../...-... +.............|...|.....-...........|.....-...............|...\........................./..\....\.............. +..............|.............-.........../....-..................................|......./........|............ +...........|.-..../......................................\....-...\-......../........-..........-......-.....| +../...........-............-.../|...........-.-.............\.............................|.............-..... +.........../...-............../........./...................................../......-.......\\............... +........................./.||......|...../.......|....|..................-..........|......\.................. +............/....-./..-...........|...-..........\....../...\/.......|\.....\....|........../..\.\............ +.......................................-.../.......|............|........|...\..........\.....-............... +/..\|.............-...-.................................\........\...................\......|....-............ +..................\............../........................./.........|..........\...\......\..........|......| +.../.................................................../...|............../....\...\...../........|.......-... +..................-.-..........................\.................-......................-..\.........-........ +...................../\.....\.............\.............../................\.|............../........./....... +....................|../.\./......................................-.../.......\............................... +|........................-..............................................|...............................-..... +....\.\...........\......|.........\/|..|....|.....\............-...../.............................\\........ +......\....|......\|.....-..................\........\.......................-............-.|..............|.. +....|.....././.......................|......../...........-.|............./......-.|....../.....\......|....\. +.........\........|.......\..........|........./..................\.........................|................- +.....\..........\.....-......../...|-........../...\/|........................................................ +.../.....................\../.........\.|.........-..........\...............................|...............\ +.........-...........................................-.|...........\......//............../..|.\............/. +.-|../...../.........|............./..........................|..-.\......\............\................../... +../....../.................|..............\.........|.\......\...../.......\............\./.......|....../..\. +......../.-..-......\.........................\|...................................-....../................... +......................-....|........./\................|......\..-\....../.......\.................\/.-\...... +............\...|...............|............./...........................................\....-.-............ +\.........|.............................|............/.........-.....\........\|...-..-..\/.../......./....... +.............................\.|...............\....\..\-.....................\......-...../......\..../.....\ +..\-......\.\........-........../........\...............\..................../....-....\.\.|.|............... +................|./........../.................................-.............|...................\............ -- cgit v1.2.3