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

aoc/year2017/
day07.rs
