aoc/year2015/
day13.rs

1//! # Knights of the Dinner Table
2//!
3//! This problem is very similar to [`Day 9`] and we solve it in almost exactly the same way by
4//! computing an adjacency matrix of happiness then permuting the order of the diners.
5//!
6//! For part one we reduce the permutatations from 8! = 40,320 permutations to 7! = 5,040
7//! permutations by arbitrarily choosing one of the diners as the start.
8//!
9//! We solve part two at the same time by noticing that by inserting yourself between two diners
10//! you set the value of their mutual link to zero. Keeping tracking of the weakest link
11//! then subtracting that from the value for part one gives the result for part two at almost
12//! no additional cost.
13//!
14//! [`Day 9`]: crate::year2015::day09
15use crate::util::hash::*;
16use crate::util::parse::*;
17use crate::util::slice::*;
18
19type Input = (i32, i32);
20
21pub fn parse(input: &str) -> Input {
22    // Assign each diner an index on a first come first served basis.
23    let lines: Vec<Vec<_>> = input.lines().map(|line| line.split([' ', '.']).collect()).collect();
24    let mut indices = FastMap::new();
25
26    for tokens in &lines {
27        let size = indices.len();
28        indices.entry(tokens[0]).or_insert(size);
29
30        let size = indices.len();
31        indices.entry(tokens[10]).or_insert(size);
32    }
33
34    // Calculate the happiness values. Note that the values are not reciprocal a => b != b => a.
35    let stride = indices.len();
36    let mut happiness = vec![0; stride * stride];
37
38    for tokens in &lines {
39        let start = indices[tokens[0]];
40        let end = indices[tokens[10]];
41        let sign = if tokens[2] == "gain" { 1 } else { -1 };
42        let value: i32 = tokens[3].signed();
43
44        // Add the values together to make the mutual link reciprocal
45        happiness[stride * start + end] += sign * value;
46        happiness[stride * end + start] += sign * value;
47    }
48
49    // Solve both parts simultaneously.
50    let mut part_one = 0;
51    let mut part_two = 0;
52    let mut indices: Vec<_> = (1..stride).collect();
53
54    indices.permutations(|slice| {
55        let mut sum = 0;
56        let mut weakest_link = i32::MAX;
57
58        let mut link = |from, to| {
59            let value = happiness[stride * from + to];
60            sum += value;
61            weakest_link = weakest_link.min(value);
62        };
63
64        link(0, slice[0]);
65        link(0, slice[slice.len() - 1]);
66
67        for i in 1..slice.len() {
68            link(slice[i], slice[i - 1]);
69        }
70
71        part_one = part_one.max(sum);
72        part_two = part_two.max(sum - weakest_link);
73    });
74
75    (part_one, part_two)
76}
77
78pub fn part1(input: &Input) -> i32 {
79    input.0
80}
81
82pub fn part2(input: &Input) -> i32 {
83    input.1
84}
aoc/year2015/day13.rs

aoc/year2015/
day13.rs
