1use utils::hash::IndexedSet;
2use utils::prelude::*;
3use utils::str::TinyStr4;
4
5#[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) []);