year2017/
day24.rs

1use utils::bit::BitIterator;
2use utils::prelude::*;
3
4/// Finding the longest and strongest bridge.
5#[derive(Clone, Debug)]
6pub struct Day24 {
7    part1: u32,
8    part2: u32,
9}
10
11impl Day24 {
12    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
13        let mut components: Vec<[u32; 2]> = parser::number_range(0..=63)
14            .repeat_n(b'/')
15            .parse_lines(input)?;
16        if components.len() >= 64 {
17            return Err(InputError::new(input, input.len(), "too many components"));
18        }
19
20        // Sort all the components with matching pin counts first
21        components.sort_unstable_by_key(|&[a, b]| a != b);
22
23        let mut bitsets = [0u64; 64];
24        let mut sums = [0u32; 64];
25        for (i, &[a, b]) in components.iter().enumerate() {
26            bitsets[a as usize] |= 1 << i;
27            bitsets[b as usize] |= 1 << i;
28            sums[i] = a + b;
29        }
30        if bitsets[0] == 0 {
31            return Err(InputError::new(input, 0, "no zero pin components"));
32        }
33
34        let mut out = [0u32; 64];
35        Self::search(&bitsets, &sums, &mut out, 0, 0, 0, 0);
36
37        Ok(Self {
38            part1: out.iter().max().copied().unwrap(),
39            part2: out.iter().rfind(|&&s| s > 0).copied().unwrap(),
40        })
41    }
42
43    fn search(
44        bitsets: &[u64],
45        sum: &[u32],
46        best: &mut [u32],
47        pins: u32,
48        used: u64,
49        strength: u32,
50        length: usize,
51    ) {
52        let remaining = bitsets[pins as usize] & !used;
53        if remaining == 0 {
54            best[length] = best[length].max(strength);
55            return;
56        }
57
58        for (component_index, component_bit) in BitIterator::ones(remaining) {
59            let component_sum = sum[component_index as usize];
60
61            Self::search(
62                bitsets,
63                sum,
64                best,
65                component_sum - pins,
66                used | component_bit,
67                strength + component_sum,
68                length + 1,
69            );
70
71            // It is always optimal to choose a component with matching pins if available
72            if component_sum == pins * 2 {
73                break;
74            }
75        }
76    }
77
78    #[must_use]
79    pub fn part1(&self) -> u32 {
80        self.part1
81    }
82
83    #[must_use]
84    pub fn part2(&self) -> u32 {
85        self.part2
86    }
87}
88
89examples!(Day24 -> (u32, u32) [
90    {input: "0/2\n2/2\n2/3\n3/4\n3/5\n0/1\n10/1\n9/10", part1: 31, part2: 19},
91]);
year2017/day24.rs

year2017/
day24.rs
