year2015/
day07.rs

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

year2015/
day07.rs
