## DEV Community

Jon Bristow

Posted on • Updated on

# Advent of Code 2019 Solution Megathread - Day 6: Universal Orbit Map

Ah, BFS my old friend. I must resist booting up a gremlin database to solve this one.

### Day 6 - The Problem

Cool as cucumbers we descend upon the map station on Mercury. For once, nothing is wrong, and we just need to verify the data and then plot an efficient course.

Part 1 is fairly straightforward, but slow if you're not careful. We've returned to the land of generous examples and explanations on this one.

Part 2 is a perfect place to try out your favorite way to do a modified breadth first search.

It seems like we're alternating between challenging and straightforward prompts. Oh well, at least I think we'll see some creative optimizations in the answers!

### Ongoing Meta

If you were part of Ryan Palo's leaderboard last year, you're still a member of that!

I'll edit in any leaderboards that people want to post, along with any description for the kinds of people you want to have on it. (My leaderboard is being used as my office's leaderboard.) And if I get something wrong, please call me out or message me and I’ll fix it ASAP.

There's no limit to the number of leaderboards you can join, so there's no problem belonging to a "Beginner" and a language specific one if you want.

#### Neat Statistics

I'm planning on adding some statistics, but other than "what languages did we see yesterday" does anyone have any ideas?

Languages Seen On Day 05

• JavaScript x 4
• Python x 3
• c
• Kotlin
• PHP
• Racket
• Rust
• Swift

Massimo Artizzu • Edited

Finally a nice and short one.

My solutions aren't particularly efficient as they involve recursive functions, but still run pretty fast so whatever. ¯\_(ツ)_/¯

## Part 1

``````const starMap = input.split('\n').reduce((map, line) => {
map[line.split(')')[1]] = line.split(')')[0];
return map;
}, {});

const getAncestorCount = body => body in starMap ? 1 + getAncestorCount(starMap[body]) : 0;

console.log(Object.keys(starMap).reduce((sum, body) => sum + getAncestorCount(body), 0));
``````

## Part 2

``````// starMap defined as above...
const getAncestors = body => body in starMap ? [ ...getAncestors(starMap[body]), starMap[body] ] : [];

const youAncestors = getAncestors('YOU');
const santaAncestors = getAncestors('SAN');

const transfers = youAncestors
.filter(body => santaAncestors.includes(body))
.map(body => [
// .reverse is actually not necessary...
...youAncestors.slice(youAncestors.indexOf(body)).reverse(),
// + 1 because we'd include the common planet twice
...santaAncestors.slice(santaAncestors.indexOf(body) + 1)
]);

// - 1 because we're counting the movements, not the positions
console.log(Math.min(...transfers.map(xfer => xfer.length - 1)));
``````

You can find my solutions on GitHub.

Jon Bristow

Maybe a future node version will add tail call optimization, and Javascript could have efficient recursion again.

Tail recursive functions are so much clearer to me than a while loop... something about walking down to a trivial solution just makes sense. 🤷‍♀️

Massimo Artizzu

I long the day they will tackle the problem once and for all. It's the last thing missing from ES2015! (Only Safari supports it.)

SavagePixie

There's got to be some better way to go about it, as even with memoisation it takes about half a minute to sort through part one, but hey, memoisation is cool.

JavaScript

``````const findElement = (input, tag) => input.filter(x => x.split(')')[1] == tag)

const getOrbits = (input, element, orbits=1) => {
if (!getOrbits.checkedOrbits) getOrbits.checkedOrbits = {}

const [ centre, object ] = element.split(')')
if (centre == 'COM') {
getOrbits.checkedOrbits[object] = 1
return orbits
}
if (getOrbits.checkedOrbits.hasOwnProperty(centre)) {
getOrbits.checkedOrbits[object] = getOrbits.checkedOrbits[centre] + 1
return orbits + getOrbits.checkedOrbits[centre]
}
const [ nextObject ] = findElement(input, centre)
return getOrbits(input, nextObject, orbits + 1)
}

const getOrbitChain = (input, element, chain=[]) => {
const [ centre, object ] = element.split(')')
const newChain = chain.concat(centre)
if (centre == 'COM') return newChain
const [ nextObject ] = findElement(input, centre)
return getOrbitChain(input, nextObject, newChain)
}

