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
   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) diagramHV
  27   where hLines = map expandLineH $ filter isHoriz trace
  28         vLines = map expandLineV $ filter isVert  trace
  29         diagramH = addLines M.empty hLines
  30         diagramHV = addLines diagramH vLines
  31
  32 part2 trace = M.size $ M.filter (> 1) diagram4
  33   where hLines = map expandLineH $ filter isHoriz trace
  34         vLines = map expandLineV $ filter isVert trace
  35         pdLines = map expandLinePD $ filter isPDiag trace
  36         ndLines = map expandLineND $ filter isNDiag trace
  37         diagram1 = addLines M.empty hLines
  38         diagram2 = addLines diagram1 vLines
  39         diagram3 = addLines diagram2 pdLines
  40         diagram4 = addLines diagram3 ndLines
  41
  42
  43
  44 isHoriz :: Line -> Bool
  45 isHoriz (Line (V2 x0 _y0) (V2 x1 _y1)) = x0 == x1
  46
  47 isVert :: Line -> Bool
  48 isVert (Line (V2 _x0 y0) (V2 _x1 y1)) = y0 == y1
  49
  50 -- x and y increasing together
  51 isPDiag :: Line -> Bool
  52 isPDiag (Line (V2 x0 y0) (V2 x1 y1)) =
  53   (x0 /= x1)
  54   && (y0 /= y1)
  55   && ((x1 - x0) == (y1 - y0))
  56
  57 -- x increasing, y decreasing
  58 isNDiag :: Line -> Bool
  59 isNDiag (Line (V2 x0 y0) (V2 x1 y1)) =
  60   (x0 /= x1)
  61   && (y0 /= y1)
  62   && ((x1 - x0) == (y0 - y1))
  63
  64
  65 -- horizOrVert :: Line -> Bool
  66 -- horizOrVert line = isHoriz line || isVert line
  67
  68
  69 -- hovLines = filter horizOrVert
  70
  71 expandLineH :: Line -> [Point]
  72 expandLineH (Line (V2 x0 y0) (V2 _x1 y1)) = -- x0 == x1
  73   [V2 x0 y | y <- [yMin..yMax]]
  74   where yMin = min y0 y1
  75         yMax = max y0 y1
  76
  77 expandLineV :: Line -> [Point]
  78 expandLineV (Line (V2 x0 y0) (V2 x1 _y1)) = -- y0 == y1
  79   [V2 x y0 | x <- [xMin..xMax]]
  80   where xMin = min x0 x1
  81         xMax = max x0 x1
  82
  83 -- x and y increasing together
  84 expandLinePD :: Line -> [Point]
  85 expandLinePD (Line (V2 x0 y0) (V2 x1 y1)) = map (uncurry V2) coords
  86   where xMin = min x0 x1
  87         xMax = max x0 x1
  88         yMin = min y0 y1
  89         yMax = max y0 y1
  90         coords = zip [xMin..xMax] [yMin..yMax]
  91
  92 -- x increasing, y decreasing
  93 expandLineND :: Line -> [Point]
  94 expandLineND (Line (V2 x0 y0) (V2 x1 y1)) = map (uncurry V2) coords
  95   where xMin = min x0 x1
  96         xMax = max x0 x1
  97         yMin = min y0 y1
  98         yMax = max y0 y1
  99         yMax1 = yMax - 1
 100         coords = zip [xMin..xMax] [yMax, yMax1..yMin]
 101
 102
 103 addLines :: Grid -> [[Point]] -> Grid
 104 addLines diagram expandedLines = foldr insertLine diagram expandedLines
 105   where insertPoint p d = M.insertWith (+) p 1 d
 106         insertLine l d = foldr insertPoint d l
 107
 108
 109 -- Parse the input file
 110
 111 traceP = lineP `sepBy` endOfLine
 112 lineP = Line <$> (pointP <* " -> ") <*> pointP
 113 pointP = V2 <$> (decimal <* ",") <*> decimal
 114
 115 -- successfulParse :: Text -> (Integer, [Maybe Integer])
 116 successfulParse input =
 117   case parseOnly traceP input of
 118     Left  _err -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err
 119     Right trace -> trace