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

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

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

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

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

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

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

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

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

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

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)}')

/// 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))
}

    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
    }

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
    }

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

<?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;
}

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