Creating, using, and merging branches
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
YOUto the common primary,
- Find all the steps from
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
SAN, you follow the path from
COM until you get to
SWI, then the reversed path from
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
SAN in their respective paths.
And here's the code.
transferSteps finds all the primaries visited going from a satellite to
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.)