December 03, 2019
in
#advent of code
#haskell

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

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 `Location`

s 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 `Segment`

s, 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 `pathP`

s. `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.)

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 `take`

n, and the `foldl'`

takes each step and `insert`

s 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 `foldl`

ing all the segments, and we do all the paths by `map`

ping 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 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 `Location`

s to being a `Map`

of `Location`

s to `Int`

s (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.