From 27047f6d4567a55e66578c3d5254f97c49073c23 Mon Sep 17 00:00:00 2001 From: Curtis McEnroe Date: Sat, 10 Dec 2016 23:37:38 -0500 Subject: Day 10 --- src/bin/day10.rs | 168 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 168 insertions(+) create mode 100644 src/bin/day10.rs (limited to 'src/bin') diff --git a/src/bin/day10.rs b/src/bin/day10.rs new file mode 100644 index 0000000..d45661e --- /dev/null +++ b/src/bin/day10.rs @@ -0,0 +1,168 @@ +use std::collections::HashMap; +use std::io::{self, Read}; +use std::str::FromStr; + +#[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash)] +struct Chip(u32); + +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +struct Bot(u32); + +#[derive(Clone, Copy, PartialEq, Eq, Hash)] +struct Output(u32); + +#[derive(Clone, Copy, Default)] +struct BotChips(Option, Option); + +impl BotChips { + fn add(&mut self, chip: Chip) { + match (self.0, self.1) { + (None, None) => { + self.0 = Some(chip); + }, + (Some(low), None) if low < chip => { + self.1 = Some(chip); + }, + (Some(high), None) => { + self.0 = Some(chip); + self.1 = Some(high); + }, + _ => panic!("bot has too many chips"), + } + } + + fn has_two(&self) -> bool { + self.0.is_some() && self.1.is_some() + } +} + +#[derive(Clone, Copy)] +enum Destination { + Bot(Bot), + Output(Output), +} + +impl Destination { + fn from_pair(ty: &str, value: u32) -> Result { + match ty { + "bot" => Ok(Destination::Bot(Bot(value))), + "output" => Ok(Destination::Output(Output(value))), + _ => Err(()), + } + } +} + +#[derive(Default)] +struct Instructions { + chips: HashMap, + bots: HashMap, +} + +impl FromStr for Instructions { + type Err = (); + fn from_str(s: &str) -> Result { + let mut instructions = Instructions::default(); + + for line in s.lines() { + let mut words = line.split(' '); + if words.next() == Some("value") { + let value = words.next().ok_or(())?.parse().map_err(|_| ())?; + let bot = words.nth(3).ok_or(())?.parse().map_err(|_| ())?; + + instructions.chips.insert(Chip(value), Bot(bot)); + } else { + let bot = words.next().ok_or(())?.parse().map_err(|_| ())?; + let low_type = words.nth(3).ok_or(())?; + let low_value = words.next().ok_or(())?.parse().map_err(|_| ())?; + let high_type = words.nth(3).ok_or(())?; + let high_value = words.next().ok_or(())?.parse().map_err(|_| ())?; + + let low = Destination::from_pair(low_type, low_value)?; + let high = Destination::from_pair(high_type, high_value)?; + + instructions.bots.insert(Bot(bot), (low, high)); + } + } + + Ok(instructions) + } +} + +#[derive(Default)] +struct State { + outputs: HashMap>, + bots: HashMap, + comparisons: HashMap<(Chip, Chip), Bot>, +} + +impl State { + fn initialize(&mut self, instructions: &Instructions) { + for (&chip, &bot) in &instructions.chips { + self.bots.entry(bot).or_insert_with(Default::default).add(chip); + } + } + + fn step(&mut self, instructions: &Instructions) -> bool { + let active_bots: Vec = self.bots.iter() + .filter(|&(_, ref chips)| chips.has_two()) + .map(|(&bot, _)| bot) + .collect(); + + if active_bots.is_empty() { + return false; + } + + for bot in active_bots { + let (low, high) = { + let chips = self.bots.get_mut(&bot).unwrap(); + (chips.0.take().unwrap(), chips.1.take().unwrap()) + }; + self.comparisons.insert((low, high), bot); + + let &(low_dest, high_dest) = instructions.bots.get(&bot).unwrap(); + self.add_to(low_dest, low); + self.add_to(high_dest, high); + } + + true + } + + fn add_to(&mut self, destination: Destination, chip: Chip) { + match destination { + Destination::Bot(bot) => { + self.bots.entry(bot).or_insert_with(Default::default).add(chip); + }, + Destination::Output(output) => { + self.outputs.entry(output).or_insert_with(Vec::new).push(chip); + }, + } + } +} + +fn solve(comparison: (Chip, Chip), input: &str) -> Option { + let instructions = input.parse().unwrap(); + let mut state = State::default(); + state.initialize(&instructions); + while state.step(&instructions) { } + state.comparisons.get(&comparison).cloned() +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {:?}", solve((Chip(17), Chip(61)), &input)); +} + +#[test] +fn part1() { + let input = " +value 5 goes to bot 2 +bot 2 gives low to bot 1 and high to bot 0 +value 3 goes to bot 1 +bot 1 gives low to output 1 and high to bot 0 +bot 0 gives low to output 2 and high to output 0 +value 2 goes to bot 2 +"; + assert_eq!(Some(Bot(2)), solve((Chip(2), Chip(5)), input.trim())); +} -- cgit 1.4.1