Advent of Code 2023 day 18

Day 18 was a challenge of two halves, but I don't mean the normal part 1 — part 2 split. First I'll talk about parsing the input, then I'll talk about solving the area-calculation problem.

Data and parsing

The data structures for this problem were simple, and direct translations from the specification. A Direction has one of four values; an Instruction is a direction and a distance; a Position is an x–y pair.

data Direction = U | D | L | R deriving (Show, Eq, Ord)
data Instruction = Instr Direction Int deriving (Show, Eq, Ord)

type Position = V2 Int -- x, y

Parsing for part 1 follows the data structure, while ignoring the hexadecimal colour code.

instructions1P = instruction1P `sepBy` endOfLine
instruction1P = Instr <$> (direction1P <* " ") 
                      <*> (decimal <* " ") 
                      <*  (skipWhile (not . isSpace))

direction1P = choice [ U <$ "U"
                     , D <$ "D"
                     , L <$ "L"
                     , R <$ "R"
                     ]

Parsing for part 2 is a bit more fiddly. I couldn't find an easy way to apply a parser to the result of another parser, so the conversion of the hex-digit string to a number was handled by the Data.Text.Read library.

instructions2P = instruction2P `sepBy` endOfLine

instruction2P = 
  instrify <$> (preambleP *> (AT.take 5)) <*> (direction2P <* ")")

preambleP = (direction1P *> " " *> decimal <* " (#")

instrify :: Text -> Direction -> Instruction
instrify h d = Instr d (fst $ fromRight (0, "") $ TR.hexadecimal h)

direction2P = choice [ U <$ "3"
                     , D <$ "1"
                     , L <$ "2"
                     , R <$ "0"
                     ]

Calculating the area

The complication here was that the trench had a non-zero width, which made the area calculation a bit more complex. I admit, I looked here for the answer: it's a combination of the shoelace formula (for finding the base area) and Pick's theorem (for the correction of adding some of the perimeter). It's the same code for both parts of the puzzle.

area :: [Instruction] -> Int
area instrs = (shoelace $ mkTrench instrs) + ((perimeter instrs) `div` 2) + 1

shoelace :: [Position] -> Int
shoelace ps = (abs $ sum $ zipWith mulPair ps $ tail ps) `div` 2
  where mulPair (V2 x1 y1) (V2 x2 y2) = x1 * y2 - x2 * y1

perimeter :: [Instruction] -> Int
perimeter = sum . fmap (\(Instr _ len) -> len)

mkTrench :: [Instruction] -> [Position]
mkTrench = scanl' move (V2 0 0)
  where move here (Instr dir len) = here ^+^ (delta dir ^* len)

delta :: Direction -> V2 Int
delta U = V2 0 1
delta D = V2 0 (-1)
delta L = V2 (-1) 0
delta R = V2 1 0

Code

You can get the code from my locally-hosted Git repo, or from Gitlab.