--- Day 7: Some Assembly Required ---
This year, Santa brought little Bobby Tables a set of wires and bitwise logic gates! Unfortunately, little Bobby is a little under the recommended age range, and he needs help assembling the circuit.
Each wire has an identifier (some lowercase letters) and can carry a 16-bit signal (a number from 0
to 65535
). A signal is provided to each wire by a gate, another wire, or some specific value. Each wire can only get a signal from one source, but can provide its signal to multiple destinations. A gate provides no signal until all of its inputs have a signal.
The included instructions booklet describes how to connect the parts together: x AND y -> z
means to connect wires x
and y
to an AND gate, and then connect its output to wire z
.
For example:
123 -> x
means that the signal 123
is provided to wire x
.
x AND y -> z
means that the bitwise AND of wire x
and wire y
is provided to wire z
.
p LSHIFT 2 -> q
means that the value from wire p
is left-shifted by 2
and then provided to wire q
.
NOT e -> f
means that the bitwise complement of the value from wire e
is provided to wire f
.
Other possible gates include OR
(bitwise OR) and RSHIFT
(right-shift). If, for some reason, you'd like to emulate the circuit instead, almost all programming languages (for example, C, JavaScript, or Python) provide operators for these gates.
For example, here is a simple circuit:
123 -> x
456 -> y
x AND y -> d
x OR y -> e
x LSHIFT 2 -> f
y RSHIFT 2 -> g
NOT x -> h
NOT y -> i
After it is run, these are the signals on the wires:
d: 72
e: 507
f: 492
g: 114
h: 65412
i: 65079
x: 123
y: 456
In little Bobby's kit's instructions booklet (provided as your puzzle input), what signal is ultimately provided to wire a
?
Rust Solution
use rustgym_util::*;
use std::collections::HashMap;
use std::collections::VecDeque;
use std::fmt::Write;
use std::io::*;
#[derive(Eq, PartialEq, Clone, Hash, Debug)]
enum Tok {
Id(String),
Val(u16),
Op(char),
}
pub fn solve(reader: &mut dyn BufRead, writer: &mut dyn Write) {
let it = reader.lines().map(|l| l.unwrap());
let mut stmt: HashMap<Tok, Vec<Tok>> = HashMap::new();
let mut adj: HashMap<Tok, Vec<Tok>> = HashMap::new();
let mut values1: HashMap<Tok, u16> = HashMap::new();
let mut values2: HashMap<Tok, u16> = HashMap::new();
for line in it {
let mut tokens: Vec<Tok> = line.split_whitespace().map(|s| parse_token(s)).collect();
let last = tokens.pop().unwrap();
tokens.pop();
stmt.insert(last.clone(), tokens.to_vec());
for i in 0..tokens.len() {
if let Tok::Id(_) = tokens[i] {
adj.entry(tokens[i].clone()).or_default().push(last.clone());
}
}
}
let mut ovalues = HashMap::new();
eval(&mut values1, &adj, &stmt, &ovalues);
let res1 = *values1.entry(Tok::Id("a".to_string())).or_default();
ovalues.insert(Tok::Id("b".to_string()), res1);
eval(&mut values2, &adj, &stmt, &ovalues);
let res2 = *values2.entry(Tok::Id("a".to_string())).or_default();
writeln!(writer, "{}", res1).unwrap();
writeln!(writer, "{}", res2).unwrap();
}
fn eval(
values: &mut HashMap<Tok, u16>,
adj: &HashMap<Tok, Vec<Tok>>,
stmt: &HashMap<Tok, Vec<Tok>>,
o: &HashMap<Tok, u16>,
) {
let mut indegree: HashMap<Tok, usize> = HashMap::new();
let mut queue: VecDeque<Tok> = VecDeque::new();
for (u, vs) in adj {
indegree.entry(u.clone()).or_default();
for v in vs {
*indegree.entry(v.clone()).or_default() += 1;
}
}
for (tok, val) in indegree.iter() {
if *val == 0 {
queue.push_back(tok.clone());
}
}
while let Some(tok) = queue.pop_front() {
*values.entry(tok.clone()).or_default() = eval_stmt(&stmt[&tok], &values, o);
for v in adj.get(&tok).unwrap_or(&vec![]) {
*indegree.entry(v.clone()).or_default() -= 1;
if indegree[v] == 0 {
queue.push_back(v.clone());
}
}
}
}
fn eval_stmt(stmt: &[Tok], values: &HashMap<Tok, u16>, o: &HashMap<Tok, u16>) -> u16 {
match stmt.len() {
1 => eval_tok(&stmt[0], values, o),
2 => !eval_tok(&stmt[1], values, o),
3 => match stmt[1] {
Tok::Op('&') => eval_tok(&stmt[0], values, o) & eval_tok(&stmt[2], values, o),
Tok::Op('|') => eval_tok(&stmt[0], values, o) | eval_tok(&stmt[2], values, o),
Tok::Op('<') => eval_tok(&stmt[0], values, o) << eval_tok(&stmt[2], values, o),
Tok::Op('>') => eval_tok(&stmt[0], values, o) >> eval_tok(&stmt[2], values, o),
_ => panic!(),
},
_ => panic!(),
}
}
fn eval_tok(tok: &Tok, values: &HashMap<Tok, u16>, o: &HashMap<Tok, u16>) -> u16 {
match tok.clone() {
Tok::Val(val) => val,
Tok::Id(_) => {
if let Some(&val) = o.get(tok) {
val
} else {
values[&tok]
}
}
_ => panic!(),
}
}
fn parse_token(s: &str) -> Tok {
if let Ok(val) = s.parse::<u16>() {
Tok::Val(val)
} else {
match s {
"AND" => Tok::Op('&'),
"OR" => Tok::Op('|'),
"LSHIFT" => Tok::Op('<'),
"RSHIFT" => Tok::Op('>'),
"NOT" => Tok::Op('!'),
"->" => Tok::Op('='),
_ => Tok::Id(s.to_string()),
}
}
}
advent_of_code!(test, "input.txt", "output.txt");
Having problems with this solution? Click here to submit an issue on github.