aoc/year2018/
day08.rs

1//! # Memory Maneuver
2//!
3//! Recursive solution computing both parts at the same time, sharing a single mutable iterator.
4//! A shared stack is used to store the scores for child nodes temporarily.
5use crate::util::parse::*;
6
7type Input = (usize, usize);
8
9pub fn parse(input: &str) -> Input {
10    parse_node(&mut input.iter_unsigned(), &mut Vec::new())
11}
12
13pub fn part1(input: &Input) -> usize {
14    input.0
15}
16
17pub fn part2(input: &Input) -> usize {
18    input.1
19}
20
21fn parse_node(iter: &mut impl Iterator<Item = usize>, stack: &mut Vec<usize>) -> (usize, usize) {
22    // Save stack size
23    let stack_base = stack.len();
24
25    // Parse header
26    let child_count = iter.next().unwrap();
27    let metadata_count = iter.next().unwrap();
28
29    let mut metadata = 0;
30    let mut score = 0;
31
32    // Parse child nodes, adding their metadata to current node and saving their score for
33    // when metadata is processed.
34    for _ in 0..child_count {
35        let (first, second) = parse_node(iter, stack);
36        metadata += first;
37        stack.push(second);
38    }
39
40    // Process metadata.
41    for _ in 0..metadata_count {
42        let n = iter.next().unwrap();
43        metadata += n;
44
45        if child_count == 0 {
46            score += n;
47        } else if n > 0 && n <= child_count {
48            score += stack[stack_base + (n - 1)];
49        }
50    }
51
52    // Pop child nodes from the stack.
53    stack.truncate(stack_base);
54
55    (metadata, score)
56}
aoc/year2018/day08.rs

aoc/year2018/
day08.rs
