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//! backward. 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::parse::*;
10use Gate::*;
11
12type Input = (u32, u32);
13
14#[derive(Clone, Copy)]
15enum Gate {
16    Constant(u32),
17    Wire(usize),
18    Not(usize),
19    Bit(usize),
20    And(usize, usize),
21    Or(usize, usize),
22    LeftShift(usize, u32),
23    RightShift(usize, u32),
24}
25
26pub fn parse(input: &str) -> Input {
27    let mut tokens = input.split_ascii_whitespace();
28    let mut circuit = vec![Constant(0); 729];
29
30    while let (Some(first), Some(second)) = (tokens.next(), tokens.next()) {
31        let gate = if first == "NOT" {
32            let _third = tokens.next().unwrap();
33            Not(to_index(second))
34        } else if second == "->" {
35            if first.as_bytes()[0].is_ascii_digit() {
36                Constant(first.unsigned())
37            } else {
38                Wire(to_index(first))
39            }
40        } else {
41            let third = tokens.next().unwrap();
42            let _fourth = tokens.next().unwrap();
43
44            match second {
45                "AND" if first == "1" => Bit(to_index(third)),
46                "AND" => And(to_index(first), to_index(third)),
47                "OR" => Or(to_index(first), to_index(third)),
48                "LSHIFT" => LeftShift(to_index(first), third.unsigned()),
49                "RSHIFT" => RightShift(to_index(first), third.unsigned()),
50                _ => unreachable!(),
51            }
52        };
53
54        let wire = tokens.next().unwrap();
55        circuit[to_index(wire)] = gate;
56    }
57
58    let mut cache = vec![u32::MAX; 729];
59    let part_one = signal(to_index("a"), &circuit, &mut cache);
60
61    cache.fill(u32::MAX);
62    cache[to_index("b")] = part_one;
63    let part_two = signal(to_index("a"), &circuit, &mut cache);
64
65    (part_one, part_two)
66}
67
68fn signal(key: usize, circuit: &[Gate], cache: &mut [u32]) -> u32 {
69    if cache[key] != u32::MAX {
70        return cache[key];
71    }
72
73    let result = match circuit[key] {
74        Constant(c) => c,
75        Wire(w) => signal(w, circuit, cache),
76        Not(w) => 0xffff & !signal(w, circuit, cache),
77        Bit(r) => 1 & signal(r, circuit, cache),
78        And(l, r) => signal(l, circuit, cache) & signal(r, circuit, cache),
79        Or(l, r) => signal(l, circuit, cache) | signal(r, circuit, cache),
80        LeftShift(w, n) => 0xffff & (signal(w, circuit, cache) << n),
81        RightShift(w, n) => signal(w, circuit, cache) >> n,
82    };
83
84    cache[key] = result;
85    result
86}
87
88pub fn part1(input: &Input) -> u32 {
89    input.0
90}
91
92pub fn part2(input: &Input) -> u32 {
93    input.1
94}
95
96/// Convert one or two character string to an index.
97fn to_index(s: &str) -> usize {
98    s.bytes().fold(0, |acc, b| 27 * acc + usize::from(b - b'a' + 1))
99}
aoc/year2015/day07.rs

aoc/year2015/
day07.rs
