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.
63    let part_one = indices.iter().find(|(_, v)| !nodes[**v].has_parent).unwrap().0;
64    let mut part_two = 0;
65
66    while let Some(index) = todo.pop_front() {
67        let Node { parent, weight, total, .. } = nodes[index];
68        let node = &mut nodes[parent];
69
70        if node.processed < 2 {
71            // Fill out the first two children in any order.
72            node.sub_weights[node.processed] = weight;
73            node.sub_totals[node.processed] = total;
74        } else {
75            // Representing the balanced nodes as `b` and the unbalanced node as `u`,
76            // there are 4 possibilities:
77            // b + [b b] => [b b] Swap
78            // b + [b u] => [u b] Swap
79            // u + [b b] -> [u b] Overwrite
80            // b + [u b] => [u b] Do nothing
81            // The unbalanced node will always be first (if it exists).
82            if node.sub_totals[0] == total {
83                node.sub_weights.swap(0, 1);
84                node.sub_totals.swap(0, 1);
85            } else if node.sub_totals[1] != total {
86                node.sub_weights[0] = weight;
87                node.sub_totals[0] = total;
88            }
89        }
90
91        // Total is a nodes weight plus the sum of all children recursively.
92        node.total += total;
93        node.processed += 1;
94
95        // If we've processed all children then add to the queue and check balance.
96        if node.processed == node.children {
97            todo.push_back(parent);
98
99            // The unbalanced node will always be first, due to the way we swap the weight
100            // when processing children.
101            if node.children >= 3 {
102                let [w, _] = node.sub_weights;
103                let [x, y] = node.sub_totals;
104
105                if x != y {
106                    part_two = w - x + y;
107                    break;
108                }
109            }
110        }
111    }
112
113    (part_one, part_two)
114}
115
116pub fn part1<'a>(input: &Input<'a>) -> &'a str {
117    input.0
118}
119
120pub fn part2(input: &Input<'_>) -> i32 {
121    input.1
122}
aoc/year2017/day07.rs

aoc/year2017/
day07.rs
