Exploring a shipping puzzle, part 2

← Back to Kevin's homepagePublished: 2018 November 9Last updated: 2018 November 12

Puzzling with friends

After posting the shipping puzzle I heard from several friends:

Rust solution(s)

My Rust solution was a simple port of my second Clojure solution. The only major difference is that it takes advantage of mutability (which is idiomatic in Rust, unlike in Clojure).

The Rust solution runs in about 4.22 ± 0.05 ms, or about 5x faster than the fast Clojure solution.

Honestly, I was surprised that it wasn’t even faster — I expected that between mutability and all of the extra compile-time size information, Rust would have been even further ahead. This is a testament to Clojure’s awesome data structures and the JVM’s just-in-time compiler.

After some thought on these performance differences, I realized that Clojure’s immutable semantics gave it an advantage: It could pervasively share data rather than copying.

Once I realized this, I modified my Rust solution to use references (rather than owned values), to reduce copying. This yielded another 2x speedup: 1.87 ± 0.01 ms.

Here’s that latter solution (which is essentially the same as my initial one; except with &Leg instead of Leg and the necessary <'a> lifetime annotations everywhere):

use std::collections::HashMap;
use std::fs::File;
use std::io::prelude::*;
use std::io::BufReader;

//Little helper for printing things out
pub fn p<T>(x: T)
where
    T: std::fmt::Debug,
{
    println!("{:?}", x);
}

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy)]
enum Day {
    M,
    T,
    W,
    R,
    F,
}
//Save ourselves some typing
use Day::*;

type City = String;

#[derive(Debug, Clone)]
pub struct Leg {
    start: City,
    end: City,
    dow: Day,
}

#[derive(Debug)]
pub struct Route<'a> {
    legs: Vec<&'a Leg>,
}

impl<'a> Route<'a> {
    fn new(l: &Leg) -> Route {
        Route { legs: vec![l] }
    }
    fn add_leg(&mut self, l: &'a Leg) {
        self.legs.push(l);
    }
}

pub fn read_legs<P: AsRef<std::path::Path>>(path: P) -> Vec<Leg> {
    let f = BufReader::new(File::open(path).unwrap());
    f.lines()
        .map(|l| l.unwrap())
        .map(|l| {
            let vals: Vec<&str> = l.split(" ").collect();
            Leg {
                start: vals[1].to_string(),
                end: vals[2].to_string(),
                dow: match vals[3] {
                    "M" => Day::M,
                    "T" => Day::T,
                    "W" => Day::W,
                    "R" => Day::R,
                    "F" => Day::F,
                    _ => panic!("Invalid day found: {}", vals[3]),
                },
            }
        }).collect()
}

pub fn assemble_routes(legs: &[Leg]) -> Vec<Route> {
    let mut legs_by_dow: HashMap<Day, Vec<&Leg>> = HashMap::new();
    for l in legs {
        legs_by_dow.entry(l.dow).or_insert_with(|| vec![]).push(&l);
    }

    let mut finished_routes: Vec<Route> = vec![];
    let mut routes_by_position: HashMap<&City, Vec<Route>> = HashMap::new();

    for dow in vec![M, T, W, R, F] {
        let mut extended_routes_by_position: HashMap<&City, Vec<Route>> = HashMap::new();

        for l in legs_by_dow.remove(&dow).unwrap() {
            //Either add this leg to an existing route, or create a new one
            let r =
                if let Some(mut r) = routes_by_position.get_mut(&l.start).and_then(|rs| rs.pop()) {
                    r.add_leg(&l);
                    r
                } else {
                    Route::new(&l)
                };

            extended_routes_by_position
                .entry(&l.end)
                .or_insert_with(|| vec![])
                .push(r);
        }

        //done adding today's legs
        //move any unextended routes into the finished vector
        for (_, mut rs) in routes_by_position {
            finished_routes.append(&mut rs);
        }
        //then carry over whatever was extended to tomorrow
        routes_by_position = extended_routes_by_position;
    }

    for (_, mut rs) in routes_by_position {
        finished_routes.append(&mut rs);
    }

    finished_routes
}

Notes: