Day 6: Universal Orbit Map

#!/usr/bin/awk -f
{
    split($0, map, ")")
    orbits[map[2]] = map[1]
}

END {
    for (i in orbits)
        for (;;)
            if (orbits[i]) {
                i = orbits[i]
                total += 1
            } else {
                break
            }

    print total
}

#!/usr/bin/awk -f
{
    split($0, map, ")")
    orbits[map[2]] = map[1]
}

END {
    i = orbits["SAN"]
    for (j = 0; j < 2; ++j) {
        for (;;)
            if (orbits[i]) {
                i = orbits[i]
                total += 1

                if (transfers[i]) {
                    total += transfers[i]
                    break
                } else {
                    transfers[i] += total
                }
            } else {
                break
            }

        if (! j) {
            total = 0
            i = orbits["YOU"]
        }
    }

    print total
}

use std::error::Error;
use std::fs::File;
use std::io::prelude::*;
use std::path::Path;
use indexmap::IndexMap;

pub fn day6a() {
    let path = Path::new("data/day6.txt");
    let display = path.display();

    let mut file = match File::open(&path) {
        Err(why) => panic!("Couldn't open {}: {}", display, why.description()),
        Ok(file) => file,
    };

    let mut s = String::new();
    match file.read_to_string(&mut s) {
        Err(why) => panic!("Couldn't read {}: {}", display, why.description()),
        Ok(_) => {}
    }

    let mut nodes: IndexMap<&str, usize> = IndexMap::new();
    let mut edges: Vec<(usize, usize)> = vec![];
    for line in s.lines() {
        let parts: Vec<&str> = line.split(")").collect();
        if !nodes.contains_key(parts[0]) {
            nodes.insert(parts[0], 0);
        }
        let index1 = nodes.get_full(parts[0]).unwrap().0;
        if !nodes.contains_key(parts[1]) {
            nodes.insert(parts[1], 0);
        }
        let index2 = nodes.get_full(parts[1]).unwrap().0;
        edges.push((index1, index2));
    }

    let root = nodes.get_full("COM").unwrap().0;
    let mut to_scan = vec![root];
    while to_scan.len() > 0 {
        let node_index = to_scan.pop().unwrap();
        let node_value = *nodes.get_index(node_index).unwrap().1;
        for edge in &edges {
            if edge.0 == node_index {
                to_scan.push(edge.1);
                let x = nodes.get_index_mut(edge.1).unwrap().1;
                *x = node_value + 1;
            }
        }
    }

    let mut count = 0;
    for node in &nodes {
        count += node.1
    }

    println!("{}", count);
}

use std::error::Error;
use std::fs::File;
use std::io::prelude::*;
use std::path::Path;
use indexmap::IndexMap;
use std::collections::HashSet;

