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
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
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)