Advent of Code 2019 - Day 6

Today's problem was about finding paths in a graph of orbits.

The first part was easily solvable using some recursion to get the total number of direct and indirect connections. The second part was to find the distance between two specific orbits.

Code

fn get_tree(input: &str) -> HashMap<String, String> {
    let mut tree: HashMap<String, String> = HashMap::new();
    for orbit in input.lines() {
        let parts: Vec<String> = orbit.split(')').map(String::from).collect();
        let b = &parts[0];
        let a = &parts[1];

        tree.insert(a.to_string(), b.to_string());
    }
    tree
}

fn get_orbits(tree: &HashMap<String, String>, key: String) -> i32 {
    if tree.contains_key(&key) {
        return get_orbits(&tree, tree.get(&key).unwrap().clone()) + 1;
    }

    0
}

fn get_path(tree: &HashMap<String, String>, key: String) -> HashSet<String> {
    let mut path = HashSet::new();

    let mut child = key;
    loop {
        let parent = tree.get(&child).unwrap().clone();
        if parent == "COM" {
            break;
        }

        path.insert(parent.clone());
        child = parent;
    }

    path
}

pub fn part_one(input: &str) -> i32 {
    let tree = get_tree(input);
    tree.iter()
        .map(|(k, _)| get_orbits(&tree, k.to_owned()))
        .sum()
}

pub fn part_two(input: &str) -> i32 {
    let tree = get_tree(input);
    let a = get_path(&tree, "YOU".to_owned());
    let b = get_path(&tree, "SAN".to_owned());
    a.union(&b)
        .filter(|v| !(a.contains(v.clone()) && b.contains(v.clone())))
        .count() as i32
}

Benchmarks

2019 - Day 06 - Part 1 time: 10.391697ms
2019 - Day 06 - Part 2 time: 384.626µs

Feedback or Questions?

I don't have a direct way to leave comments on posts. But if you want to give some feedback or have some questions you can contact in other ways.