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 self::Gate::*;
10use crate::util::parse::*;
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
68pub fn part1(input: &Input) -> u32 {
69    input.0
70}
71
72pub fn part2(input: &Input) -> u32 {
73    input.1
74}
75
76fn signal(key: usize, circuit: &[Gate], cache: &mut [u32]) -> u32 {
77    if cache[key] != u32::MAX {
78        return cache[key];
79    }
80
81    let result = match circuit[key] {
82        Constant(c) => c,
83        Wire(w) => signal(w, circuit, cache),
84        Not(w) => 0xffff & !signal(w, circuit, cache),
85        Bit(r) => 1 & signal(r, circuit, cache),
86        And(l, r) => signal(l, circuit, cache) & signal(r, circuit, cache),
87        Or(l, r) => signal(l, circuit, cache) | signal(r, circuit, cache),
88        LeftShift(w, n) => 0xffff & (signal(w, circuit, cache) << n),
89        RightShift(w, n) => signal(w, circuit, cache) >> n,
90    };
91
92    cache[key] = result;
93    result
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
