Solution en Haskell

Ce problème ressemble à la partie 2 du jour 10 de cette année.

La première partie peut être aisément fait avec un parcours en largeur/profondeur mais ça devient clairement impossible pour la partie 2.

Remarquons que l'on cherche à trouver le nombre de sommets de coordonnées entières situées à l'intérieur d'un polygone.
On va donc de baser sur le théorème de Pick et la shoelace formula.
La shoelace formula est une formule pour calculer l'aire d'un polygone.
Si les sommets du polygone sont (x1, y1), ..., (xn, yn) alors l'aire du polygone est
|x1 y2 - y1 x2 + ... + x_{n-1} yn - y_{n-1} xn + xn y1 - yn x1| / 2

Le théorème de Pick donne une formule pour calculer le nombre de points intérieurs à un polygone à partir de son aire (qui est calculé par la shoelace formula) et du nombre de points à sa frontière (c'est juste la somme des distances données par les instructions).

La formule est la suivante: A = i + b/2 - 1 où A est l'aire, i le nombre de points à l'intérieur et b le nombre de points à la frontière.

Pour calculer le nombre de "#" total, il faut faire la somme i + b où i = A - b/2 - 1.

Donc, voici le code Haskell

data Direction = Up | Down | Left | Right
data Instr = Instr !Direction !Int
hexToInt :: String -> Int
hexToInt = foldl' (\acc x -> acc * 16 + hexDigitToInt x) 0
 where hexDigitToInt x
 | isDigit x = ord x - ord '0'
 | otherwise = ord x - ord 'a' + 10
parser :: Parser [(Instr, Instr)]
parser = instr `sepEndBy1` eol where
 instr = do
 dir1 <- direction <* " "
 len1 <- decimal <* " (#" 
 len2 <- hexToInt <$> count 5 hexDigitChar
 dir2 <- direction2 <* ")"
 pure (Instr dir1 len1, Instr dir2 len2)
 direction = choice [Up <$ "U", Down <$ "D", Left <$ "L", Right <$ "R"] 
 direction2 = choice [Right <$ "0", Down <$ "1", Left <$ "2", Up <$ "3"] 
trenchPoints :: [Instr] -> [V2 Int]
trenchPoints = scanl' go (V2 0 0) where
 go p (Instr dir len) = p + case dir of
 Left -> V2 0 (-len)
 Right -> V2 0 len
 Up -> V2 (-len) 0
 Down -> V2 len 0
-- return the double of the polygon area
shoelaceFormula :: [V2 Int] -> Int
shoelaceFormula points = abs $ sum (zipWith go points (drop 1 points ++ points))
 where go (V2 x y) (V2 x' y') = x * y' - x' * y
-- via Pick theorem and Shoelace Formula
-- https://en.wikipedia.org/wiki/Pick%27s_theorem
-- https://en.wikipedia.org/wiki/Shoelace_formula
solveFor :: ((Instr, Instr) -> Instr) -> [(Instr, Instr)] -> Int
solveFor f instrs = boundary + interior where
 instrs' = map f instrs
 doubleArea = shoelaceFormula (trenchPoints instrs')
 boundary = sum [len | Instr _ len <- instrs']
 interior = (doubleArea - boundary) `div` 2 + 1
solve :: Text -> IO ()
solve = aoc parser (solveFor fst) (solveFor snd)