aoc/year2017/
day24.rs

1//! # Electromagnetic Moat
2//!
3//! Both parts are calculated at the same time by recursively building all possible bridge
4//! combinations. Two optimizations are used to speed things up ten times.
5//!
6//! First ports that only appear in two components are merged. For example `2/17` and `17/3`
7//! becomes a single component `2/3` with a weight of 39 and a length of 2. This shaves about 30%
8//! off the time needed.
9//!
10//! The second optimization is far more critical and reduces the time needed by 85%. The
11//! observation is that components with two ports the same, for example `7/7`, are always optimal
12//! to pick first, as they increase strength and length without changing the port number.
13//!
14//! If we can place such a component then there's no need to consider further components which
15//! reduces the total number of combinations to consider.
16use crate::util::bitset::*;
17use crate::util::iter::*;
18use crate::util::parse::*;
19
20struct Component {
21    left: usize,
22    right: usize,
23    weight: usize,
24    length: usize,
25}
26
27struct State {
28    possible: [usize; 64],
29    both: [usize; 64],
30    weight: [usize; 64],
31    length: [usize; 64],
32    bridge: [usize; 64],
33}
34
35pub fn parse(input: &str) -> [usize; 64] {
36    let mut components: Vec<_> = input
37        .iter_unsigned()
38        .chunk::<2>()
39        .map(|[left, right]| Component { left, right, weight: left + right, length: 1 })
40        .collect();
41
42    // First optimization. If a port value appears in only 2 components (excluding zero)
43    // then fuse the components together.
44    for n in 1..64 {
45        let mut indices = components.iter().enumerate().filter_map(|(index, component)| {
46            (component.left == n || component.right == n).then_some(index)
47        });
48
49        if let (Some(a), Some(b), None) = (indices.next(), indices.next(), indices.next()) {
50            let second = components.swap_remove(b);
51            let first = components.swap_remove(a);
52
53            let left = if first.left == n { first.right } else { first.left };
54            let right = if second.left == n { second.right } else { second.left };
55            let weight = first.weight + second.weight;
56            let length = first.length + second.length;
57
58            components.push(Component { left, right, weight, length });
59        }
60    }
61
62    // Second optimization. Sort components with both ports the same before other components,
63    // so that the loop when choosing components in `build` function can terminate early.
64    components.sort_unstable_by_key(|c| (c.left ^ c.right, c.left));
65
66    let mut state = State {
67        possible: [0; 64],
68        both: [0; 64],
69        weight: [0; 64],
70        length: [0; 64],
71        bridge: [0; 64],
72    };
73
74    for (index, component) in components.iter().enumerate() {
75        let mask = 1 << index;
76        state.possible[component.left] |= mask;
77        state.possible[component.right] |= mask;
78
79        // Bitwise logic trick. `a ^ b ^ a = b` and `a ^ b ^ b = a` so given a single port and
80        // the XOR of both we can work out the other port of a component.
81        state.both[index] = component.left ^ component.right;
82        state.weight[index] = component.weight;
83        state.length[index] = component.length;
84    }
85
86    // Recursively build all possible bridges.
87    build(&mut state, 0, 0, 0, 0);
88    state.bridge
89}
90
91/// Strongest bridge.
92pub fn part1(input: &[usize]) -> usize {
93    *input.iter().max().unwrap()
94}
95
96/// Longest bridge.
97pub fn part2(input: &[usize]) -> usize {
98    *input.iter().rfind(|&&n| n > 0).unwrap()
99}
100
101fn build(state: &mut State, current: usize, used: usize, strength: usize, length: usize) {
102    // Bitset of all unused components that have a matching port.
103    let remaining = state.possible[current] & !used;
104
105    // Extract the index of each component from the bitset.
106    for index in remaining.biterator() {
107        let next = current ^ state.both[index];
108        let new_used = used | (1 << index);
109        let new_strength = strength + state.weight[index];
110        let new_length = length + state.length[index];
111
112        if state.possible[next] & !new_used == 0 {
113            // No more possible components to add to the bridge.
114            state.bridge[new_length] = state.bridge[new_length].max(new_strength);
115        } else {
116            build(state, next, new_used, new_strength, new_length);
117            // Critical optimization. If this is a component with two ports of the same values,
118            // for example 5/5 or 7/7, then it's always optimal to add it to the bridge.
119            // We don't need to consider further options.
120            if current == next {
121                break;
122            }
123        }
124    }
125}
aoc/year2017/day24.rs

aoc/year2017/
day24.rs
