Day 09: All in a Single Night

With a good graph library (not a 2d graph but a mathematical graph) traveling salesman becomes easy. Luckily I took the time to write a graph library. It’s not perfect but it works. I wanted to merge traveling salesman into the library and use a BinaryHeap to keep track of all distances but Ord is not implemented for floats which makes this difficult (and I have to make a new type to store in the heap).

Ignoring all that, implementing traveling salesman is painless.

Loading code...

day_09.rs

use crate::graph::graph::Graph;

fn parse_input (input: &str) -> Graph<String, usize> {
	let line_iterator = input.lines()
		.map(|line| line.split(" ").collect::<Vec<_>>())
		.map(|line| (
			String::from(line[0]), // From
			String::from(line[2]), // To
			usize::from_str_radix(line[4], 10).unwrap() // Distance
		));
	let mut graph = Graph::new_from_iterator(line_iterator);
	graph.make_undirected();
	return graph;
}

pub fn day_09_1 (input: &str) -> String {
	let graph = parse_input(input);
	let mut best_distance = usize::MAX;
	for path in graph.all_paths() {
		let distance = graph.path_distance(path);
		if distance < best_distance {
			best_distance = distance;
		}
	}
	return best_distance.to_string();
}

pub fn day_09_2 (input: &str) -> String {
	let graph = parse_input(input);
	let mut best_distance = 0;
	for path in graph.all_paths() {
		let distance = graph.path_distance(path);
		if distance > best_distance {
			best_distance = distance;
		}
	}
	return best_distance.to_string();
}