5
\$\begingroup\$

I am doing Advent of Code 2019 in order to learn Rust (it's been fun, but challenging!).

I am looking for help and feedback from more experiences Rustaceans on my solution to Day 6: Universal Orbit Map in Rust.

Specifically I am looking to see where I am not doing it the idiomatic Rust way, where my Java background shines through or anything that doesn't look or feel right or Rust-ish.

use std::collections::HashMap;
use std::io;
use std::io::Read;

fn main() {
    let mut input = String::new();
    match io::stdin().read_to_string(&mut input) {
        Ok(v) => v,
        Err(_) => panic!("Unable to read input"),
    };
    let mut orbits = HashMap::new();
    input
        .lines()
        .map(|l| l.split(")").collect::<Vec<&str>>())
        .for_each(|o| {
            orbits.insert(o[1].to_string(), o[0].to_string());
        });
    let num_orbits = orbits
        .iter()
        .map(|k| path(k.0, &orbits))
        .map(|p| p.len())
        .sum::<usize>();

    let mut you_path = path("YOU", &orbits);
    let mut san_path = path("SAN", &orbits);

    while you_path.get(you_path.len() - 1) == san_path.get(san_path.len() - 1) {
        you_path.pop();
        san_path.pop();
    }

    println!(
        "Number of orbits: {}, Number of jumps: {}",
        num_orbits,
        (you_path.len() + san_path.len())
    );
}

fn path(from: &str, orbits: &HashMap<String, String>) -> Vec<String> {
    let mut p = Vec::new();
    let mut inner = from;
    loop {
        match orbits.get(inner) {
            Some(v) => {
                p.push(v.to_string());
                inner = v;
            }
            None => break,
        };
    }
    p
}
\$\endgroup\$
1
\$\begingroup\$
fn main() {
    let mut input = String::new();
    match io::stdin().read_to_string(&mut input) {
        Ok(v) => v,
        Err(_) => panic!("Unable to read input"),
    };

If you are just going to panic, use unwrap or expect method on Result.

    let mut orbits = HashMap::new();
    input
        .lines()
        .map(|l| l.split(")").collect::<Vec<&str>>())
        .for_each(|o| {
            orbits.insert(o[1].to_string(), o[0].to_string());
        });

I'd do:

    let mut orbits : HashMap<_,_> = input
        .lines()
        .map(|l| l.split(")").collect::<Vec<&str>>())
        .map(|o| {
            (o[1].to_string(), o[0].to_string())
        })
        .collect();

You can collect() into many things including hashmaps.

    let num_orbits = orbits
        .iter()
        .map(|k| path(k.0, &orbits))
        .map(|p| p.len())
        .sum::<usize>();

I generally prefer to put the variable on the let: let num_orbits: usize, instead of in the ::<>

    let mut you_path = path("YOU", &orbits);
    let mut san_path = path("SAN", &orbits);

    while you_path.get(you_path.len() - 1) == san_path.get(san_path.len() - 1) {
        you_path.pop();
        san_path.pop();
    }

There is a last() method that you can use here insetad of the .get()

    println!(
        "Number of orbits: {}, Number of jumps: {}",
        num_orbits,
        (you_path.len() + san_path.len())
    );
}

fn path(from: &str, orbits: &HashMap<String, String>) -> Vec<String> {

You could have all of this operate on &str if you use lifetimes, but thats a little more advanced.

    let mut p = Vec::new();
    let mut inner = from;
    loop {
        match orbits.get(inner) {
            Some(v) => {

Use while let Some(v) = orbits.get(inner) {. This will loop until orbits.get returns None.

                p.push(v.to_string());
                inner = v;
            }
            None => break,
        };
    }
    p
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks! That’s very helpful and generous! \$\endgroup\$ – saidaspen Dec 11 '19 at 4:22
4
\$\begingroup\$

Disclaimer: I don't know Rust.

I only have comments on performance.

To compute the number of orbits, it's unnecessary to compute paths, you could compute just the length of paths. That would reduce the space complexity to constant.

When computing the number of orbits, instead of going from each planet until the root, you could go from the root, traversing paths to every planet exactly once. That would reduce the time complexity to linear.

When computing the common ancestor from SAN and YOU, you only need to track part of the path segments, until a common point.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.