const calculateTransfers = (input, origin, destination) => {
const fromYou = getOrbitChain(input, origin)
const fromDest = getOrbitChain(input, destination)
const commonObject = fromYou.filter(x => fromDest.includes(x))[0]
return fromYou.indexOf(commonObject) + fromDest.indexOf(commonObject) - 2
}

module.exports = input => {
const data = input.split('\n')
const partOne = data.reduce((a, b) => a + getOrbits(data, b), 0)
const partTwo = calculateTransfers(data, 'YOU', 'SAN')
return({ partOne, partTwo })
}
``````

Jon Bristow • Edited

Unsolicited hints from a fellow 2+ minute initial runtime maker:

• Make sure your culling is working properly,
• only keep the minimum info you need for each loop pass
• meditate on the implications of “every object orbits around one other object.”

SavagePixie • Edited

You're absolutely right. I've changed the approach and with this I managed to reduce the processing time from 43.3 seconds to 2.6:

``````const calculateOrbits = (input, centre, orbits=0) => {
const objects = input.filter(x => x.split(')')[0] == centre)
return objects. length == 0
? orbits
: objects.reduce((a, b) => a + calculateOrbits(input, b.split(')')[1], orbits + 1), orbits)
}

const calculateTransfers = (input, origin, destination) => {
const fromYou = getOrbitChain(input, origin)
const fromDest = getOrbitChain(input, destination)
const commonObject = fromYou.filter(x => fromDest.includes(x))[0]
return fromYou.indexOf(commonObject) + fromDest.indexOf(commonObject) - 2
}

const findElement = (input, tag) => input.filter(x => x.split(')')[1] == tag)

const getOrbitChain = (input, element, chain=[]) => {
const [ centre, object ] = element.split(')')
const newChain = chain.concat(centre)
if (centre == 'COM') return newChain
const [ nextObject ] = findElement(input, centre)
return getOrbitChain(input, nextObject, newChain)
}

module.exports = input => {
const data = input.split('\n')
const partOne = calculateOrbits(data, 'COM')
const partTwo = calculateTransfers(data, 'YOU', 'SAN')
return({ partOne, partTwo })
}
``````

Johnny

Part 1 was a no-brainer in clojure:

``````; Returns the number of orbits the given object is contained in (i.e. direct orbit + indirect orbits)
(defn orbit-centers [orbit-map object]
(count (take-while some? (drop 1 (iterate orbit-map object)))))

; Returns the sum of the orbit centers for each object in the orbit map.
(defn direct-and-indirect-orbits [orbit-map]
(apply + (map (partial orbit-centers orbit-map) (keys orbit-map))))

