aoc/year2017/
day07.rs

1//! # Recursive Circus
2//!
3//! Tree structures are tricky to implement in Rust, requiring wrapping the pointer in a [`Rc`].
4//! To avoid this we store the tree "upside down" with each node containing a single index to its
5//! parent, stored in a flat `vec`.
6//!
7//! We rely on a special structure of the input that the unbalanced node requiring change will
8//! always be the lowest node in the tree and have at least two other balanced siblings
9//! so that we can disambiguate.
10//!
11//! [`Rc`]: std::rc::Rc
12use std::collections::VecDeque;
13
14use crate::util::hash::*;
15use crate::util::parse::*;
16
17type Input<'a> = (&'a str, i32);
18
19#[derive(Clone, Copy, Default)]
20struct Node {
21    parent: Option<usize>,
22    children: usize,
23    processed: usize,
24    weight: i32,
25    total: i32,
26    sub_weights: [i32; 2],
27    sub_totals: [i32; 2],
28}
29
30pub fn parse(input: &str) -> Input<'_> {
31    // Split each line into the program name then the rest of the information.
32    let pairs: Vec<_> = input.lines().map(|line| line.split_once(' ').unwrap()).collect();
33    // Convert each program name into a fixed index so that we can use faster vec lookups
34    // later on when processing the tree.
35    let indices: FastMap<_, _> = pairs.iter().enumerate().map(|(i, &(key, _))| (key, i)).collect();
36    // Create a vec of the correct size with default values.
37    let mut nodes = vec![Node::default(); indices.len()];
38    // We'll process nodes from leaf to root.
39    let mut todo = VecDeque::new();
40
41    for (i, &(_, suffix)) in pairs.iter().enumerate() {
42        // Remove delimiters.
43        let mut iter = suffix.split(|c: char| !c.is_ascii_alphanumeric()).filter(|s| !s.is_empty());
44
45        let weight = iter.next().unwrap().signed();
46        nodes[i].weight = weight;
47        nodes[i].total = weight;
48
49        for edge in iter {
50            nodes[i].children += 1;
51            let child = indices[edge];
52            nodes[child].parent = Some(i);
53        }
54
55        // Start with leaf nodes.
56        if nodes[i].children == 0 {
57            todo.push_back(i);
58        }
59    }
60
61    // The root is the only node without a parent. Start from any node, and walk up the
62    // tree until finding the root.
63    let mut candidate = 0;
64    while let Some(parent) = nodes[candidate].parent {
65        candidate = parent;
66    }
67    let part_one = pairs[candidate].0;
68    let mut part_two = 0;
69
70    while let Some(index) = todo.pop_front() {
71        let Node { parent, weight, total, .. } = nodes[index];
72        let parent = parent.unwrap();
73        let node = &mut nodes[parent];
74
75        if node.processed < 2 {
76            // Fill out the first two children in any order.
77            node.sub_weights[node.processed] = weight;
78            node.sub_totals[node.processed] = total;
79        } else {
80            // Representing the balanced nodes as `b` and the unbalanced node as `u`,
81            // there are 4 possibilities:
82            // b3 + [b1 b2] => [b2 b1] Swap, keep accumulating
83            // b3 + [b1 u2] => [u2 b1] Swap, unbalanced node identified
84            // u3 + [b1 b2] -> [u3 b2] Overwrite, unbalanced node identified
85            // b3 + [u1 b2] => [u1 b2] Do nothing, unbalanced node identified
86            // The unbalanced node will always be first (if it exists).
87            if node.sub_totals[0] == total {
88                node.sub_weights.swap(0, 1);
89                node.sub_totals.swap(0, 1);
90            } else if node.sub_totals[1] != total {
91                node.sub_weights[0] = weight;
92                node.sub_totals[0] = total;
93            }
94
95            // If the unbalanced node was identified, it is now first, and we can short-circuit
96            // summing the weights of the rest of the tree.
97            let [x, y] = node.sub_totals;
98
99            if x != y {
100                part_two = node.sub_weights[0] - x + y;
101                break;
102            }
103        }
104
105        // Total is a node's weight plus the sum of all children recursively.
106        node.total += total;
107        node.processed += 1;
108
109        // If we've processed all children then add to the queue and check balance.
110        if node.processed == node.children {
111            todo.push_back(parent);
112        }
113    }
114
115    (part_one, part_two)
116}
117
118pub fn part1<'a>(input: &Input<'a>) -> &'a str {
119    input.0
120}
121
122pub fn part2(input: &Input<'_>) -> i32 {
123    input.1
124}
aoc/year2017/day07.rs

aoc/year2017/
day07.rs
