Advent of Code day 9

day9.rs

extern crate regex;
extern crate permutohedron;

use std::fs::File;
use std::io::BufReader;
use std::io::BufRead;
use std::collections::{HashMap, HashSet};

use regex::Regex;
use permutohedron::LexicalPermutation;

fn main() {
    let input_fname = "day9_input.txt";
    let re = Regex::new("^(.*) to (.*) = (.*)$").unwrap();
    let f = File::open(input_fname).unwrap();
    let reader = BufReader::new(f);
    let mut nodes: HashSet<String> = HashSet::new();
    let mut distances: HashMap<(String, String), u16> = HashMap::new();

    // Parse input
    for line in reader.lines() {
        let line = line.unwrap();
        let cap = re.captures(&line).unwrap();
        let from = cap.at(1).unwrap().to_string();
        let to = cap.at(2).unwrap().to_string();
        let distance = cap.at(3).unwrap().parse::<u16>().unwrap();
        distances.insert((from.clone(), to.clone()), distance);
        distances.insert((to.clone(), from.clone()), distance);
        nodes.insert(from);
        nodes.insert(to);
    }

    // To find the shortest path visiting all nodes in a clique,
    // permutate all other nodes, and find the minimum distance.

    let mut nodes_vec : Vec<&String> = nodes.iter().collect();

    // The permutation algorithm assumes lexically-sorted input
    nodes_vec.sort();

    let mut min_distance = u16::max_value();
    let mut max_distance = 0;

    loop {
        let total_distance = nodes_vec.windows(2).fold(0, |acc, w| {
            acc + *distances.get(&(w[0].clone(), w[1].clone())).unwrap()
        });
        if total_distance < min_distance {
            min_distance = total_distance;
        }
        if total_distance > max_distance {
            max_distance = total_distance;
        }
        
        if !nodes_vec.next_permutation() {
            break
        }
    }
    println!("Min distance: {}", min_distance);
    println!("Max distance: {}", max_distance);
}