; Parses the input format into a map of object -> orbit center
(defn parse-orbit-map [raw]
(apply hash-map (flatten (map (comp reverse #(.split #"\)" %)) (.split #"\n" raw)))))

(def input (parse-orbit-map (slurp (first *command-line-args*))))
(println "Total number of (in)direct orbits:" (direct-and-indirect-orbits input))
``````

I kinda got stuck on part 2, so the solution for this isn't really optimal (takes around half a second):

``````; Returns a sequence of objects that orbit the given center
(defn orbiting [orbit-map center]
(map first (filter #(= (% 1) center) orbit-map)))

; Calculates the minimum amount of traversals required in an orbit map to move from object to destination
; (This is currently very inefficient and bad, I might still improve it)
(defn traversals [orbit-map object destination]
(condp = object
nil Integer/MIN_VALUE
destination -2
(inc (apply max (traversals (dissoc orbit-map object) (orbit-map object) destination)
(for [orbit-obj (orbiting (dissoc orbit-map object) object)]
(traversals (dissoc orbit-map orbit-obj) orbit-obj destination))))))

(println "Traversals required to get from you to santa:" (traversals input "YOU" "SAN"))
``````

Fun one nonetheless!

Jon Bristow

I am fake upset you didn't break out the clojure zipper library for this! (it's like using a cannon for flies in this case)

Johnny • Edited

Oh, I will definitely look into that, thanks for the suggestion.
I'm still a newbie in clj.

Jon Bristow

Zipper is extremely powerful for navigating trees efficiently.

Johnny

I vastly improved it without using zippers now.

``````; Counts the amount of elements in coll before element appears. Returns (count coll) if it doesn't appear at all.
(defn count-until [element coll]
(count (take-while (partial not= element) coll)))

; Calculates the minimum amount of traversals required in an orbit map to move from object to destination
(defn traversals [orbit-map object destination]
(let [object-centers (orbit-centers orbit-map object)
destination-centers (orbit-centers orbit-map destination)
first-common-center (some (set destination-centers) object-centers)]
(+ (count-until first-common-center object-centers)
(count-until first-common-center destination-centers))))
``````

I just fetch the first common center of both objects and add the steps it takes to get there for both.

Neil Gall • Edited

Back to Prolog today but rather than battle with reading the input file in Prolog and turning it into relations, which I have no idea where to begin with, I used a Perl one-liner to turn it into Prolog source code. That's not cheating is it?

``````perl -n -e '/^([A-Za-z0-9]+)\)([A-Za-z0-9]+)/ && print "orbits(object_\$1, object_\$2).\n"' <input.txt >rules.pl
``````

Part 1 boiled down to finding all possible paths in the graph and counting them.

``````indirect(C, A) :-
orbits(C, A)
; orbits(C, B), indirect(B, A).

total(N) :-
setof([X, Y], indirect(X, Y), S),
length(S, N).
``````

Part 2 was more involved but is ultimately a similar algorithm in Prolog, filtering the possible solutions down to a single path between the start and end which does not visit any location twice.

``````can_jump(X, Y) :-
orbits(X, Y)
; orbits(Y, X).

part2(Length) :-
findall(L, (
orbits(SAN, object_SAN)
, orbits(YOU, object_YOU)
, path_to(YOU, SAN, P)
, length(P, L)
), Length).

path_to(X, Y, P) :-
path_to_impl(X, Y, [X], P).

path_to_impl(X, Y, _, [Y]) :-
can_jump(X, Y).

path_to_impl(X, Y, L, [Z|Path]) :-
can_jump(X, Z)
, \+(member(Z, L))
, \+(member(Y, L))
, path_to_impl(Z, Y, [Z|L], Path).
``````

Shortest code for the day?

Jon Bristow • Edited

Since I solved one based on the Josephus Problem by hand once because I had just seen a numberphile video based upon it, it's only cheating (in my book) if someone else figured it out for you.

I don't think it's even cheating looking at someone else's solution, as long as you write your own version instead of copying it. (renaming doesn't count!)

Ali Spittel

Honestly, Advent of Code is so much fun. This stuff makes me fall back in love with programming.

``````def get_data(_file):
orbits = {}
objects = set()

for line in _file:
to_orbit, orbiter = line.rstrip().split(")")
orbits[orbiter] = to_orbit

return orbits, objects

def get_orbit(current_obj, orbits):
if current_obj not in orbits: return []
return [orbits[current_obj]] + get_orbit(orbits[current_obj], orbits)

def get_total_orbits(orbits):
return sum(len(get_orbit(obj, orbits)) for obj in objects)

def get_path_between(start, end, orbits):
start_path, end_path = get_orbit(start, orbits), get_orbit(end, orbits)
# Get the first point that is in both paths
overlapping_point = [i for i in start_path if i in end_path][0]
return start_path.index(overlapping_point) + end_path.index(overlapping_point)

with open("input.txt") as _file:
orbits, objects = get_data(_file)

print(f"Part 1: {get_total_orbits(orbits)}")
print(f'Part 2: {get_path_between("YOU", "SAN", orbits)}')
``````

Ryan Palo

After a weekend of flu, I'm back in action--albeit about four days behind the pace now. I'll catch up. Here's today's solution in Rust. No BFS for me. Just a hashtable of children, and a (likely inefficient, but good enough) reverse lookup to do some ancestor math.

``````/// Day 6: Universal Orbit Map
///
/// Find out how many orbits there are in a galaxy map

use std::fs::File;
use std::io::prelude::*;
use std::collections::HashMap;

/// An orbit map is a mapping of nodes to the names of their children.
type OMap = HashMap<String, Vec<String>>;

/// Expects a list of mappings of the form AAA)BBB, one per line.
/// AAA here is the parent of BBB (and potentially many others).
/// Nodes only have one parent.
fn parse_input() -> OMap {
let mut result: OMap = HashMap::new();
for line in buf.lines() {
let text = line.unwrap();
let mut entities = text.split(")");
let parent = entities.next().unwrap();
let child = entities.next().unwrap();
let children = result.entry(parent.to_string()).or_default();
children.push(child.to_string());
result.entry(child.to_string()).or_default();
}
result
}

/// Count the sum of the number of steps it is from each node in a tree
/// to the root.
///
/// The result is the sum of a node's distance from COM and all of its
/// children's orbit counts.
fn count_orbits(depth: usize, parent: &str, orbit_map: &OMap) -> usize {
let children = &orbit_map[parent];
if children.len() == 0 {
depth
} else {
let children_total: usize = children.iter()
.map(|c| count_orbits(depth + 1, c, orbit_map))
.sum();
depth + children_total
}
}

/// Builds a list of the ancestors of an entity starting with its
/// parent and ending with COM.  Or, the String version of COM.
/// Or... the &String version of COM.  Shut up, rust is stupid.
fn ancestors<'a>(orbit_map: &'a OMap, a: &String, mut so_far: Vec<&'a String>) -> Vec<&'a String> {
for (parent, children) in orbit_map.iter() {
if children.contains(a) && parent == "COM" {
so_far.push(parent);
return so_far;
} else if children.contains(a) {
so_far.push(parent);
return ancestors(orbit_map, parent, so_far);
}
}
panic!("Couldn't find parent!");
}

/// Find out how many steps minimum are between the parents of a and b.
///
/// Assumes that the orbit is acyclic with only one root,
/// and thus, there is only one way to get from one to the other,
/// up through the tree to a common ancestor and back down
fn steps_between(orbit_map: &OMap, a: &String, b: &String) -> usize{
let a_ancestors = ancestors(orbit_map, a, Vec::new());
let b_ancestors = ancestors(orbit_map, b, Vec::new());

let same = a_ancestors.iter().rev().zip(b_ancestors.iter().rev())
.filter(|(x, y)| x == y).count();

(a_ancestors.len() - same) + (b_ancestors.len() - same)
}

pub fn run() {
let orbit_map = parse_input();
let parent = "COM".to_string();
println!("Total orbits: {}", count_orbits(0, &parent, &orbit_map));
let me = "YOU".to_string();
let santa = "SAN".to_string();
println!("Distance between me and Santa: {}", steps_between(&orbit_map, &me, &santa))
}
``````

Yuriy Kulikov

Interesting and challenging problem today. I went for a parent-to-children map for the first part and a tree for the second. Runs within a couple of milliseconds.

Part 1:

``````    private fun parseMap(input: String): Map<String, List<String>> = input.lines()
.map { line -> line.substringBefore(")") to line.substringAfter(")") }
.groupBy(
{ (name, _) -> name },
{ (_, orbitedBy) -> orbitedBy }
)

private fun calculateAllOrbits(map: Map<String, List<String>>): Int {
fun List<String>.recursiveSearch(level: Int): Int {
return map { name ->
map.getOrDefault(name, emptyList()).recursiveSearch(level + 1)
}.sum() + level + size
}

return map.getValue("COM").recursiveSearch(-1) + 1
}
``````

Part 2:

``````private fun parseTree(input: String): Map<String, String> {
return input.lines()
.map { line -> line.substringAfter(")") to line.substringBefore(")") }
.toMap()
}

private fun stepsToSanta(tree: Map<String, String>): Int {
fun String.toRoot(): List<String> {
return tree[this]?.toRoot()?.plus(this) ?: listOf(this)
}

val you = "YOU".toRoot()
val san = "SAN".toRoot()
val common = you.intersect(san)
val path = you.plus(san.reversed()).minus(common)
return path.size - 2
}
``````

Jon Bristow • Edited

Without embarrassment, I show this code to you. Part 1 takes a few minutes to complete. I will respond with an optimized version later.

``````import java.nio.file.Files
import java.nio.file.Paths
import java.util.*

object Day06 {

const val FILENAME = "src/main/resources/day06.txt"

fun parseOrbit(s: String): Pair<String, String> {
return """(.*)\)(.*)""".toRegex().matchEntire(s)?.let {
it.groupValues[1] to it.groupValues[2]
} ?: throw Error("Bad orbit: \$s")
}

fun part1(): Int {

.map(::parseOrbit).fold(mutableMapOf<String, MutableSet<String>>()) { m, (a, b) ->
val nset = (m[a] ?: mutableSetOf())
m[a] = nset
m
}.countChildren()
}

fun part2(): Int {
.map(::parseOrbit).fold(mutableMapOf<String, Set<String>>()) { m, (a, b) ->
m[a] = (m[a] ?: emptySet()) + b
m
}

val youParents = paths.filterValues { "YOU" in it }.keys.map { it to 0 }

return paths.findDistanceToSan(queue = LinkedList(youParents), seen = setOf("YOU"))
}

private tailrec fun MutableMap<String, Set<String>>.findDistanceToSan(
queue: Deque<Pair<String, Int>>,
seen: Set<String>
): Int {
val (node, dist) = queue.pop()
return when (node) {
"SAN" -> dist - 1
in seen -> findDistanceToSan(queue, seen)
else -> {
queue.addAll(filterValues { node in it }.keys.map { it to (dist + 1) })
queue.addAll(filterKeys { node == it }.flatMap { (k, v) -> v.map { it to (dist + 1) } })
findDistanceToSan(LinkedList(queue.filterNot { (n, d) -> n in seen }), seen + node)
}
}
}

}

private fun MutableMap<String, MutableSet<String>>.countChildren() =
toList().indices.fold(toMap()) { m, _ ->
m.mapValues { (k, v) ->
v.addAll(v.flatMap { this[it] ?: mutableSetOf() })
v
}
}.toList().sumBy { (k, v) -> v.size }

fun main() {
println(Day06.part1())
println(Day06.part2())
}
``````

Part 2 was my old friend "Djikstra's Algorithm". It wasn't enough data to warrant breaking out A*Search, but if previous years are any indication we will probably need it at some point.

Jon Bristow

Ahhh... much better. This runs in msecs.

``````import java.nio.file.Files
import java.nio.file.Paths
import java.util.*

object Day06 {

private const val FILENAME = "src/main/resources/day06.txt"

private fun parseOrbit(s: String): Pair<String, String> {
return """(.*)\)(.*)""".toRegex().matchEntire(s)?.let {
it.groupValues[1] to it.groupValues[2]
} ?: throw Error("Bad orbit: \$s")
}

private fun List<String>.countPaths() =
map(::parseOrbit).fold(mapOf<String, Set<String>>()) { m, (a, b) ->
val nset = (m[a] ?: emptySet()) + b
m + (a to nset)
}.let { orbits ->
orbits.countChildren(orbits["COM"].orEmpty().map { it to 1 }, 0)
}

private tailrec fun Map<String, Set<String>>.countChildren(
paths: List<Pair<String, Int>>,
size: Int
): Int {

val nextPaths = paths.flatMap {
this[it.first].orEmpty().map { c -> c to it.second + 1 }
}
return when {
nextPaths.isEmpty() -> size + paths.sumBy(Pair<String, Int>::second)
else -> countChildren(nextPaths, size + paths.sumBy(Pair<String, Int>::second))
}

}

private fun List<String>.shortestDistanceToSanta(): Int {
val paths = map(::parseOrbit).fold(mutableMapOf<String, Set<String>>()) { m, (a, b) ->
m[a] = (m[a] ?: emptySet()) + b
m
}

val youParents = paths.filterValues { "YOU" in it }.keys.map { it to 0 }

return paths.findDistanceToSan(queue = LinkedList(youParents), seen = setOf("YOU"))

}

private tailrec fun MutableMap<String, Set<String>>.findDistanceToSan(
queue: Deque<Pair<String, Int>>,
seen: Set<String>
): Int {
val (node, dist) = queue.pop()
return when (node) {
"SAN" -> dist - 1
in seen -> findDistanceToSan(queue, seen)
else -> {
queue.addAll(filterValues { node in it }.keys.map { it to (dist + 1) })
queue.addAll(filterKeys { node == it }.flatMap { (_, v) -> v.map { it to (dist + 1) } })
findDistanceToSan(LinkedList(queue.filterNot { (n, _) -> n in seen }), seen + node)
}
}
}

}

fun main() {
println(Day06.part1())
println(Day06.part2())
}
``````

Stephanie Hope

I liked that the explanation was much easier to understand today. I'm pretty happy with this one.

``````<?php

\$input = file("input6.txt");
global \$directly_orbits_map;

foreach(\$input as \$line){
\$line = explode(")", \$line);
\$directly_orbits_map[substr(\$line[1], 0, strlen(\$line[1])-1)] = \$line[0];
}

\$total = 0;
foreach (\$directly_orbits_map as \$orbiter => \$planet){
\$total += get_orbit_steps(\$orbiter, "COM");
}

echo "Part 1: total steps: \$total \n";

\$join = get_divergence_point();
\$path = get_orbit_steps(\$directly_orbits_map["YOU"], \$join) + get_orbit_steps(\$directly_orbits_map["SAN"], \$join);
echo "Part 2: path length: ".\$path;

function get_orbit_steps(\$orbiter, \$destination){
global \$directly_orbits_map;
if (\$directly_orbits_map[\$orbiter]==\$destination){
return 1;
}
return 1 + get_orbit_steps(\$directly_orbits_map[\$orbiter], \$destination);
}

function get_divergence_point(){
\$your_path = path_to_origin("YOU");
\$santa_path = path_to_origin("SAN");

foreach (\$your_path as \$planet){
if (in_array(\$planet, \$santa_path)){
return \$planet;
}
}
}

function path_to_origin(\$from){
global \$directly_orbits_map;

while (\$directly_orbits_map[\$from] != "COM"){
\$from = \$directly_orbits_map[\$from];
\$planets[] = \$from;
}
return \$planets;
}
``````

Yordi Verkroost

Solution for part two, in Elixir.

``````defmodule Aoc19.Day6b do
@moduledoc false

alias Aoc19.Utils.Common

def start(input_location) do
input_location
|> paths()
|> transfers("YOU", "SAN")
end

defp transfers(paths, object1, object2) do
path1 = Map.fetch!(paths, object1)
path2 = Map.fetch!(paths, object2)
set1 = MapSet.new(path1)
set2 = MapSet.new(path2)
intersection = MapSet.intersection(set1, set2)

intersection
|> Enum.map(&distances(&1, [path1, path2]))
|> Enum.min()
end

defp distances(object, paths) do
paths
|> Enum.map( fn path ->
path_distance(path, object, 0)
end)
|> Enum.sum()
end

defp path_distance([hd | _rest], object, length) when hd == object, do: length
defp path_distance([_hd | rest], object, length) do
path_distance(rest, object, length + 1)
end

defp paths(orbit_map) do
Map.new(orbit_map, fn {orbits, orbited} ->
{orbits,
orbited
|> walk([], orbit_map)
|> Enum.reverse()}
end)
end

defp walk(orbited, path, orbit_map) do
next_orbit? = Map.has_key?(orbit_map, orbited)
continue(next_orbit?, orbited, path, orbit_map)
end

defp continue(true, orbits, path, orbit_map) do
orbited = Map.fetch!(orbit_map, orbits)
walk(orbited, [orbits | path], orbit_map)
end

defp continue(false, orbited, path, _orbit_map), do: [orbited | path]

input_location
|> to_map()
end

defp to_map(input) do
Map.new(input, fn line ->
[orbited, orbits] = String.split(line, ")")
{orbits, orbited}
end)
end
end
``````

Here's part one

Einar Norðfjörð

Javascript solution w/ Graph implementation

``````Map.prototype.reduce = function(reducer, initialState) {
let state = initialState
for (entry of this.entries()) {
state = reducer(state, entry)
}
return state
}

Map.prototype.map = function(fn) {
return this.reduce((p, [key, value]) => {
p.set(key, fn(value))
return p
}, new Map())
}

class Graph {
constructor() {
}

}
}
toString() {
(p, [vertex, neighbors]) =>
p + '\n' + `\${vertex} -> \${neighbors.join(' ')}`
)
}

dfs(startingNode, reducer, initialState) {
const visited = this.adjacencyList.map(() => false)
return this.DFSUtil(startingNode, visited, reducer, initialState)
}

DFSUtil(vert, visited, reducer, state) {
state = reducer(state, vert)
visited.set(vert, true)

for (const neighbor of neighbors) {
if (!visited.get(neighbor))
state = this.DFSUtil(neighbor, visited, reducer, state)
}

return state
}

bfs(from, to, reducer, state) {
const queue = []
const visited = this.adjacencyList.map(() => false)

queue.push(from)
while (queue.length) {
const vertex = queue.shift()
for (const neighbor of neighbors) {
if (!visited.get(neighbor)) {
visited.set(neighbor, true)
state = reducer(state, neighbor, vertex)
queue.push(neighbor)

if (neighbor === to) {
return state
}
}
}
}
return false
}

shortestPath(from, to) {
const initialState = this.adjacencyList.map(() => ({
distance: Infinity,
predecessor: null
}))
initialState.get(from).distance = 0

const result = this.bfs(
from,
to,
(p, v, vertex) => {
const val = p.get(v)
val.distance = p.get(vertex).distance + 1
val.predecessor = vertex
return p
},
initialState
)

return result.get(to).distance
}

countIndirectOrbits() {
(sum, [key]) => sum + this.dfs(key, (a, b) => a + 1, -1),
0
)
}
}

const input = require('fs')
.toString()

const map = input.split('\n')
const orbits = map.map(x => x.split(')'))

const graph = new Graph()
const directedGraph = new Graph()

orbits.forEach(([orbitee, orbiter]) => {
})

console.log(directedGraph.toString())
console.log(directedGraph.countIndirectOrbits())
console.log(graph.shortestPath('YOU', 'SAN') - 2)

``````

Rizwan

Day dusted with swift

``````import Cocoa

func directAndImmediateOrbits(_ input: [String]) -> Int {
var orbits: [String : String] = [:]
input.forEach { (orbit) in
let pair = orbit.components(separatedBy: ")")
orbits[pair[1]] = pair[0]
}

let root = "COM"

func depthForNode(_ node: String) -> Int {
if node == root {
return 0
}
var total = 0
total = total + 1 + depthForNode(orbits[node]!)
}
depthForNode("COM")
var total = 0
orbits.keys.forEach { (key) in
total += depthForNode(key)
}
}

func orbitTransfersCount(_ input: [String], _ startAndEnd: (String,String)) -> Int {
var orbits: [String : String] = [:]
input.forEach { (orbit) in
let pair = orbit.components(separatedBy: ")")
orbits[pair[1]] = pair[0]
}

var parents : [String] = []
func depthToRoot(_ node: String,_ root: String = "COM") -> Int {
if node == root {
return 0
}
var total = 0
if let orbit = orbits[node] {
parents.append(orbit)
total = total + 1 + depthToRoot(orbit,root)
}
}

func ancestors(_ node: String) -> [String] {
parents.removeAll()
depthToRoot(node,"COM")
return parents
}

let p1 = ancestors(startAndEnd.0)
let p2 = ancestors(startAndEnd.1)

func getCommonParent(_ p1: [String], _ p2: [String]) -> String {
let commonParent: String = ""
for (index,p1) in p1.enumerated() {
for (index,p2) in p2.enumerated() {
if p1 == p2 {
return p1
}
}
}
return ""
}

let common = getCommonParent(p1, p2)
var total = depthToRoot(startAndEnd.0,common) + depthToRoot(startAndEnd.1,common) - 2
}

func testCase1() -> Int {
let input = """
COM)B
B)C
C)D
D)E
E)F
B)G
G)H
D)I
E)J
J)K
K)L
""".trimmingCharacters(in: .whitespacesAndNewlines).components(separatedBy: .newlines)
return directAndImmediateOrbits(input)
}

func testCase2() -> Int {
let 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
""".trimmingCharacters(in: .whitespacesAndNewlines).components(separatedBy: .newlines)
return orbitTransfersCount(input, ("YOU","SAN"))
}

func allTestCases() {
print(testCase1())
print(testCase2())
}

allTestCases()
func partOne() -> Int {
return directAndImmediateOrbits(input)
}

func partTwo() -> Int {
return orbitTransfersCount(input, ("YOU","SAN"))
}

print(partOne())
print(partTwo())
``````

Lots of recursive functions...

``````class Body():
def __init__(self, name, parent):
self.children = []
self.name = name
self.parent = parent

child_relationships = [orbit for orbit in orbits if orbit.startswith(body.name)]

for child_relationship in child_relationships:
orbits.remove(child_relationship)
child_name = child_relationship.split(')')[1]
child_body = Body(child_name, parent=body)
body.children.append(child_body)

def find_parent_body(node, body_name, result):
for child in node.children:
if child.name == body_name:
result.append(node)
else:
find_parent_body(child, body_name, result)  # Depth first search

def search_children(node, node_to_find_name, dist=0):
for child in node.children:
if child.name == node_to_find_name:
return dist
else:
result = search_children(child, node_to_find_name, dist+1)
if result is not None:
return result

def find_dist_to_node(parent_node, node_to_find_name):
result = search_children(parent_node, node_to_find_name)
if result is None:
return 1 + find_dist_to_node(parent_node.parent, node_to_find_name)
return result

if __name__ == '__main__':
orbits = [orbit for orbit in puzzle_input.split('\n') if orbit != '']
com = Body('COM', None)

result = []
find_parent_body(com, 'YOU', result)
you_parent = result[0]

print('Part 2 Solution')
print(find_dist_to_node(you_parent, 'SAN'))

``````

Matt Ellen-Tsivintzeli • Edited

Bit late to the party on this one. With good reason, but also I kept making mistakes with how to add up the jumps.

Got there eventually.

Part 2 first:

``````function orbitsToSanta()
{
let pretext = document.getElementsByTagName('pre')[0].innerHTML;
let orbits = pretext.split('\n').filter(o=>o!=='');
let orbithash = {};
let meorbit = '';
let sanorbit = '';

for(let orbit of orbits)
{
orbithash[orbit] = new leaf(orbit);
}

for(let orbit of orbits)
{
let [main, sub] = orbit.split(')');
if(sub === 'YOU')
{
meorbit = orbit;
}
if(sub === 'SAN')
{
sanorbit = orbit;
}
let parent = orbits.filter(oo =>
{
let [othermain, othersub] = oo.split(')');
return main === othersub;
})[0];
if(typeof(parent) !== 'undefined')//root node has no parent.
{
orbithash[orbit].parent = orbithash[parent];
}
}

let melist = orbithash[meorbit].listOrbits();
let sanlist = orbithash[sanorbit].listOrbits();
// hco is Highest Common Orbit
let hco = melist.filter(o => sanlist.indexOf(o) > -1).slice(-1)[0];
let hcolist = orbithash[hco].listOrbits();

let melength = melist.filter(l => hcolist.indexOf(l) === -1).length - 1; // minus 1 because you exclude the current orbit.
let sanlength = sanlist.filter(l => hcolist.indexOf(l) === -1).length - 1; // minus 1 because the hco is already counted.

return melength+sanlength;
}

function leaf(orbit)
{
this.orbit = orbit;
this.parent = null;
}

leaf.prototype.orbitCounts = function()
{
let count = 1;

if(this.parent !== null)
{
count = 1 + this.parent.orbitCounts();
}

return count;
};

leaf.prototype.listOrbits = function()
{
if(this.parent === null)
{
return [];
}

let pos = this.parent.listOrbits();

pos.push(this.orbit);

return pos;
};
``````

Part 1 had the following code in place of the number of jumps calculation:

``````    let counts = 0;

for(let orbit of orbits)
{
counts += orbithash[orbit].orbitCounts();
}

return counts;
``````

Bruno Raoult

Late here, but as I am doing 2019 AOC now (yes, nearly 3 years later), and I noticed there was no `C` solution for this one here, I have one here.
Nothing special there, as the two parts are trivial after the tree has been built, and you get a way to find existing nodes by name (mainly to build tree). For that, instead of an usual hash-table, I decided to go for a `trie` structure. Don't ask me why ;-)