Day 6: Universal Orbit Map

https://adventofcode.com/2019/day/6



In [1]:

    
inputLines = lines <$> readFile "input/day06.txt"



In [2]:

    
import qualified Data.Map as Map
import Data.List.Split



In [3]:

    
inputOrbits :: IO (Map.Map String String)
inputOrbits = Map.fromList . map ((\ [a, b] -> (b, a)) . splitOn ")") <$> inputLines

Parse the given strings and construct a map of direct orbits

The map maps each object to the object that it orbits directly.



In [4]:

    
parseOrbits :: [String] -> Map.Map String String
parseOrbits = Map.fromList . map ((\ [a, b] -> (b, a)) . splitOn ")")



In [5]:

    
inputOrbits = parseOrbits <$> inputLines

Find the path from a given object to the center of mass



In [6]:

    
pathToCenterOfMass :: Map.Map String String -> String -> [String]
pathToCenterOfMass orbits start = go start
    where
        go :: String -> [String]
        go object = case maybeObject2 of Nothing -> [object]
                                         Just object2 -> object:go object2
            where
                maybeObject2 :: Maybe String
                maybeObject2 = Map.lookup object orbits

Part 1

Calculate the total number of direct and indirect orbits for a given map of direct orbits. Note that we use pred to reduce each path length by one because each path includes its start object, which does not count.



In [7]:

    
numberOfOrbits :: Map.Map String String -> Int
numberOfOrbits directOrbits = sum . map (pred . length . pathToCenterOfMass directOrbits) . Map.keys $ directOrbits

Verify given example



In [8]:

    
numberOfOrbits $ parseOrbits ["COM)B", "B)C", "C)D", "D)E", "E)F", "B)G", "G)H", "D)I", "E)J", "J)K", "K)L"]

Solution



In [9]:

    
numberOfOrbits <$> inputOrbits

Part 2

Calculate the number of steps from the object orbited by object1 to the one orbited by object2.



In [10]:

    
orbitalTransfers :: String -> String -> Map.Map String String -> Int
orbitalTransfers object1 object2 directOrbits =
    let
        pathFromCenterOfMass = reverse . pathToCenterOfMass directOrbits
        
        path1 = pathFromCenterOfMass object1
        path2 = pathFromCenterOfMass object2
        
        commonPrefixLength :: [String] -> [String] -> Int
        commonPrefixLength _ [] = 0
        commonPrefixLength [] _ = 0
        commonPrefixLength (x:xs) (y:ys)
            | x == y = succ $ commonPrefixLength xs ys
            | otherwise = 0
    in
        -- Modifications to the sum of both path lengths:
        -- - deduct the common prefix path length twice
        -- - add one because the last common object has to be visited
        -- - subtract two because object1 and object2 don't count
        -- - subtract one because the number of steps is one less than the path length
        length path1 + length path2 - 2 * commonPrefixLength path1 path2 + 1 - 2 - 1

Verify given example



In [11]:

    
orbitalTransfers "YOU" "SAN" $ parseOrbits ["COM)B", "B)C", "C)D", "D)E", "E)F", "B)G", "G)H", "D)I", "E)J", "J)K", "K)L", "K)YOU", "I)SAN"]

Solution



In [12]:

    
orbitalTransfers "YOU" "SAN" <$> inputOrbits