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
- Counting the total number of orbits
- Counting algorithmically
- Writing a working recursive algorithm
- 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
- Ugh, pathfinding...or is it?
- Finding a pattern...and hoping it's good enough
- Writing a working algorithm
- 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
andSAN
both indirectly orbitD
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 forSAN
, the store each subsequent orbiting planet all the way back toCOM
- 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!
Top comments (0)