Skip to main content

year2015/
day07.rs

1use utils::hash::IndexedSet;
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 = IndexedSet::with_capacity(512);
32        for l in input.lines() {
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            if !indexes.insert(name) {
40                return Err(InputError::new(input, l, "duplicate wire"));
41            }
42        }
43        if indexes.len() >= Self::U16_CONST_MASK {
44            return Err(InputError::new(input, 0, "too many wires"));
45        }
46
47        let parse_wire = parser::one_of((
48            parser::tinystr4(u8::is_ascii_lowercase)
49                .map_res(|v| indexes.index_of(&v).ok_or("wire not found")),
50            parser::u16().map(|v| Self::U16_CONST_MASK | v as usize),
51        ));
52
53        let wires = parser::one_of((
54            parse_wire.with_prefix("NOT ").map(Signal::Not),
55            parse_wire
56                .with_suffix(" AND ")
57                .then(parse_wire)
58                .map(|(a, b)| Signal::And(a, b)),
59            parse_wire
60                .with_suffix(" OR ")
61                .then(parse_wire)
62                .map(|(a, b)| Signal::Or(a, b)),
63            parse_wire
64                .with_suffix(" RSHIFT ")
65                .then(parser::u8())
66                .map(|(a, b)| Signal::RShift(a, b)),
67            parse_wire
68                .with_suffix(" LSHIFT ")
69                .then(parser::u8())
70                .map(|(a, b)| Signal::LShift(a, b)),
71            parse_wire.map(Signal::Wire),
72        ))
73        .with_suffix(" -> ")
74        .with_suffix(parser::tinystr4(u8::is_ascii_lowercase))
75        .parse_lines(input)?;
76
77        let Some(a_idx) = indexes.index_of(&TinyStr4::from_const(b"a")) else {
78            return Err(InputError::new(input, 0, "missing 'a' wire"));
79        };
80        let Some(b_idx) = indexes.index_of(&TinyStr4::from_const(b"b")) else {
81            return Err(InputError::new(input, 0, "missing 'b' wire"));
82        };
83
84        Ok(Self {
85            wires,
86            a_idx,
87            b_idx,
88        })
89    }
90
91    #[must_use]
92    pub fn part1(&self) -> u16 {
93        self.calculate(self.a_idx, &mut vec![None; self.wires.len()])
94    }
95
96    #[must_use]
97    pub fn part2(&self) -> u16 {
98        let mut cache = vec![None; self.wires.len()];
99        cache[self.b_idx] = Some(self.part1());
100        self.calculate(self.a_idx, &mut cache)
101    }
102
103    fn calculate(&self, idx: usize, cache: &mut [Option<u16>]) -> u16 {
104        if idx & Self::U16_CONST_MASK == Self::U16_CONST_MASK {
105            idx as u16
106        } else if let Some(v) = cache[idx] {
107            v
108        } else {
109            let v = match self.wires[idx] {
110                Signal::Wire(l) => self.calculate(l, cache),
111                Signal::And(l, r) => self.calculate(l, cache) & self.calculate(r, cache),
112                Signal::Or(l, r) => self.calculate(l, cache) | self.calculate(r, cache),
113                Signal::Not(l) => !self.calculate(l, cache),
114                Signal::LShift(l, by) => self.calculate(l, cache) << by,
115                Signal::RShift(l, by) => self.calculate(l, cache) >> by,
116            };
117            cache[idx] = Some(v);
118            v
119        }
120    }
121}
122
123examples!(Day07 -> (u16, u16) []);