325 lines
8.2 KiB
Rust
325 lines
8.2 KiB
Rust
use std::{
|
|
collections::{HashMap, HashSet, VecDeque},
|
|
fmt::Display,
|
|
};
|
|
|
|
use itertools::Itertools;
|
|
|
|
pub fn run() {
|
|
let input = include_str!("../input/day20.txt");
|
|
// let input = r#"
|
|
// broadcaster -> a, b, c
|
|
// %a -> b
|
|
// %b -> c
|
|
// %c -> inv
|
|
// &inv -> a
|
|
// "#;
|
|
|
|
// let input = r#"
|
|
// broadcaster -> a
|
|
// %a -> inv, con
|
|
// &inv -> b
|
|
// %b -> con
|
|
// &con -> output
|
|
// "#;
|
|
|
|
let modules = parse_modules(input);
|
|
dbg!(simulate_one_thousand(modules.clone()));
|
|
|
|
let rx_input = find_inputs(&modules, "rx");
|
|
assert_eq!(rx_input.len(), 1);
|
|
let rx_input = rx_input[0];
|
|
assert!(modules[rx_input].as_any().is::<Conjunction>());
|
|
|
|
let rx_input_inputs = find_inputs(&modules, rx_input);
|
|
let cycles = rx_input_inputs
|
|
.into_iter()
|
|
.map(|s| find_output_cycle(modules.clone(), s))
|
|
.collect::<Vec<_>>();
|
|
|
|
dbg!(crate::day08::lcm(cycles.into_iter()));
|
|
}
|
|
|
|
fn parse_modules(s: &'static str) -> HashMap<&'static str, Box<dyn Module>> {
|
|
let mut m = HashMap::<&'static str, Box<dyn Module>>::new();
|
|
m.insert("output", Box::new(Output));
|
|
let mut conjunctions = vec![];
|
|
for l in s.trim().lines() {
|
|
let l = l.trim();
|
|
let (name, receivers) = l.split_once(" -> ").unwrap();
|
|
let receivers = receivers.split(", ").collect::<Vec<_>>();
|
|
let trimmed_name: &'static str;
|
|
let module: Box<dyn Module>;
|
|
if name == "broadcaster" {
|
|
trimmed_name = "broadcaster";
|
|
module = Box::new(Broadcaster { receivers });
|
|
} else if name.starts_with("%") {
|
|
trimmed_name = &name[1..];
|
|
module = Box::new(FlipFlop {
|
|
receivers,
|
|
state: false,
|
|
});
|
|
} else if name.starts_with("&") {
|
|
trimmed_name = &name[1..];
|
|
conjunctions.push(trimmed_name);
|
|
module = Box::new(Conjunction {
|
|
receivers,
|
|
inputs: HashMap::new(),
|
|
});
|
|
} else {
|
|
panic!("invalid name {}", name);
|
|
}
|
|
m.insert(trimmed_name, module);
|
|
}
|
|
for name in conjunctions {
|
|
let inputs = m
|
|
.iter()
|
|
.filter(|(_, v)| v.get_destinations().contains(&name))
|
|
.map(|(k, _)| (*k, false))
|
|
.collect::<HashMap<&'static str, bool>>();
|
|
let any = m.get_mut(name).unwrap().as_any_mut();
|
|
let conjunction = any.downcast_mut::<Conjunction>().unwrap();
|
|
conjunction.inputs = inputs;
|
|
}
|
|
m
|
|
}
|
|
|
|
#[derive(Debug, Clone, Copy)]
|
|
struct Pulse {
|
|
destination: &'static str,
|
|
value: bool,
|
|
}
|
|
|
|
trait Module: std::fmt::Debug {
|
|
fn get_destinations(&self) -> &[&'static str];
|
|
fn handle_pulse(&mut self, source: &'static str, value: bool) -> Vec<Pulse>;
|
|
fn as_any_mut(&mut self) -> &mut dyn std::any::Any;
|
|
fn as_any(&self) -> &dyn std::any::Any;
|
|
fn clone_module(&self) -> Box<dyn Module>;
|
|
}
|
|
|
|
#[derive(Debug, Clone, PartialEq, Eq)]
|
|
struct Broadcaster {
|
|
receivers: Vec<&'static str>,
|
|
}
|
|
|
|
impl Module for Broadcaster {
|
|
fn handle_pulse(&mut self, _source: &'static str, value: bool) -> Vec<Pulse> {
|
|
self.receivers
|
|
.iter()
|
|
.map(|r| Pulse {
|
|
destination: r,
|
|
value,
|
|
})
|
|
.collect()
|
|
}
|
|
|
|
fn get_destinations(&self) -> &[&'static str] {
|
|
&self.receivers
|
|
}
|
|
|
|
fn clone_module(&self) -> Box<dyn Module> {
|
|
Box::new(self.clone())
|
|
}
|
|
|
|
fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
|
|
self
|
|
}
|
|
|
|
fn as_any(&self) -> &dyn std::any::Any {
|
|
self
|
|
}
|
|
}
|
|
|
|
#[derive(Debug, Clone, PartialEq, Eq)]
|
|
struct FlipFlop {
|
|
receivers: Vec<&'static str>,
|
|
state: bool,
|
|
}
|
|
|
|
impl Module for FlipFlop {
|
|
fn handle_pulse(&mut self, _source: &'static str, value: bool) -> Vec<Pulse> {
|
|
if value {
|
|
return vec![];
|
|
}
|
|
self.state = !self.state;
|
|
self.receivers
|
|
.iter()
|
|
.map(|r| Pulse {
|
|
destination: r,
|
|
value: self.state,
|
|
})
|
|
.collect()
|
|
}
|
|
|
|
fn get_destinations(&self) -> &[&'static str] {
|
|
&self.receivers
|
|
}
|
|
|
|
fn clone_module(&self) -> Box<dyn Module> {
|
|
Box::new(self.clone())
|
|
}
|
|
|
|
fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
|
|
self
|
|
}
|
|
|
|
fn as_any(&self) -> &dyn std::any::Any {
|
|
self
|
|
}
|
|
}
|
|
|
|
#[derive(Debug, Clone, PartialEq, Eq)]
|
|
struct Conjunction {
|
|
receivers: Vec<&'static str>,
|
|
inputs: HashMap<&'static str, bool>,
|
|
}
|
|
|
|
impl Module for Conjunction {
|
|
fn handle_pulse(&mut self, source: &'static str, value: bool) -> Vec<Pulse> {
|
|
self.inputs.insert(source, value);
|
|
let output = !self.inputs.values().all(|b| *b);
|
|
self.receivers
|
|
.iter()
|
|
.map(|r| Pulse {
|
|
destination: r,
|
|
value: output,
|
|
})
|
|
.collect()
|
|
}
|
|
|
|
fn get_destinations(&self) -> &[&'static str] {
|
|
&self.receivers
|
|
}
|
|
|
|
fn clone_module(&self) -> Box<dyn Module> {
|
|
Box::new(self.clone())
|
|
}
|
|
|
|
fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
|
|
self
|
|
}
|
|
|
|
fn as_any(&self) -> &dyn std::any::Any {
|
|
self
|
|
}
|
|
}
|
|
|
|
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
|
|
struct Output;
|
|
|
|
impl Module for Output {
|
|
fn get_destinations(&self) -> &[&'static str] {
|
|
&[]
|
|
}
|
|
|
|
fn handle_pulse(&mut self, _source: &'static str, _value: bool) -> Vec<Pulse> {
|
|
vec![]
|
|
}
|
|
|
|
fn clone_module(&self) -> Box<dyn Module> {
|
|
Box::new(Output)
|
|
}
|
|
|
|
fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
|
|
self
|
|
}
|
|
|
|
fn as_any(&self) -> &dyn std::any::Any {
|
|
self
|
|
}
|
|
}
|
|
|
|
fn simulate(modules: &mut HashMap<&'static str, Box<dyn Module>>) -> (usize, usize) {
|
|
let mut pulses_to_send = VecDeque::from([(
|
|
"button",
|
|
Pulse {
|
|
destination: "broadcaster",
|
|
value: false,
|
|
},
|
|
)]);
|
|
let mut high = 0;
|
|
let mut low = 0;
|
|
// println!("button -low-> broadcaster");
|
|
while let Some((source, p)) = pulses_to_send.pop_front() {
|
|
if p.value {
|
|
high += 1;
|
|
} else {
|
|
low += 1;
|
|
}
|
|
let handler = p.destination;
|
|
let handling_module = modules.get_mut(handler);
|
|
if handling_module.is_none() {
|
|
// println!("no module {}", handler);
|
|
continue;
|
|
}
|
|
let new = handling_module.unwrap().handle_pulse(source, p.value);
|
|
for p in new {
|
|
// let value = if p.value { "high" } else { "low" };
|
|
// println!("{} -{}-> {}", handler, value, p.destination);
|
|
pulses_to_send.push_back((handler, p));
|
|
}
|
|
}
|
|
(high, low)
|
|
}
|
|
|
|
impl Clone for Box<dyn Module> {
|
|
fn clone(&self) -> Self {
|
|
self.clone_module()
|
|
}
|
|
}
|
|
|
|
fn simulate_one_thousand(mut modules: HashMap<&'static str, Box<dyn Module>>) -> usize {
|
|
let mut high = 0;
|
|
let mut low = 0;
|
|
for _ in 0..1000 {
|
|
let r = simulate(&mut modules);
|
|
high += r.0;
|
|
low += r.1;
|
|
}
|
|
high * low
|
|
}
|
|
|
|
fn find_inputs(
|
|
modules: &HashMap<&'static str, Box<dyn Module>>,
|
|
dest: &'static str,
|
|
) -> Vec<&'static str> {
|
|
let mut inputs = vec![];
|
|
for (name, module) in modules.iter() {
|
|
if module.get_destinations().contains(&dest) {
|
|
inputs.push(*name);
|
|
}
|
|
}
|
|
inputs
|
|
}
|
|
|
|
fn find_output_cycle(
|
|
mut modules: HashMap<&'static str, Box<dyn Module>>,
|
|
name: &'static str,
|
|
) -> usize {
|
|
let mut iterations = 0;
|
|
loop {
|
|
iterations += 1;
|
|
|
|
let mut pulses_to_send = VecDeque::from([(
|
|
"button",
|
|
Pulse {
|
|
destination: "broadcaster",
|
|
value: false,
|
|
},
|
|
)]);
|
|
while let Some((source, p)) = pulses_to_send.pop_front() {
|
|
if !p.value && p.destination == name {
|
|
return iterations;
|
|
}
|
|
let handler = p.destination;
|
|
if let Some(handling_module) = modules.get_mut(handler) {
|
|
let new = handling_module.handle_pulse(source, p.value);
|
|
for p in new {
|
|
pulses_to_send.push_back((handler, p));
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|