DEV Community

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

Jon Bristow on December 06, 2019

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 ...

Read full post

Massimo Artizzu • Dec 6 '19 • 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 • Dec 6 '19

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 • Dec 6 '19

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 • Dec 6 '19

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 • Dec 6 '19 • 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 • Dec 6 '19 • 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 • Dec 6 '19

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!
(Full code: github.com/jkoenig134/AdventOfCode...)

Jon Bristow • Dec 6 '19

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 • Dec 6 '19 • Edited

Oh, I will definitely look into that, thanks for the suggestion.
I only knew about (tree-seq),
I'm still a newbie in clj.

Jon Bristow • Dec 7 '19

Zipper is extremely powerful for navigating trees efficiently.

It’s also as easy to read as overly point free Haskell.

Johnny • Dec 7 '19

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 • Dec 6 '19 • 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 • Dec 6 '19 • 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 • Dec 7 '19

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
        objects.add(to_orbit)
        objects.add(orbiter)

    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 • Dec 10 '19

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::io::BufReader;
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 buf = BufReader::new(File::open("data/day6.txt").unwrap());
    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 • Dec 6 '19

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 • Dec 6 '19 • 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 {

        return Files.readAllLines(Paths.get(FILENAME))
            .map(::parseOrbit).fold(mutableMapOf<String, MutableSet<String>>()) { m, (a, b) ->
                val nset = (m[a] ?: mutableSetOf())
                nset.add(b)
                m[a] = nset
                m
            }.countChildren()
    }

    fun part2(): Int {
        val paths = Files.readAllLines(Paths.get(FILENAME))
            .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 • Dec 6 '19

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 part1() = Files.readAllLines(Paths.get(FILENAME)).countPaths()

    fun part2(): Int = Files.readAllLines(Paths.get(FILENAME)).shortestDistanceToSanta()

}


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

Stephanie Hope • Dec 6 '19

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 • Dec 6 '19

Solution for part two, in Elixir.

defmodule Aoc19.Day6b do
  @moduledoc false

  alias Aoc19.Utils.Common

  def start(input_location) do
    input_location
    |> read()
    |> 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]

  defp read(input_location) do
    input_location
    |> Common.read_lines()
    |> 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ð • Dec 6 '19

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() {
    this.adjacencyList = new Map()
  }

  addDirectedEdge(v, w) {
    if (!this.adjacencyList.get(v)) this.adjacencyList.set(v, [])
    if (!this.adjacencyList.get(w)) this.adjacencyList.set(w, [])
    this.adjacencyList.get(v).push(w)
  }
  addEdge(v, w) {
    if (!this.adjacencyList.get(v)) this.adjacencyList.set(v, [])
    if (!this.adjacencyList.get(w)) this.adjacencyList.set(w, [])
    this.adjacencyList.get(v).push(w)
    this.adjacencyList.get(w).push(v)
  }
  toString() {
    return this.adjacencyList.reduce(
      (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)

    const neighbors = this.adjacencyList.get(vert)

    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()
      const neighbors = this.adjacencyList.get(vertex)
      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() {
    return this.adjacencyList.reduce(
      (sum, [key]) => sum + this.dfs(key, (a, b) => a + 1, -1),
      0
    )
  }
}

const input = require('fs')
  .readFileSync(0)
  .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]) => {
  graph.addEdge(orbiter, orbitee)
  directedGraph.addDirectedEdge(orbiter, orbitee)
})

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

Rizwan • Dec 6 '19

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]!)
        return total
    }
    depthForNode("COM")
    var total = 0
    orbits.keys.forEach { (key) in
        total += depthForNode(key)
    }
    return total
}

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)
        }
        return total
    }

    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
    return total
}


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())

Chad S • Dec 9 '19 • Edited

A Python solution (also see github.com/devChad/advent_of_code)

Lots of recursive functions...

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


def add_children_to_body(body, orbits):
    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)
        add_children_to_body(child_body, orbits)


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)
    add_children_to_body(com, orbits)

    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 • Dec 7 '19 • 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 • Oct 1 '22

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 ;-)

Thibaut Patel • Dec 12 '19

A javascript walkthrough. I was happy to have coded the part 1 in a clean way because it helped me a ton for the part 2!