Advent of Code 2019 day 3

    Day 3 is back to familiar ground: walking across a grid of points, looking for interesting things along the way.

    Data structures

    The first thing to fix is the data structures I'll be using to address the problem. As we want to find the points that intersect between paths, a Set of Locations seems like a good place to start.

    type Location = V2 Int -- x, y
    type Visited = S.Set Location

    That's where we want to end up, but what does the input look like? It's a sequence of path Segments, each with a Direction and a length.

    data Direction = East | South | West | North deriving (Show, Eq)
    data Segment = Segment { _direction :: Direction
                           , _steps :: Int
                           } deriving (Show, Eq)

    The first part of the problem is going to be expanding those segments into the Path taken by each wire. As we're building the path, we need to keep track of both the locations visited, and the current _tip of the wire so we know where to add the next segment's locations.

    data Path = Path { _visited :: Visited
                     , _tip :: Location
                   deriving (Show, Eq)

    Now the data structures are fixed, most of the rest of the work is just translating from one to another.


    We have, at last, something almost interesting to parse! Here's the parser, using the applicative style. Briefly, <$> is like function composition, <*> joins arguments, and <|> shows choices between alternatives.

    wiresP = many pathP
    pathP = segmentP `sepBy1` comma
    segmentP = segmentify <$> directionP <*> integer
        where segmentify direction steps = 
                  Segment { _direction = direction, _steps = steps }
    directionP = eP <|> sP <|> wP <|> nP
    eP = (symb "R" *> pure East)
    sP = (symb "D" *> pure South)
    wP = (symb "L" *> pure West)
    nP = (symb "U" *> pure North)

    Paraphrasing, this shows that the wires are many (0 or more) paths, and each path is a sequence of one or more segments separated by commas. A segment is a combination of a direction and a number of steps, and the function segmentify builds the Segment record from them. The direction parser just takes a symbol and returns the direction, using pure to turn it into an applicative value.

    I had to use sepBy1 in order to prevent Megaparsec creating an infinite number of zero-length pathPs. sepBy1 requires there be at least one segment in the path. Yes, there are only two paths in the input and this allows for any number, but this way was almost easier.

    (If you want to know more about this style of parsing, the Monday Morning Haskell posts are a good introduction.)

    Part 1

    The core of this part is the function travelSegment, which takes a single Segment and a Path, and extends the path with the segment. Most of it should be simple enough to read. The main work is done in the foldl' function; the iterate generates an infinite number of steps in the specified direction, the right number are taken, and the foldl' takes each step and inserts it into the visited set. (The arithmetic signs with ^ are for manipulating the vectors I'm using for locations.)

    travelSegment :: Path -> Segment -> Path
    travelSegment path segment = path { _tip = tip', _visited = visited' }
        where   delta = facing $ _direction segment
                distance = _steps segment
                start = _tip path
                visited = _visited path
                visited' = foldl' (flip S.insert) visited $ take distance $ drop 1 $ iterate (^+^ delta) start
                tip' = start ^+^ distance *^ delta
    facing :: Direction -> Location
    facing East = V2 1 0
    facing South = V2 0 (-1)
    facing West = V2 (-1) 0
    facing North = V2 0 1

    Travelling along the whole path is just foldling all the segments, and we do all the paths by mapping over all the segment specifications.

    travelAllPaths :: [[Segment]] -> [Path]
    travelAllPaths = map travelPath
    travelPath :: [Segment] -> Path
    travelPath segments = foldl' travelSegment path0 segments
        where   path0 = Path { _visited = S.empty, _tip = V2 0 0 }

    We now have all the sets of points visited by each wire. We can find the common points by intersecting those sets, and then find the closed one. crossovers finds where the wires cross, and closest find the crossover closer to the origin. Note that fold1' takes the first element of the list as the base case for the fold.

    closest :: Visited -> Int
    closest points = S.findMin $ manhattan points
    crossovers :: [Path] -> Visited
    crossovers travelledPaths = 
          foldl1' S.intersection $ map _visited travelledPaths

    The code for this part is on Github. Part 2 is a bit different…

    Part 2

    Part 2 adds an interesting wrinkle. Rather than just keeping track of the crossings, we now have to annotate each step with the distance to get there. There's two ways to do this. One is to keep the code as above, and re-create the distances once I've found the crossings. The other is to re-engineer the existing code to keep the "distance travelled" annotations as we go. I decided to do the latter.

    The main difference is changing the type of Visited from being a Set of Locations to being a Map of Locations to Ints (as the distances). This isn't too bad, as the keys in a Map naturally form a Set. Not much else needs to change, beyond using functions from the Map library rather than the Set library. The Path record type now needs to keep track of the _currentLength as well as as the tip.

    The travelSegment function needs to change, so that it includes these distances as each segment is processed. The foldl' now operates on pairs of (distance, location), and that needs a special insertStep function to handle the pair and record the shortest distances if a point is revisited.

    travelSegment :: Path -> Segment -> Path
    travelSegment path segment = path { _tip = tip', _visited = visited', _currentLength = len'}
        where   delta = facing $ _direction segment
                distance = _steps segment
                start = _tip path
                len = _currentLength path
                len' = len + distance
                visited = _visited path
                visited' = foldl' insertStep visited $ take distance $ drop 1 $ zip [len, (len + 1) ..] $ iterate (^+^ delta) start
                tip' = start ^+^ distance *^ delta
                insertStep visits (dist, loc) = if loc `M.member` visits
                                                then visits
                                                else M.insert loc dist visits

    crossovers also needs to change, so that each crossover is stored with the sum of path lengths that lead to it; M.intersectionWith (+) does that. (Thanks to Reddit user mstksg for pointing that out to me.)

    crossovers :: [Path] -> Visited
    crossovers travelledPaths = 
          foldl1' (M.intersectionWith (+)) $ map _visited travelledPaths

    shortestPaths then finds the smallest element in the map.

    shortestPaths :: Visited -> Int
    shortestPaths crossings = minimum $ M.elems crossings


    And that's it! The full code is on Github. Let me know what you think.

    Neil Smith

    Read more posts by this author.