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

aoc/year2016/
day10.rs
