aoc/year2015/
day07.rs

1//! # Some Assembly Required
2//!
3//! To obtain the result we recursively compute the inputs starting at gate `a` and working
4//! backwards. To make things faster we memoize the result of each wire in a cache, so that each
5//! wire is computed at most once.
6//!
7//! For part two we pre-seed the value of `b` in the cache with the result from part one then
8//! re-run the same process.
9use crate::util::hash::*;
10use crate::util::parse::*;
11
12type Result = (u16, u16);
13
14enum Gate<'a> {
15    Wire(&'a str),
16    Not(&'a str),
17    And(&'a str, &'a str),
18    Or(&'a str, &'a str),
19    LeftShift(&'a str, u16),
20    RightShift(&'a str, u16),
21}
22
23pub fn parse(input: &str) -> Result {
24    let mut tokens = input.split_ascii_whitespace();
25    let mut circuit = FastMap::new();
26
27    while let (Some(first), Some(second)) = (tokens.next(), tokens.next()) {
28        let gate = if first == "NOT" {
29            let _third = tokens.next().unwrap();
30            Gate::Not(second)
31        } else if second == "->" {
32            Gate::Wire(first)
33        } else {
34            let third = tokens.next().unwrap();
35            let _fourth = tokens.next().unwrap();
36
37            match second {
38                "AND" => Gate::And(first, third),
39                "OR" => Gate::Or(first, third),
40                "LSHIFT" => Gate::LeftShift(first, third.unsigned()),
41                "RSHIFT" => Gate::RightShift(first, third.unsigned()),
42                _ => unreachable!(),
43            }
44        };
45
46        let wire = tokens.next().unwrap();
47        circuit.insert(wire, gate);
48    }
49
50    let mut cache = FastMap::new();
51    let result1 = signal("a", &circuit, &mut cache);
52
53    cache.clear();
54    cache.insert("b", result1);
55    let result2 = signal("a", &circuit, &mut cache);
56
57    (result1, result2)
58}
59
60fn signal<'a>(
61    key: &'a str,
62    circuit: &FastMap<&'a str, Gate<'a>>,
63    cache: &mut FastMap<&'a str, u16>,
64) -> u16 {
65    if let Some(result) = cache.get(key) {
66        return *result;
67    }
68
69    let result = if key.chars().next().unwrap().is_ascii_digit() {
70        key.unsigned()
71    } else {
72        match circuit[key] {
73            Gate::Wire(w) => signal(w, circuit, cache),
74            Gate::Not(w) => !signal(w, circuit, cache),
75            Gate::And(l, r) => signal(l, circuit, cache) & signal(r, circuit, cache),
76            Gate::Or(l, r) => signal(l, circuit, cache) | signal(r, circuit, cache),
77            Gate::LeftShift(w, n) => signal(w, circuit, cache) << n,
78            Gate::RightShift(w, n) => signal(w, circuit, cache) >> n,
79        }
80    };
81
82    cache.insert(key, result);
83    result
84}
85
86pub fn part1(input: &Result) -> u16 {
87    input.0
88}
89
90pub fn part2(input: &Result) -> u16 {
91    input.1
92}
aoc/year2015/day07.rs

aoc/year2015/
day07.rs
