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

aoc/year2015/
day13.rs
