path: root/2015/rs/src/nine.rs

#![feature(iter_next_chunk)]

use std::collections::{HashSet, HashMap};
use std::io::Write;

static INPUT: &'static str = include_str!("nine.txt");

fn main() {
  let valueified = INPUT.split('\n').filter(|s| !s.is_empty())
    .flat_map(|s| {
      let [rhs, dist] = s.split(" = ").next_chunk::<2>().unwrap();
      let [from, to] = rhs.split(" to ").next_chunk::<2>().unwrap();
      let dist = dist.parse::<usize>().unwrap();
      [(from, to, dist), (to, from, dist)]
    });

  let paths: HashMap<&'static str, Vec<(&'static str, usize)>> = valueified
    .map(|(a,b,c)| (a, (b, c)))
    .fold(HashMap::new(), |mut map, (k, v)| {map.entry(k).or_default().push(v); map});
  let mut path = Vec::new();
  let mut bestpath = Vec::new();
  let mut bestdist = usize::MAX;
  let mut worstpath = Vec::new();
  let mut worstdist = 0;
  for start in paths.keys() {
    path.clear();
    path.push(*start);
    walk_steps(&mut path, 0, &mut bestpath, &mut bestdist, &mut worstpath, &mut worstdist, &paths);
  }
  println!("Best route: {} with dist = {bestdist}", bestpath.join(" => "));
  println!("Worst route: {} with dist = {worstdist}", worstpath.join(" => "));
}

fn walk_steps(path: &mut Vec<&'static str>, dist: usize, bestpath: &mut Vec<&'static str>, bestdist: &mut usize, worstpath: &mut Vec<&'static str>, worstdist: &mut usize, steps: &HashMap<&'static str, Vec<(&'static str, usize)>>) {
  if path.len() != steps.len() {
    let prev = path.last().unwrap();
    for (step, stepdist) in &steps[prev] {
      if path.contains(step) { continue; }
      path.push(step);
      walk_steps(path, dist + stepdist, bestpath, bestdist, worstpath, worstdist, steps);
      path.pop();
    }
  } else {
    if dist < *bestdist {
      *bestpath = path.clone();
      *bestdist = dist;
    }
    else if dist > *worstdist {
      *worstpath = path.clone();
      *worstdist = dist;
    }
  }
}