Universal Orbit Map
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-04-28 15:11:50

## [Advent of Code 2019 Day 6](https://adventofcode.com/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
![Visualization of Part 1 algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kywzhe2vuivx2of8eoxy.gif)

## 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
![Visualization of Part 2 algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/w3g5z0ji275bkglgltk0.gif)

## 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!