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),
}

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(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] {
                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()),
        }
    }
}

adventofcode!(test, "input.txt", "output.txt");