advent05/Main.hs

   1 -- Writeup at https://work.njae.me.uk/2021/12/04/advent-of-code-2021-day-4/
   2
   3 import Data.Text ()
   4 import qualified Data.Text.IO as TIO
   5
   6 import Data.Attoparsec.Text hiding (take)
   7 import Control.Applicative
   8
   9 import qualified Data.Map.Strict as M
  10 import Linear (V2(..), (^+^))
  11
  12
  13 type Point = V2 Int
  14 type Grid = M.Map Point Int
  15
  16 data Line = Line Point Point deriving (Eq, Show)
  17
  18
  19 main :: IO ()
  20 main =
  21   do  text <- TIO.readFile "data/advent05.txt"
  22       let trace = successfulParse text
  23       print $ part1 trace
  24       print $ part2 trace
  25
  26 part1 trace = M.size $ M.filter (> 1) diagram
  27   where hvLines = map expandLine $ filter isHorizOrVert trace
  28         diagram = addLines M.empty hvLines
  29
  30 part2 trace = M.size $ M.filter (> 1) diagram
  31   where allLines = map expandLine trace
  32         diagram = addLines M.empty allLines
  33
  34
  35 isHoriz :: Line -> Bool
  36 isHoriz (Line (V2 x0 _y0) (V2 x1 _y1)) = x0 == x1
  37
  38 isVert :: Line -> Bool
  39 isVert (Line (V2 _x0 y0) (V2 _x1 y1)) = y0 == y1
  40
  41 isHorizOrVert :: Line -> Bool
  42 isHorizOrVert line = (isHoriz line) || (isVert line)
  43
  44 expandLine :: Line -> [Point]
  45 expandLine line@(Line p0 _p1) = take numPoints $ iterate (^+^ delta) p0
  46   where numPoints = findLen line + 1
  47         delta = findDelta line
  48
  49 findLen :: Line -> Int
  50 findLen (Line (V2 x0 y0) (V2 x1 y1)) =
  51   max (abs (x1 - x0)) (abs (y1 - y0))
  52
  53 findDelta :: Line -> Point
  54 findDelta (Line (V2 x0 y0) (V2 x1 y1)) = (V2 dx dy)
  55   where dx = signum (x1 - x0)
  56         dy = signum (y1 - y0)
  57
  58 addLines :: Grid -> [[Point]] -> Grid
  59 addLines = foldr insertLine
  60   where insertPoint p d = M.insertWith (+) p 1 d
  61         insertLine l d = foldr insertPoint d l
  62
  63
  64 -- Parse the input file
  65
  66 traceP = lineP `sepBy` endOfLine
  67 lineP = Line <$> (pointP <* " -> ") <*> pointP
  68 pointP = V2 <$> (decimal <* ",") <*> decimal
  69
  70 -- successfulParse :: Text -> (Integer, [Maybe Integer])
  71 successfulParse input =
  72   case parseOnly traceP input of
  73     Left  _err -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err
  74     Right trace -> trace