December 07, 2019
in
#advent of code
#haskell

This one turned out to be much simpler than I first thought. A brief reading of the task description had me thinking about trees of nested orbits and trying to fold over them to find all the orbits. But it turns out that all you need to know is how to go from a satellite to its primary.

I store that information in a `Map`

, which I build using a `fold`

over the list of orbits, inserting each satellite-primary pair as I go.

```
-- from satellite to primary
type Orbits = M.Map String String
buildOrbits :: [(String, String)] -> Orbits
buildOrbits = foldl' addOrbit M.empty
addOrbit :: Orbits -> (String, String) -> Orbits
addOrbit orbits (primary, satellite) = M.insert satellite primary orbits
```

Counting the direct and indirect orbits for a *single* satellite is 1, plus the number of orbits available from its primary.

```
orbitCount :: Orbits -> String -> Int
orbitCount orbits here
| here `M.member` orbits = 1 + (orbitCount orbits (orbits!here))
| otherwise = 0
```

If you do that for all the satellites, you get the total number of orbits.

```
part1 :: Orbits -> Int
part1 orbits = sum $ map (orbitCount orbits) $ M.keys orbits
```

You could do this with a graph-search algorithm. But given that the set of orbits is a tree, an easier way to do it is

- Find all the steps from
`YOU`

to the common primary,`COM`

. - Find all the steps from
`SAN`

to`COM`

.

Those two paths will meet at some point and be identical from there onwards. Say they meet at `SWI`

, the switching planet. To move from `YOU`

to `SAN`

, you follow the path from `YOU`

to `COM`

until you get to `SWI`

, then the reversed path from `SAN`

to `SWI`

.

You can find the distinct parts of each transfer path with the `difference`

operation. And as you only need the *number* of steps, you only need the sizes of the paths. That means you can treat the paths as a `Set`

of primaries visited. Because `SWI`

is common to both paths, it will be excluded from the distinct parts, so the sets will be too small; but that's fixed by including the direct primary of `YOU`

and `SAN`

in their respective paths.

And here's the code. `transferSteps`

finds all the primaries visited going from a satellite to `COM`

.

```
transferSteps :: Orbits -> Transfers -> String -> Transfers
transferSteps orbits transfers here
| here `M.member` orbits = transferSteps orbits transfers' there
| otherwise = transfers'
where there = orbits!here
transfers' = S.insert here transfers
```

The code for `part2`

finds the two paths, finds the distinct parts of them, finds the sizes of those parts, and returns the sum.

```
part2 :: Orbits -> Int
part2 orbits = youDist + sanDist
where youTrans = transferSteps orbits S.empty (orbits!"YOU")
sanTrans = transferSteps orbits S.empty (orbits!"SAN")
onlyYou = youTrans \\ sanTrans
onlySan = sanTrans \\ youTrans
youDist = S.size onlyYou
sanDist = S.size onlySan
```

(There's an alternative implementation that uses a `Map`

to keep track of the explicit distances to each step on the path, and then finding the maximal value of distance in the disjoint paths. But for this particular instance, the `Set`

method is simpler.)

The full solution is on Gitweb (and Github).