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.
Parsing
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 $ S.map 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
Code
And that's it! The full code is on Github. Let me know what you think.