advent_of_code/year2015/
day09.rs

1use crate::common::id_assigner::IdAssigner;
2use crate::common::permutation::all_permutations;
3use crate::common::tuple_window_iterator::TupleWindowIteratorExt;
4use crate::input::Input;
5
6const MAX_LOCATIONS: u16 = 10;
7
8pub fn solve(input: &Input) -> Result<u32, String> {
9    let mut id_assigner = IdAssigner::<{ MAX_LOCATIONS as usize }, str>::new("");
10
11    let mut places = Vec::with_capacity(MAX_LOCATIONS as usize);
12    let mut distances = [0; (MAX_LOCATIONS * MAX_LOCATIONS) as usize];
13    for line in input.text.lines() {
14        // "Faerun to Tristram = 58"
15        let mut parts = line.split(' ');
16        let from = id_assigner.id_of(parts.next().ok_or("Invalid input")?)?;
17        let to = id_assigner.id_of(parts.nth(1).ok_or("Invalid input")?)?;
18        let distance = parts
19            .nth(1)
20            .ok_or("Invalid input")?
21            .parse::<u32>()
22            .map_err(|_| "Invalid input")?;
23
24        if !places.contains(&from) {
25            places.push(from);
26        }
27        if !places.contains(&to) {
28            places.push(to);
29        }
30        distances[(from + to * MAX_LOCATIONS) as usize] = distance;
31        distances[(to + from * MAX_LOCATIONS) as usize] = distance;
32    }
33
34    let mut best_distance = input.part_values(u32::MAX, u32::MIN);
35    let comparator = input.part_values(
36        std::cmp::min as fn(_, _) -> _,
37        std::cmp::max as fn(_, _) -> _,
38    );
39
40    all_permutations(&mut places, &mut |ordering| {
41        let this_distance = ordering.iter().tuple_windows().fold(0, |acc, (p1, p2)| {
42            acc + distances[(p1 + p2 * MAX_LOCATIONS) as usize]
43        });
44        best_distance = comparator(best_distance, this_distance);
45        Ok(())
46    })?;
47
48    Ok(best_distance)
49}
50
51#[test]
52pub fn tests() {
53    use crate::input::{test_part_one, test_part_two};
54
55    let example_input = "London to Dublin = 464
56London to Belfast = 518
57Dublin to Belfast = 141";
58    test_part_one!(example_input => 605);
59    test_part_two!(example_input => 982);
60
61    let real_input = include_str!("day09_input.txt");
62    test_part_one!(real_input => 207);
63    test_part_two!(real_input => 804);
64}
advent_of_code/year2015/day09.rs

advent_of_code/year2015/
day09.rs
