year2015/
day07.rs

1use std::collections::HashMap;
2use utils::prelude::*;
3
4/// Logic gates.
5///
6/// Use indexes instead of wire names for performance.
7/// To avoid adding a special type for the gates with constant inputs, pack u16 constants into the
8/// highest usize values. This should be fine on any platform with at least 32-bit pointers.
9#[derive(Clone, Debug)]
10pub struct Day07 {
11    wires: Vec<Signal>,
12    a_idx: usize,
13    b_idx: usize,
14}
15
16#[derive(Copy, Clone, Debug)]
17enum Signal {
18    Wire(usize),
19    And(usize, usize),
20    Or(usize, usize),
21    Not(usize),
22    LShift(usize, u8),
23    RShift(usize, u8),
24}
25
26impl Day07 {
27    const U16_CONST_MASK: usize = usize::MAX & !(u16::MAX as usize);
28
29    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
30        let mut indexes = HashMap::new();
31        for (i, l) in input.lines().enumerate() {
32            let Some((_, name)) = l.rsplit_once(" -> ") else {
33                return Err(InputError::new(input, l, "line missing \" -> \""));
34            };
35            indexes.insert(name.as_bytes(), i);
36        }
37        if indexes.len() >= Self::U16_CONST_MASK {
38            return Err(InputError::new(input, 0, "too many wires"));
39        }
40
41        let parse_wire = parser::one_of((
42            parser::take_while(u8::is_ascii_lowercase)
43                .map_res(|v| indexes.get(v).copied().ok_or("wire not found")),
44            parser::u16().map(|v| Self::U16_CONST_MASK | v as usize),
45        ));
46
47        let wires = parser::one_of((
48            parse_wire.with_prefix("NOT ").map(Signal::Not),
49            parse_wire
50                .with_suffix(" AND ")
51                .then(parse_wire)
52                .map(|(a, b)| Signal::And(a, b)),
53            parse_wire
54                .with_suffix(" OR ")
55                .then(parse_wire)
56                .map(|(a, b)| Signal::Or(a, b)),
57            parse_wire
58                .with_suffix(" RSHIFT ")
59                .then(parser::u8())
60                .map(|(a, b)| Signal::RShift(a, b)),
61            parse_wire
62                .with_suffix(" LSHIFT ")
63                .then(parser::u8())
64                .map(|(a, b)| Signal::LShift(a, b)),
65            parse_wire.map(Signal::Wire),
66        ))
67        .with_suffix(" -> ")
68        .with_suffix(parser::take_while(u8::is_ascii_lowercase))
69        .parse_lines(input)?;
70
71        let Some(&a_idx) = indexes.get(&b"a"[..]) else {
72            return Err(InputError::new(input, 0, "missing 'a' wire"));
73        };
74        let Some(&b_idx) = indexes.get(&b"b"[..]) else {
75            return Err(InputError::new(input, 0, "missing 'b' wire"));
76        };
77
78        Ok(Self {
79            wires,
80            a_idx,
81            b_idx,
82        })
83    }
84
85    #[must_use]
86    pub fn part1(&self) -> u16 {
87        self.calculate(self.a_idx, &mut vec![None; self.wires.len()])
88    }
89
90    #[must_use]
91    pub fn part2(&self) -> u16 {
92        let mut cache = vec![None; self.wires.len()];
93        cache[self.b_idx] = Some(self.part1());
94        self.calculate(self.a_idx, &mut cache)
95    }
96
97    fn calculate(&self, idx: usize, cache: &mut [Option<u16>]) -> u16 {
98        if idx & Self::U16_CONST_MASK == Self::U16_CONST_MASK {
99            idx as u16
100        } else if let Some(v) = cache[idx] {
101            v
102        } else {
103            let v = match self.wires[idx] {
104                Signal::Wire(l) => self.calculate(l, cache),
105                Signal::And(l, r) => self.calculate(l, cache) & self.calculate(r, cache),
106                Signal::Or(l, r) => self.calculate(l, cache) | self.calculate(r, cache),
107                Signal::Not(l) => !self.calculate(l, cache),
108                Signal::LShift(l, by) => self.calculate(l, cache) << by,
109                Signal::RShift(l, by) => self.calculate(l, cache) >> by,
110            };
111            cache[idx] = Some(v);
112            v
113        }
114    }
115}
116
117examples!(Day07 -> (u16, u16) []);
year2015/day07.rs

year2015/
day07.rs
