Universal Orbit Map

Advent of Code 2019 Day 6

Task: Solve for X where...

Part 1

X = the total number of direct and indirect orbits

Part 2

X = the minimum number of orbital transfers required to move from the object YOU are orbiting to the object SAN is orbiting

Example input

COM)B
B)C
C)D
D)E
E)F
B)G
G)H
D)I
E)J
J)K
K)L

It represents:

• A series of planet-to-planet orbital relationships
• Each line follows the pattern A)B
• The pattern indicates that planet B is in orbit around planet A

A hint at Part 2:

Before you use your map data to plot a course

• I sense the need for a pathfinding algorithm
• I sense an inability to complete Part 2

Part 1

1. Counting the total number of orbits
2. Counting algorithmically
3. Writing a working recursive algorithm
4. A visual depiction of the algorithm

Counting the total number of orbits

The puzzle instructions offer this visual based on the example input:

        G - H       J - K - L
       /           /
COM - B - C - D - E - F
               \
                I

And the following confirmations:

• D has a total of 3 orbits: 1 direct, 2 indirect
• L has a total of 7 orbits: 1 direct, 6 indirect
• COM has a total of 0 orbits
• The grand total of orbits is 42

What are the other orbit totals?

• B has a total of 1 orbit: 1 direct
• G has a total of 2 orbits: 1 direct, 1 indirect
• H has a total of 3 orbits: 1 direct, 2 indirect
• C has a total of 2 orbits: 1 direct, 1 indirect
• I has a total of 4 orbits: 1 direct, 3 indirect
• E has a total of 4 orbits: 1 direct, 3 indirect
• J has a total of 5 orbits: 1 direct, 4 indirect
• F has a total of 5 orbits: 1 direct, 4 indirect
• K has a total of 6 orbits: 1 direct, 5 indirect

3 + 7 + 0 + 1 + 2 + 3 + 2 + 4 + 4 + 5 + 5 + 6 = 42

Counting algorithmically

The visualized map, again:

        G - H       J - K - L
       /           /
COM - B - C - D - E - F
               \
                I

The visualized map, but with counts of orbited planets instead of planet names:

        2 + 3       5 + 6 + 7
       +           +
  0 + 1 + 2 + 3 + 4 + 5
               +
                4

How could I generate these numbers with an algorithm?

Writing a working recursive algorithm

The example input, again:

COM)B
B)C
C)D
D)E
E)F
B)G
G)H
D)I
E)J
J)K
K)L

As a dictionary of orbited planets and the planets that directly orbit them

COM: B
B: C, G
C: D
D: E, I
E: F, J
G: H
J: K
K: L

A recursive algorithm that moves from key to the value to key to value, incrementing a count of orbiters at each subsequent level

Recursive Sub-routine: Tally Orbiters
Accepts two parameters
  1. Name of planet to look-up
  2. Level indicating number of orbited planets each planet found has
If there is no key in the object mapping planets to their orbiters that matches the first parameter
  Return 0
Else - there is a key
  Return the sum of:
    1. The product of level and the number of orbiting planets associated with the key
    2. The sum of all returned values from calling Tally Orbiters with each orbiting planet and an incremented level

A visual depiction of the algorithm

Part 2

1. Ugh, pathfinding...or is it?
2. Finding a pattern...and hoping it's good enough
3. Writing a working algorithm
4. A visual depiction of my working algorithm

Ugh, pathfinding...or is it?

• As anticipated, Part 2 asks for a shortest path between two points
• However, it seems like the path may be very simple...almost V-like in shape

Finding a pattern...and hoping it's good enough

The updated example input:

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

The diagram offered for this part highlights this path:

                          YOU
                         /
        . - .       J - K - .
       /           /
  . - . - . - D - E - .
               \
                I - SAN

Observations

• The meeting point appears to be D
• Two planets directly orbit D
• YOU and SAN both indirectly orbit D

Thinking algorithmically

• I know I can parse the input to map out each planet's direct orbiter
• Then, I can generate two ordered lists: one for YOU and one for SAN, the store each subsequent orbiting planet all the way back to COM
• I'll assume that somewhere in both lists is a first of several shared planets...that one being the planet that forms the apex of the V-like shape depicted in the sample diagram
• Once that planet is found, I need to calculate the sum of all planets in each list prior to the location of the shared planet in each list

Writing a working algorithm

Split the input at each newline character to create a list of strings
  Split each string at each ) character to create a list of two strings

Set planets as an empty object

For each 2-element array of strings
  Create a key in planets named using the second element
  Set as that key's value the first element

By now we have a dictionary mapping each orbiting planet with their direct orbiter

Starting from the value associated with the 'YOU' key in planets
  Accumulate an ordered list of planets that eventually lead back to 'COM'

Starting from the value associated with the 'SAN' key in planets
  Accumulate an ordered list of planets that eventually lead back to 'COM'

Starting from the first value in the list ending with 'YOU'
  Check whether the current planet exists in the path ending with 'SAN'
    Once a match is found
      Store the sum of the number of planets visited prior to the current planet in both paths

Return the sum

A visual depiction of my working algorithm

I did it!!

• Wow, both parts solved. I wasn't expecting that.
• Recursion and quasi-pathfinding. I didn't think I would figure out Part 2.
• Sadly, no simulator this time. It would have been cool to render the map of my input's solar system. But I have no idea how I'd even begin to craft it as a data structure, let alone render it on a page.
• Oh well. The Gifs I made seem explanatory enough!