Advent of Code 2019 day 6

    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

    Part 1

    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

    Part 2

    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

    1. Find all the steps from YOU to the common primary, COM.
    2. 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).

    Neil Smith

    Read more posts by this author.