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 tracking 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::parse::*;
18use crate::util::slice::*;
19
20type Input = (i32, i32);
21
22pub fn parse(input: &str) -> Input {
23    // Assign each diner an index on a first come first served basis.
24    let lines: Vec<Vec<_>> = input.lines().map(|line| line.split([' ', '.']).collect()).collect();
25    let mut indices = FastMap::new();
26
27    for tokens in &lines {
28        let size = indices.len();
29        indices.entry(tokens[0]).or_insert(size);
30
31        let size = indices.len();
32        indices.entry(tokens[10]).or_insert(size);
33    }
34
35    // Calculate the happiness values. Note that the values are not reciprocal a => b != b => a.
36    let stride = indices.len();
37    let mut happiness = vec![0; stride * stride];
38
39    for tokens in &lines {
40        let start = indices[tokens[0]];
41        let end = indices[tokens[10]];
42        let sign = if tokens[2] == "gain" { 1 } else { -1 };
43        let value: i32 = tokens[3].signed();
44
45        // Add the values together to make the mutual link reciprocal
46        happiness[stride * start + end] += sign * value;
47        happiness[stride * end + start] += sign * value;
48    }
49
50    // Solve both parts simultaneously.
51    let mut part_one = 0;
52    let mut part_two = 0;
53    let mut indices: Vec<_> = (1..stride).collect();
54
55    indices.half_permutations(|slice| {
56        let mut sum = 0;
57        let mut weakest_link = i32::MAX;
58
59        let mut link = |from, to| {
60            let value = happiness[stride * from + to];
61            sum += value;
62            weakest_link = weakest_link.min(value);
63        };
64
65        link(0, slice[0]);
66        link(0, slice[slice.len() - 1]);
67
68        for i in 1..slice.len() {
69            link(slice[i], slice[i - 1]);
70        }
71
72        part_one = part_one.max(sum);
73        part_two = part_two.max(sum - weakest_link);
74    });
75
76    (part_one, part_two)
77}
78
79pub fn part1(input: &Input) -> i32 {
80    input.0
81}
82
83pub fn part2(input: &Input) -> i32 {
84    input.1
85}
aoc/year2015/day13.rs

aoc/year2015/
day13.rs
