year2015/
day13.rs

1use std::collections::HashMap;
2use utils::graph::explore_hamiltonian_paths;
3use utils::prelude::*;
4
5/// Seating plan.
6///
7/// Very similar to [Day 9](crate::Day09), including part 2, which only requires subtracting the
8/// minimum edge from each permutation's total.
9#[derive(Clone, Debug)]
10pub struct Day13 {
11    part1: i32,
12    part2: i32,
13}
14
15type Seated = u32;
16
17impl Day13 {
18    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
19        let parsed = parser::take_while1(u8::is_ascii_alphabetic)
20            .with_suffix(" would ")
21            .then(
22                parser::one_of((
23                    parser::u16().with_prefix("gain ").map(i32::from),
24                    parser::u16().with_prefix("lose ").map(|x| -i32::from(x)),
25                ))
26                .with_suffix(" happiness units by sitting next to "),
27            )
28            .then(parser::take_while1(u8::is_ascii_alphabetic).with_suffix(b'.'))
29            .parse_lines(input)?;
30
31        let mut indexes = HashMap::new();
32        parsed.iter().for_each(|&(person, ..)| {
33            let len = indexes.len();
34            indexes.entry(person).or_insert(len);
35        });
36
37        if indexes.len() > Seated::BITS as usize {
38            return Err(InputError::new(input, 0, "too many people"));
39        }
40
41        let people = indexes.len();
42        let mut matrix = vec![0; people * people];
43        parsed.iter().for_each(|&(person1, change, person2)| {
44            matrix[indexes[person1] * people + indexes[person2]] = change;
45        });
46
47        let (mut part1, mut part2) = (i32::MIN, i32::MIN);
48        explore_hamiltonian_paths(
49            people as u32,
50            0,
51            (0, i32::MAX),
52            |a, b| {
53                matrix[a as usize * people + b as usize] + matrix[b as usize * people + a as usize]
54            },
55            |(total, min_edge), edge| (total + edge, min_edge.min(edge)),
56            |(total, min_edge), loop_edge| {
57                part1 = part1.max(total + loop_edge);
58                part2 = part2.max(total + loop_edge - min_edge.min(loop_edge));
59            },
60        );
61
62        Ok(Self { part1, part2 })
63    }
64
65    #[must_use]
66    pub fn part1(&self) -> i32 {
67        self.part1
68    }
69
70    #[must_use]
71    pub fn part2(&self) -> i32 {
72        self.part2
73    }
74}
75
76examples!(Day13 -> (i32, i32) [
77    {file: "day13_example0.txt", part1: 330},
78]);
year2015/day13.rs

year2015/
day13.rs
