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)


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

    Neil Smith

    Read more posts by this author.