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 mut tokens = input.split_ascii_whitespace();
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 let Some(command) = tokens.next() {
35        if command == "value" {
36            let value = tokens.next().unwrap().unsigned();
37            let dest = to_dest(tokens.nth(2).unwrap(), tokens.next().unwrap());
38
39            todo.push_back((dest, value));
40        } else {
41            let key: u32 = tokens.next().unwrap().unsigned();
42            let low = to_dest(tokens.nth(3).unwrap(), tokens.next().unwrap());
43            let high = to_dest(tokens.nth(3).unwrap(), tokens.next().unwrap());
44
45            bots.insert(key, Bot { low, high, chip: None });
46        }
47    }
48
49    while let Some(((is_bot, index), value)) = todo.pop_front() {
50        if is_bot {
51            let bot = bots.get_mut(&index).unwrap();
52
53            if let Some(previous) = bot.chip {
54                let (min, max) = previous.minmax(value);
55                if min == 17 && max == 61 {
56                    part_one = index;
57                }
58
59                todo.push_back((bot.low, min));
60                todo.push_back((bot.high, max));
61            } else {
62                bot.chip = Some(value);
63            }
64        } else if index <= 2 {
65            part_two *= value;
66        }
67    }
68
69    (part_one, part_two)
70}
71
72pub fn part1(input: &Input) -> u32 {
73    input.0
74}
75
76pub fn part2(input: &Input) -> u32 {
77    input.1
78}
79
80fn to_dest(first: &str, second: &str) -> Dest {
81    (first == "bot", second.unsigned())
82}
aoc/year2016/day10.rs

aoc/year2016/
day10.rs
