day-6

Solution in Python for the day 6 puzzle of the 2019 edition of the Advent of Code annual programming challenge.

🎄🌟🌟 Universal Orbit Map 🎄🌟🌟

🔍📖 Annotated Statements

You've landed at the Universal Orbit Map facility on Mercury. Because navigation in space often involves transferring between orbits, the orbit maps here are useful for finding efficient routes between, for example, you and Santa. You download a map of the local orbits (your puzzle input).

Backstory introduction.

Except for the universal Center of Mass (COM), every object in space is in orbit around exactly one other object. An orbit looks roughly like this:

                  \
                   \
                    |
                    |
AAA--> o            o <--BBB
                    |
                    |
                   /
                  /

In this diagram, the object BBB is in orbit around AAA. The path that BBB takes around AAA (drawn with lines) is only partly shown. In the map data, this orbital relationship is written AAA)BBB, which means "BBB is in orbit around AAA".

No questions yet.

Before you use your map data to plot a course, you need to make sure it wasn't corrupted during the download. To verify maps, the Universal Orbit Map facility uses orbit count checksums - the total number of direct orbits (like the one shown above) and indirect orbits.

What are these indirect orbits?

Whenever A orbits B and B orbits C, then A indirectly orbits C. This chain can be any number of objects long: if A orbits B, B orbits C, and C orbits D, then A indirectly orbits D.

Example:

Body	Example
A	Moon
B	Earth
C	Sun
D	Galactic Center

For example, suppose you have the following map:

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

Visually, the above map of orbits looks like this:

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

In this visual representation, when two objects are connected by a line, the one on the right directly orbits the one on the left.

Here, we can count the total number of orbits as follows:

D directly orbits C and indirectly orbits B and COM, a total of 3 orbits.
L directly orbits K and indirectly orbits J, E, D, C, B, and COM, a total of 7 orbits.
COM orbits nothing.

The total number of direct and indirect orbits in this example is 42.

Computing the number of orbits can be compared as a graph traversal.

What is the total number of direct and indirect orbits in your map data?

Indeed.

📃➡ Input Contents Format

Content files, example.txt and input.txt, contain a number of lines with two alphanumeric identifiers separated by a single closing parenthesis.

⚙🚀 Implementation

💾🔍 Content Decoding

The most practical output format after decoding will be a list of tuples. Each tuple representing a pair of objects, the second one orbiting the first one.

Starting from a filename encoded as a str object, the following sequence of operations are required:

1. Open and read the file, with the usual open() and read() methods.
2. Remove the trailing line return, using strip().
3. Split the single string into a list of strings using split() on new line boundaries with os.linesep.
4. For each item of the list of strings
   1. Split the string using a closing parenthesis ) as separator.

def load_contents(filename: str) -> list[tuple]:
    lines = open(filename).read().strip().split(os.linesep)
    contents = [tuple(l.split(')')) for l in lines]
    return contents

💡🙋 Puzzle Solving

The answer as stated in the puzzle, consists in the total of direct and indirect orbits.

What is the total number of direct and indirect orbits in your map data?

Direct orbits correspond to the contents extracted from the input file. The indirect orbits require to compute all the paths between objects separated by distance of two or greater.

A first brute force approach to this problem would consist in building a per-object map which points to a list of other objects it relates to. The algorithm in this case requires computing a map of objects which orbit another object, which is the reverse of the contents extracted from the file.

1. Initialize a new map.
2. For each (orbited, orbiter) tuple in the content list.
   1. Create a new orbiter entry in the map referencing the orbited object.

orbiters = dict()
for orbited, orbiter in contents:
    orbiters[orbiter] = orbited

The next step consists in expanding all the possible dependencies.

1. Initialize a new map.
2. For each orbiter in the orbiters map
   1. Expand the list of orbited objects.

The expansion of an object into the list of all objects it orbits around is easier done using a recursive method, taking the orbiters along a single orbiter, and returns a list of objects.

1. Initialize an empty list.
2. Lookup the object around which the orbiter orbits around.
3. Append the orbited object to the list.
4. Test if the orbited object is equal to COM, the universal Center of Mass:
   • If not equal, then call again this method and append its result to the list before returning it.
5. Return the list of orbited objects.

COM = 'COM'

def expand_orbited_objects(orbiters: list[tuple], orbiter: str) -> list[str]:
    orbited_objects = list()
    orbited = orbiters[orbiter]
    orbited_objects.append(orbited)
    if COM != orbited:
       orbited_objects.extend(expand_orbited_objects(orbiters, orbited))
    return orbited_objects

Computing the answer is just a mater of counting all the items for all the orbiters.

answer = sum(len(v) for v in orbited_objects.values())

The solving method pieced together:

def solve(contents: list[tuple]) -> int:
    orbiters = dict()
    for orbited, orbiter in contents:
        orbiters[orbiter] = orbited
    orbited_objects = dict()
    for orbiter in orbiters:
        orbited_objects[orbiter] = expand_orbited_objects(
            orbiters=orbiters, orbiter=orbiter)
    output = sum(len(v) for v in orbited_objects.values())
    return output

Contents	Answer
example.txt	42
input.txt	151345

😰🙅 Part Two

🥺👉👈 Annotated Description

Now, you just need to figure out how many orbital transfers you (YOU) need to take to get to Santa (SAN).

You start at the object YOU are orbiting; your destination is the object SAN is orbiting. An orbital transfer lets you move from any object to an object orbiting or orbited by that object.

For example, suppose you have the following map:

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

Visually, the above map of orbits looks like this:

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

In this example, YOU are in orbit around K, and SAN is in orbit around I. To move from K to I, a minimum of 4 orbital transfers are required:

    K to J
    J to E
    E to D
    D to I

It appears that a lot of materials can be reused from part one, notably the per-orbited objects.

Afterward, the map of orbits looks like this:

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

Understood.

What is the minimum number of orbital transfers required to move from the object YOU are orbiting to the object SAN is orbiting? (Between the objects they are orbiting - not between YOU and SAN.)

🤔🤯 Solver Implementation

First things would be to check that the YOU and SAN.

>>> 'YOU' in orbited_objects
True
>>> 'SAN' in orbited_objects
True

Using the set object, we can easily factorize common orbited objects by both YOU and SAN objects. Thus the part two is for once quite straight forward to implement:

def solve_part_two(contents: list[tuple]) -> int:
    orbiters = map_orbiters(contents=contents)
    orbited_objects = map_orbited_objects(orbiters=orbiters)
    san_orbited_objects = set(orbited_objects['SAN'])
    you_orbited_objects = set(orbited_objects['YOU'])
    unique_orbited_objects = you_orbited_objects ^ san_orbited_objects
    answer = len(unique_orbited_objects)
    return answer

Contents	Answer
example_part2.txt	4
input.txt	391

🚀✨ Further Improvements 🚀✨

The recursive implementation of the expand_orbited_objects() method could be simplified using an iterator yielding list items.