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    let mut indices = Vec::new();
45
46    for n in 1..64 {
47        indices.clear();
48
49        for (index, component) in components.iter().enumerate() {
50            if component.left == n || component.right == n {
51                indices.push(index);
52            }
53        }
54
55        if let [a, b] = indices[..] {
56            let second = components.swap_remove(b);
57            let first = components.swap_remove(a);
58
59            let left = if first.left == n { first.right } else { first.left };
60            let right = if second.left == n { second.right } else { second.left };
61            let weight = first.weight + second.weight;
62            let length = first.length + second.length;
63
64            components.push(Component { left, right, weight, length });
65        }
66    }
67
68    // Second optimization. Sort components with both ports the same before other components,
69    // so that the loop when choosing components in `build` function can terminate early.
70    components.sort_unstable_by_key(|c| (c.left ^ c.right, c.left));
71
72    let mut state = State {
73        possible: [0; 64],
74        both: [0; 64],
75        weight: [0; 64],
76        length: [0; 64],
77        bridge: [0; 64],
78    };
79
80    for (index, component) in components.iter().enumerate() {
81        let mask = 1 << index;
82        state.possible[component.left] |= mask;
83        state.possible[component.right] |= mask;
84
85        // Bitwise logic trick. `a ^ b ^ a = b` and `a ^ b ^ b = a` so given a single port and
86        // the XOR of both we can work out the other port of a component.
87        state.both[index] = component.left ^ component.right;
88        state.weight[index] = component.weight;
89        state.length[index] = component.length;
90    }
91
92    // Recursively build all possible bridges.
93    build(&mut state, 0, 0, 0, 0);
94    state.bridge
95}
96
97/// Strongest bridge.
98pub fn part1(input: &[usize]) -> usize {
99    *input.iter().max().unwrap()
100}
101
102/// Longest bridge.
103pub fn part2(input: &[usize]) -> usize {
104    *input.iter().rfind(|&&n| n > 0).unwrap()
105}
106
107fn build(state: &mut State, current: usize, used: usize, strength: usize, length: usize) {
108    // Bitset of all unused components that have a matching port.
109    let remaining = state.possible[current] & !used;
110
111    // Extract the index of each component from the bitset.
112    for index in remaining.biterator() {
113        let next = current ^ state.both[index];
114        let new_used = used | (1 << index);
115        let new_strength = strength + state.weight[index];
116        let new_length = length + state.length[index];
117
118        if state.possible[next] & !new_used == 0 {
119            // No more possible components to add to the bridge.
120            state.bridge[new_length] = state.bridge[new_length].max(new_strength);
121        } else {
122            build(state, next, new_used, new_strength, new_length);
123            // Critical optimization. If this is a component with two ports of the same values,
124            // for example 5/5 or 7/7 then it's always optimal to add it to the bridge.
125            // We don't need to consider further options.
126            if current == next {
127                break;
128            }
129        }
130    }
131}
aoc/year2017/day24.rs

aoc/year2017/
day24.rs