pub fn day6b() {
    let path = Path::new("data/day6.txt");
    let display = path.display();

    let mut file = match File::open(&path) {
        Err(why) => panic!("Couldn't open {}: {}", display, why.description()),
        Ok(file) => file,
    };

    let mut s = String::new();
    match file.read_to_string(&mut s) {
        Err(why) => panic!("Couldn't read {}: {}", display, why.description()),
        Ok(_) => {}
    }

    let mut nodes: IndexMap<&str, usize> = IndexMap::new();
    let mut edges: Vec<(usize, usize)> = vec![];
    for line in s.lines() {
        let parts: Vec<&str> = line.split(")").collect();
        if !nodes.contains_key(parts[0]) {
            nodes.insert(parts[0], 0);
        }
        let index1 = nodes.get_full(parts[0]).unwrap().0;
        if !nodes.contains_key(parts[1]) {
            nodes.insert(parts[1], 0);
        }
        let index2 = nodes.get_full(parts[1]).unwrap().0;
        edges.push((index1, index2));
    }

    let get_path = |start: usize, end: usize| {
        let mut current = start;
        let mut ret: HashSet<usize> = HashSet::new();
        ret.insert(current);
        while current != end {
            for edge in &edges {
                if edge.1 == current {
                    current = edge.0;
                    break;
                }
            }
            ret.insert(current);
        }
        ret
    };

    let you_path = get_path(nodes.get_full("YOU").unwrap().0, nodes.get_full("COM").unwrap().0);
    let san_path = get_path(nodes.get_full("SAN").unwrap().0, nodes.get_full("COM").unwrap().0);

    println!("{}", you_path.symmetric_difference(&san_path).count() - 2);
}

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int MN = 100000;
map<string,int> ms;
vvi g;
int dp[MN];
int get(string& s) {
	int sz = ms.size();
	if(ms.find(s) == ms.end()) {
		ms[s] = sz;
		return sz;
	}
	return ms[s];
}
int det(int u) {
	if(dp[u] != -1) return dp[u];
	int res = 0;
	for(int i=0;i<g[u].size();i++) {
		int v = g[u][i];
		res += det(v)+1;
	}
	return dp[u] = res;
}
int main() {
	string s;
	g.assign(MN,vi());
	memset(dp,-1,sizeof(dp));
	while(cin >> s) {
		int pos = s.find(')');
		string a = s.substr(0,pos);
		string b = s.substr(pos+1,s.size()-pos-1);
		int u = get(a),v = get(b);
		g[u].push_back(v);
	}

	int tot = 0;
	for(int i=0;i<ms.size();i++) {
		tot += det(i);
	}
	cout << tot << '\n';
}

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int MN = 100000;
map<string,int> ms;
vvi g;
int get(string& s) {
	int sz = ms.size();
	if(ms.find(s) == ms.end()) {
		ms[s] = sz;
		return sz;
	}
	return ms[s];
}
int dist[MN];
int main() {
	string s;
	g.assign(MN,vi());
	memset(dist,-1,sizeof(dist));
	while(cin >> s) {
		int pos = s.find(')');
		string a = s.substr(0,pos);
		string b = s.substr(pos+1,s.size()-pos-1);
		int u = get(a),v = get(b);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	string S = "YOU",T = "SAN";
	int st = get(S),ed = get(T);
	queue<int> q;
	q.push(st);
	dist[st] = 0;
	while(!q.empty()) {
		int u = q.front();q.pop();
		for(int i=0;i<g[u].size();i++) {
			int v = g[u][i];
			if(dist[v] != -1) continue;
			dist[v] = dist[u]+1;
			q.push(v);
		}
	}
	cout << dist[ed]-2 << '\n';
}

Then for Part 2 I built a function that recursively finds the path between a given planet and 'COM' and then provides that as a list. I took that list for 'YOU' and 'SAN' and looked for which parts of the path were shared.

The last element on the shared list is node they both have to go through, so some quick distance calculations (distance 'YOU' vs distance 'SAN' vs distance SHARED) and a minor correction for distance of you vs distance of what you're orbiting and I had the answer

input_string_list = input_string.split('\n')[:-1]
#print(input_string_list)

planets = {}
planet_distances = {}

for relationship in input_string_list:
    host, satellite = relationship.split(')')
    if host in planets.keys():
        planets[host].append(satellite)
    else:
        planets[host] = [satellite]
    if satellite not in planets.keys():
        planets[satellite] = []

def traverse_planets(host, distance):
    planet_distances[host] = distance
    for satellite in planets[host]:
        traverse_planets(satellite, distance + 1)
        
def path_to_com(origin):
    if origin == 'COM':
        return ['COM']
    else:
        for planet in planets.keys():
            if origin in planets[planet]:
                #I'm orbitting 'planet'
                #print(planet)
                #print(origin)
                return path_to_com(planet) + [origin]
def intersection(lst1, lst2): 
    lst3 = [value for value in lst1 if value in lst2] 
    return lst3 

traverse_planets('COM',0)

my_path = path_to_com('YOU')
san_path = path_to_com('SAN')

shared_path = intersection(my_path, san_path)

print(my_path)
print(san_path)

print(shared_path)

print(f"My Path Distance: {planet_distances['YOU']}")
print(f"Santa Path Distance: {planet_distances['SAN']}")
print(f"Shared Path Distance: {planet_distances[shared_path[-1]]}")
      
print(f"My Distance to Shared: {planet_distances['YOU'] - planet_distances[shared_path[-1]]}")
print(f"Santa Distance to Shared: {planet_distances['SAN'] - planet_distances[shared_path[-1]]}")

  def solution_part1(filename) do
    loadinput(filename)
    |> parse_orbits
    |> start_walk
    |> List.flatten()
    |> Enum.sum()
  end

  defp loadinput(filename) do
    File.read!(filename)
    |> String.split("\n")
    |> Enum.map(&String.split(&1, "\)"))
  end

  # Part 1

  # Map objects to their orbiters
  defp parse_orbits(orbit_list) do
    map = %{}

    Enum.reduce(orbit_list, map, fn orbit, map_acc ->
      insert_orbit_to_map(map_acc, orbit)
    end)
  end

  defp insert_orbit_to_map(map, orbit) do
    object = Enum.at(orbit, 0)
    orbiter = Enum.at(orbit, 1)
    # Add orbiter to the list of object's orbiters,
    # and create new list if it's the first
    Map.put(map, object, [orbiter | Map.get(map, object, [])])
  end

  defp start_walk(map) do
    walk_and_count(map["COM"], map, 0)
  end

  defp walk_and_count(orbiters, _, _depth)
       when orbiters == [] do
    []
  end

  # For every orbiting object, mark its depth, and recurse deeper
  defp walk_and_count(orbiters, map, depth) do
    Enum.map(orbiters, fn orbiter ->
      orbiters_of_orbiter = Map.get(map, orbiter, [])
      depth = depth + 1

      [depth, walk_and_count(orbiters_of_orbiter, map, depth)]
    end)
  end

  def solution_part2(filename) do
    loadinput(filename)
    |> find_santa()
  end

  # Map every orbiting object to its parent
  defp parse_reverse_orbits(orbit_list) do
    map = %{}

    Enum.reduce(orbit_list, map, fn orbit, acc ->
      key = Enum.at(orbit, 1)
      value = Enum.at(orbit, 0)
      Map.put(acc, key, value)
    end)
  end

  defp find_santa(list) do
    map_rise = parse_reverse_orbits(list)

    # For both objects, find the path to COM.
    santa = path_upwards(map_rise, "SAN", [])
    you = path_upwards(map_rise, "YOU", [])

    weave_paths(santa, you)
  end

  defp path_upwards(_, current, path)
       when current == nil do
    path
  end

  defp path_upwards(map_rise, current, path) do
    com = Map.get(map_rise, current, nil)
    path_upwards(map_rise, com, [current | path])
  end

  defp weave_paths(santa, you) do
    # Drop the parts that are common to both,
    # to find the unique parts
    if hd(santa) == hd(you) do
      weave_paths(tl(santa), tl(you))
    else
      # Finally, sum the lengths of the unique parts
      length(you) + length(santa) - 2
    end
  end

class OrbitObject(object):

    def __init__(self, orbits=[], orbiters=[], id=""):

        self.orbits = orbits
        self.orbiters = orbiters
        self.id = id

def read_map(file_name):

    with open(file_name, 'r') as fid:
        data = fid.readlines()

    for idx in range(len(data)):
        data[idx] = data[idx].strip().split(')')

    return data

def find_root_id(map):

    # Find the root of the tree. Apparently this didn't need to be general but
    # it is now!
    roots = [item[0] for item in map]
    leaves = [item[1] for item in map]

    for item in roots:
        if item not in leaves:
            return item

    raise ValueError("Tree has no root!")

def map_to_tree(map, root=None):

    if root is None:
        root_id = find_root_id(map)

        root = OrbitObject([], [], root_id)

    root_orbiters = [item[1] for item in map if item[0] == root.id]

    for orbiter in root_orbiters:
        new_orbiter = OrbitObject(root, [], orbiter)
        root.orbiters.append(new_orbiter)
        map_to_tree(map, new_orbiter)

    return root

def total_orbits(root, depth=1):

    orbit_sum = 0
    orbit_sum += (len(root.orbiters) * depth)

    for orbiter in root.orbiters:
        orbit_sum += total_orbits(orbiter, depth + 1)

    return orbit_sum

def find_path_by_id(root, id, path=[]):

    if root.id == id:
        return 1
    else:
        if len(path) == 0:
            path.insert(0, root)
        for orbiter in root.orbiters:
            find = find_path_by_id(orbiter, id, path)
            if find is not None:
                path.insert(1, orbiter)
                return path

    return None

def dist_between(root, id_1, id_2):

    first_path = find_path_by_id(root, id_1, [])
    second_path = find_path_by_id(root, id_2, [])

    for idx in range(len(first_path)):
        if first_path[idx].id == second_path[idx].id:
            continue
        else:
            pivot_num = idx
            break

    dist = len(first_path[pivot_num:]) + len(second_path[pivot_num:]) - 2
    return dist

input_file = "PuzzleInput.txt"

input_map = read_map(input_file)

root = map_to_tree(input_map)

num_orbits = total_orbits(root)

print(num_orbits)

transfers = dist_between(root, "YOU", "SAN")

print(transfers)

let input =
  Utils.read_lines ~path:"input"
  |> List.map (fun line ->
         Scanf.sscanf line "%s@)%s" (fun pre post -> (post, pre)))

module StringMap = Map.Make (String)
module StringSet = Set.Make (String)

let rec count_orbits acc orbit_map = function
  | "COM" -> acc
  | corpus -> count_orbits (1 + acc) orbit_map (StringMap.find corpus orbit_map)

let rec full_path acc orbit_map = function
  | "COM" -> acc
  | corpus ->
      full_path (StringSet.add corpus acc) orbit_map
        (StringMap.find corpus orbit_map)

let path_to corpus orbits =
  full_path StringSet.empty orbits (StringMap.find corpus orbits)

let () =
  let orbits_around = input |> List.to_seq |> StringMap.of_seq in

  let orbits_length =
    StringMap.map (count_orbits 1 orbits_around) orbits_around
  in

  let n_orbits = StringMap.fold (fun _ acc k -> acc + k) orbits_length 0 in

  let path_to_you = path_to "YOU" orbits_around in
  let path_to_san = path_to "SAN" orbits_around in

  let n_transfers =
    StringSet.cardinal (StringSet.diff path_to_you path_to_san)
    + StringSet.cardinal (StringSet.diff path_to_san path_to_you)
  in

  Printf.printf "Part 1: %u\n" n_orbits;
  Printf.printf "Part 2: %u\n" n_transfers

package d06

import (
	"regexp"
	"strings"

	"github.com/jzimbel/adventofcode-go/solutions"
)

// intermediate data structure to make building the tree easier
type orbitMap map[string][]string

// standard tree structure with awareness of its parent and depth from the root
type tree struct {
	label    string
	depth    uint
	parent   *tree
	children []*tree
}

// allows for fast access to any node in a tree by its label
type flatTree map[string]*tree

const (
	centerOfMass string = "COM"
	you          string = "YOU"
	santa        string = "SAN"
)

var pattern = regexp.MustCompile(`(.+)\)(.+)`)

// makeFlatTree creates a flatTree that points to nodes in an underlying tree.
func makeFlatTree(om orbitMap) flatTree {
	ft := make(flatTree, len(om))

	var buildTree func(string, uint, *tree) *tree
	buildTree = func(label string, depth uint, parent *tree) *tree {
		t := tree{
			label:    label,
			children: make([]*tree, 0, len(om[label])),
			depth:    depth,
			parent:   parent,
		}
		for i := range om[label] {
			t.children = append(t.children, buildTree(om[label][i], depth+1, &t))
		}
		ft[label] = &t
		return &t
	}

	buildTree(centerOfMass, 0, nil)
	return ft
}

func (ft flatTree) sumDepths() (count uint) {
	for _, t := range ft {
		count += t.depth
	}
	return
}

func (t *tree) getAncestors() []*tree {
	ancestors := make([]*tree, t.depth)
	current := t
	for i := uint(0); i < t.depth; i++ {
		current = current.parent
		ancestors[i] = current
	}
	return ancestors
}

func getCommonAncestor(t1 *tree, t2 *tree) (common *tree) {
	ancestors1 := t1.getAncestors()
	ancestors2 := t2.getAncestors()

	// put the second list of ancestors into a set for faster existence checking between the two lists
	compareSet := make(map[*tree]struct{}, len(ancestors2))
	for _, ancestor := range ancestors2 {
		compareSet[ancestor] = struct{}{}
	}
	for _, ancestor := range ancestors1 {
		if _, ok := compareSet[ancestor]; ok {
			common = ancestor
			break
		}
	}
	return
}

func parseInput(input string) (om orbitMap) {
	lines := strings.Split(input, "\n")
	om = make(orbitMap, len(lines))
	for _, line := range lines {
		matches := pattern.FindStringSubmatch(line)
		base, satellite := matches[1], matches[2]
		if _, ok := om[base]; ok {
			om[base] = append(om[base], satellite)
		} else {
			om[base] = []string{satellite}
		}
	}
	return
}

func part1(ft flatTree) uint {
	return ft.sumDepths()
}

func part2(ft flatTree) uint {
	common := getCommonAncestor(ft[you].parent, ft[santa].parent)
	return (ft[you].parent.depth - common.depth) + (ft[santa].parent.depth - common.depth)
}

// Solve provides the day 6 puzzle solution.
func Solve(input string) (*solutions.Solution, error) {
	ft := makeFlatTree(parseInput(input))
	return &solutions.Solution{Part1: part1(ft), Part2: part2(ft)}, nil
}

#!/usr/bin/env crystal

class Node
  property name : String
  property parent : Node | Nil

  def initialize(name, parent)
    @parent = parent
    @name = name
  end

  def is_root?
    parent == nil
  end

  def to_s
    name
  end

  # get depth to root
  def get_depth
    get_ancestors.size
  end

  def get_ancestors
    if is_root?
      [] of Node
    else
      parents = [] of Node

      p = parent
      while p != nil
        parents << p if p
        p = p.parent if p
      end

      parents
    end
  end
end

def find_or_make_node(map, name)
  if ! map.has_key? name
    map[name] = Node.new(name, nil)
  end
  map[name]
end

def find_common_parent(map, node1, node2)
  node1_ps = node1.get_ancestors
  node2_ps = node2.get_ancestors

  common = node1_ps & node2_ps
  common.sort_by { |n| n.get_depth }

  common.first
end

# Build our map

nodes = {} of String => Node
nodes["COM"] = Node.new("COM", nil)

input = ARGV.size > 0 ? ARGV[0] : "day6/input.txt"
File.read_lines(input).each do |line|
  n1, n2 = line.split(")").map{ |n| n.strip }
  node1 = find_or_make_node(nodes, n1)
  node2 = find_or_make_node(nodes, n2)
  node2.parent = node1
end

# Part 1, find and sum the depth of each node
puts "Part 1"
puts nodes.values.reduce(0) { |sum, node| sum + node.get_depth }

# Part 2, find the distance between YOU and SAN
puts "Part 2"
common = find_common_parent(nodes, nodes["YOU"], nodes["SAN"])
path_dist = (nodes["YOU"].get_depth - common.get_depth) + (nodes["SAN"].get_depth - common.get_depth)
puts path_dist-2 # subtract two since we're counting *transfers*, we don't
                 # "transfer" from our start/end nodes

const fs = require('fs');
const R = require('ramda');
const m = fs.readFileSync('input.txt').toString().split('\n')

// Generate nodes
const generateObjects = array => {
    const nodes = R.flatten(array.map(x => x.split(')')));
    const orbits = [...new Set([...nodes])].map(x => {
        return { node: x, children: [], parent: '' };
    });

    for (let i = 0; i < array.length; i++) {
        const [parent, child] = array[i].split(')');
    
        orbits.find(x => {
            if (x.node === parent) {
                x.children.push(child);
            } else if (x.node === child) {
                x.parent = parent;
            }
        });
    }

    return orbits;
}

// Takes an array of nodes and returns the total number of orbits
const findOrbits = array => {
    let orbits = 0;

    const recurse = (object, array) => {
        if (object.parent !== '') {
            orbits++;
            return recurse(array.find(x => x.node === object.parent), array);
        } else {
            return;
        }
    }

    array.forEach(x => recurse(x, array));

    return orbits;
}

const objects = generateObjects(m);
const totalOrbits = findOrbits(objects);
console.log(`Total orbits: ${totalOrbits}`);

const fs = require('fs');
const R = require('ramda');
const m = fs.readFileSync('input.txt').toString().split('\n')

// Generate nodes
const generateObjects = array => {
    const nodes = R.flatten(array.map(x => x.split(')')));
    const orbits = [...new Set([...nodes])].map(x => {
        return { node: x, children: [], parent: '' };
    });

    for (let i = 0; i < array.length; i++) {
        const [parent, child] = array[i].split(')');
    
        orbits.find(x => {
            if (x.node === parent) {
                x.children.push(child);
            } else if (x.node === child) {
                x.parent = parent;
            }
        });
    }

    return orbits;
}

// Takes a node and returns an array of ordered nodes to root parent
const traverse = (node, array) => {
    let nodes = [];
    const index = array.findIndex(x => x.node === node);

    const recurse = (object, array) => {
        if (object.parent !== '') {
            nodes.push(object.node);
            return recurse(array.find(x => x.node === object.parent), array);
        } else {
            nodes.push(object.node);
        }
    }

    recurse(array[index], array);

    return nodes;
}

// Takes two points and an input and returns a distance
const findDistance = (a, b, input) => {
    const x = traverse(a, input);
    const y = traverse(b, input);
    const intersection = R.head(R.intersection(x, y));

    return [...x.slice(1, x.findIndex(x => x === intersection)), ...y.slice(1, y.findIndex(x => x === intersection)).reverse()].length;
}

const objects = generateObjects(m);
const distance = findDistance('SAN', 'YOU', objects);

console.log(`Minimum number of orbital transfers required: ${distance}`);