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 std::collections::VecDeque;
11
12use crate::util::hash::*;
13use crate::util::integer::*;
14use crate::util::parse::*;
15
16type Input = (u32, u32);
17type Dest = (bool, u32);
18
19struct Bot {
20    low: Dest,
21    high: Dest,
22    chip: Option<u32>,
23}
24
25pub fn parse(input: &str) -> Input {
26    let tokens: Vec<_> = input.split_ascii_whitespace().collect();
27    let mut tokens = &tokens[..];
28
29    let mut todo = VecDeque::with_capacity(500);
30    let mut bots = FastMap::with_capacity(500);
31
32    let mut part_one = u32::MAX;
33    let mut part_two = 1;
34
35    while !tokens.is_empty() {
36        if tokens[0] == "value" {
37            let value = tokens[1].unsigned();
38            let dest = to_dest(tokens[4], tokens[5]);
39
40            todo.push_back((dest, value));
41            tokens = &tokens[6..];
42        } else {
43            let key: u32 = tokens[1].unsigned();
44            let low = to_dest(tokens[5], tokens[6]);
45            let high = to_dest(tokens[10], tokens[11]);
46
47            bots.insert(key, Bot { low, high, chip: None });
48            tokens = &tokens[12..];
49        }
50    }
51
52    while let Some(((is_bot, index), value)) = todo.pop_front() {
53        if is_bot {
54            let bot = bots.get_mut(&index).unwrap();
55
56            if let Some(previous) = bot.chip {
57                let (min, max) = previous.minmax(value);
58                if min == 17 && max == 61 {
59                    part_one = index;
60                }
61
62                todo.push_back((bot.low, min));
63                todo.push_back((bot.high, max));
64            } else {
65                bot.chip = Some(value);
66            }
67        } else if index <= 2 {
68            part_two *= value;
69        }
70    }
71
72    (part_one, part_two)
73}
74
75pub fn part1(input: &Input) -> u32 {
76    input.0
77}
78
79pub fn part2(input: &Input) -> u32 {
80    input.1
81}
82
83fn to_dest(first: &str, second: &str) -> Dest {
84    (first == "bot", second.unsigned())
85}
aoc/year2016/day10.rs

aoc/year2016/
day10.rs
