Advent of Code 2021 day 5

Day 5 was one where generalising the code made things simpler. I started by being explicit about filling out lines, but ended up with generalising the solution to something much neater.

This being a problem with coordinates and counting intersections, I built my solution around a Map from Points to Ints (the counts of the number of lines crossing each point). A Point comes from the linear package, the V2 object for two-dimensional points.

That gives me these data types, and the parser to read them.

import qualified Data.Map.Strict as M
import Linear (V2(..), (^+^))

type Point = V2 Int
type Grid = M.Map Point Int

data Line = Line Point Point deriving (Eq, Show)


traceP = lineP `sepBy` endOfLine
lineP = Line <$> (pointP <* " -> ") <*> pointP
pointP = V2 <$> (decimal <* ",") <*> decimal

The other operation is to expand a line from the two endpoints to the set of points it represents. I can define a delta for each line, how the location changes at each step along the line. The constraint that lines are horizontal, vertical, or at 45⁰ means the components of that delta are the signum of the differences between the line ends.

Expanding the line then becomes repeatedly applying the delta to the starting point, taking enough points to include both ends.

expandLine :: Line -> [Point]
expandLine line@(Line p0 _p1) = take numPoints $ iterate (^+^ delta) p0
  where numPoints = findLen line + 1
        delta = findDelta line

findLen :: Line -> Int
findLen (Line (V2 x0 y0) (V2 x1 y1)) = 
  max (abs (x1 - x0)) (abs (y1 - y0))

findDelta :: Line -> Point
findDelta (Line (V2 x0 y0) (V2 x1 y1)) = (V2 dx dy)
  where dx = signum (x1 - x0)
        dy = signum (y1 - y0)

To find the counts, I expand all the lines into points and include them in the diagram with nested folds around M.insertWith. I find the answers by filtering the diagram and finding its size.

part2 trace = M.size $ M.filter (> 1) diagram
  where allLines = map expandLine trace
        diagram = addLines M.empty allLines
        
addLines :: Grid -> [[Point]] -> Grid
addLines = foldr insertLine 
  where insertLine l d = foldr insertPoint d l
        insertPoint p d = M.insertWith (+) p 1 d

Part 1 becomes slightly more complex, as I have to include only the horizontal and vertical lines. A quick predicate to define the lines to include, then a filter to retain only the lines I want.

part1 trace = M.size $ M.filter (> 1) diagram
  where hvLines = map expandLine $ filter isHorizOrVert trace
        diagram = addLines M.empty hvLines

isHoriz :: Line -> Bool
isHoriz (Line (V2 x0 _y0) (V2 x1 _y1)) = x0 == x1

isVert :: Line -> Bool
isVert (Line (V2 _x0 y0) (V2 _x1 y1)) = y0 == y1

isHorizOrVert :: Line -> Bool
isHorizOrVert line = (isHoriz line) || (isVert line)

Code

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

Advent of Code 2021 day 5

Code

Neil Smith