aoc/year2016/
day10.rs

1//! # Balance Bots
2//!
3//! Performs a [topological sort](https://en.wikipedia.org/wiki/Topological_sorting) of the bots,
4//! starting from raw values, passing through some number of bots then ending in an output.
5//!
6//! We maintain a [`VecDeque`] of chips and destinations starting with raw inputs.
7//! Once each robot receives 2 chips then its low and high outputs are added to the queue.
8//!
9//! As a minor optimization we only need to store the product of outputs 0, 1 and 2.
10use crate::util::hash::*;
11use crate::util::parse::*;
12use std::collections::VecDeque;
13
14type Input = (u32, u32);
15type Dest<'a> = (&'a str, &'a str);
16
17struct Bot<'a> {
18    low: Dest<'a>,
19    high: Dest<'a>,
20    chips: [u32; 2],
21    amount: usize,
22}
23
24pub fn parse(input: &str) -> Input {
25    let tokens: Vec<_> = input.split_ascii_whitespace().collect();
26    let mut tokens = &tokens[..];
27
28    let mut todo = VecDeque::new();
29    let mut bots = FastMap::new();
30
31    let mut part_one = u32::MAX;
32    let mut part_two = 1;
33
34    while !tokens.is_empty() {
35        if tokens[0] == "value" {
36            let value = tokens[1].unsigned();
37            let dest = (tokens[4], tokens[5]);
38
39            tokens = &tokens[6..];
40            todo.push_back((dest, value));
41        } else {
42            let key = tokens[1].unsigned();
43            let low = (tokens[5], tokens[6]);
44            let high = (tokens[10], tokens[11]);
45
46            tokens = &tokens[12..];
47            bots.insert(key, Bot { low, high, chips: [0; 2], amount: 0 });
48        }
49    }
50
51    while let Some(((kind, index), value)) = todo.pop_front() {
52        let index = index.unsigned();
53
54        if kind == "bot" {
55            bots.entry(index).and_modify(|bot| {
56                bot.chips[bot.amount] = value;
57                bot.amount += 1;
58
59                if bot.amount == 2 {
60                    let min = bot.chips[0].min(bot.chips[1]);
61                    let max = bot.chips[0].max(bot.chips[1]);
62
63                    todo.push_back((bot.low, min));
64                    todo.push_back((bot.high, max));
65
66                    if min == 17 && max == 61 {
67                        part_one = index;
68                    }
69                }
70            });
71        } else if index <= 2 {
72            part_two *= value;
73        }
74    }
75
76    (part_one, part_two)
77}
78
79pub fn part1(input: &Input) -> u32 {
80    input.0
81}
82
83pub fn part2(input: &Input) -> u32 {
84    input.1
85}
aoc/year2016/day10.rs

aoc/year2016/
day10.rs
