Some Assembly Required

## --- 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`?

Some Assembly Required
``````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),
}

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(parse_token).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] {
}
}
}
let mut ovalues = HashMap::new();
let res1 = *values1.entry(Tok::Id("a".to_string())).or_default();
ovalues.insert(Tok::Id("b".to_string()), res1);
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>,
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);
*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()),
}
}
}