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    has_parent: bool,
19    parent: usize,
20    children: usize,
21    processed: usize,
22    weight: i32,
23    total: i32,
24    sub_weights: [i32; 2],
25    sub_totals: [i32; 2],
26}
27
28type Input<'a> = (&'a str, i32);
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 = i;
53            nodes[child].has_parent = true;
54        }
55
56        // Start with leaf nodes.
57        if nodes[i].children == 0 {
58            todo.push_back(i);
59        }
60    }
61
62    // The root is the only node without a parent. Start from any node, and walk up the
63    // tree until finding the root.
64    let mut candidate = 0;
65    while nodes[candidate].has_parent {
66        candidate = nodes[candidate].parent;
67    }
68    let part_one = pairs[candidate].0;
69    let mut part_two = 0;
70
71    while let Some(index) = todo.pop_front() {
72        let Node { parent, weight, total, .. } = nodes[index];
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
