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

View post

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