aoc/year2017/
day24.rs

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

aoc/year2017/
day24.rs
