heh
| -rw-r--r-- | Cargo.toml | 1 | ||||
| -rw-r--r-- | src/main.rs | 184 | ||||
| -rw-r--r-- | src/util.rs | 38 |
3 files changed, 148 insertions, 75 deletions
@@ -6,6 +6,7 @@ edition = "2021" # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html [dependencies] +arrayvec = "0.7.4" itertools = "0.12.0" memchr = "2.6.4" [profile.release] diff --git a/src/main.rs b/src/main.rs index 30af69d..d94ddea 100644 --- a/src/main.rs +++ b/src/main.rs @@ -17,27 +17,31 @@ extern crate test; pub mod util; +use std::mem::MaybeUninit; + +use arrayvec::ArrayVec; pub use util::prelude::*; #[derive(Eq, Debug, PartialEq)] -enum ModuleT<'a> { +enum ModuleT { Flip(bool), - Cj(HashMap<&'a [u8], bool>), + Cj(ArrayVec<(u16, bool), 11>), Untyped, } -struct Module<'a> { - ty: ModuleT<'a>, - output: Box<[&'a [u8]]>, +#[derive(Debug)] +struct Module { + ty: ModuleT, + output: Box<[u16]>, } -impl<'a> Module<'a> { +impl Module { pub fn pass<'b>( &mut self, - myname: &'a [u8], - from: &[u8], + myname: u16, + from: u16, x: bool, - stack: &'b mut VecDeque<(&'a [u8], &'a [u8], bool)>, + stack: &'b mut VecDeque<(u16, u16, bool)>, ) { match self.ty { ModuleT::Flip(ref mut state) => { @@ -45,19 +49,19 @@ impl<'a> Module<'a> { return; } *state = !*state; - for o in &*self.output { + for &o in &*self.output { stack.push_back((myname, o, *state)); } } ModuleT::Cj(ref mut mem) => { - *mem.get_mut(from).unwrap() = x; - let s = !mem.values().all(|&x| x); - for o in &*self.output { + mem.iter_mut().find(|(x, _)| x == &from).unwrap().1 = x; + let s = !mem.iter().all(|&(_, x)| x); + for &o in &*self.output { stack.push_back((myname, o, s)); } } ModuleT::Untyped => { - for x in &*self.output { + for &x in &*self.output { stack.push_back((myname, x, false)); } } @@ -76,58 +80,108 @@ fn split<'a>( }) } -fn parse<'a>( - i: impl Iterator<Item = (&'a [u8], impl Iterator<Item = &'a [u8]>)>, -) -> HashMap<&'a [u8], Module<'a>> { - let mut modules = HashMap::new(); +impl<'a, T> std::ops::IndexMut<u16> for Hold<T> { + fn index_mut(&mut self, index: u16) -> &mut Self::Output { + unsafe { self.names.get_unchecked_mut(index.nat()).assume_init_mut() } + } +} + +impl<'a, T> std::ops::Index<u16> for Hold<T> { + type Output = T; + fn index(&self, index: u16) -> &Self::Output { + unsafe { self.names.get_unchecked(index.nat()).assume_init_ref() } + } +} + +struct Hold<T> { + names: [MaybeUninit<T>; 26 * 26], +} + +impl<'a, T> std::ops::IndexMut<&[u8]> for Hold<T> { + fn index_mut(&mut self, index: &[u8]) -> &mut Self::Output { + unsafe { + self.names + .get_unchecked_mut(hash(index).nat()) + .assume_init_mut() + } + } +} + +impl<'a, T> std::ops::Index<&[u8]> for Hold<T> { + type Output = T; + + fn index(&self, index: &[u8]) -> &Self::Output { + unsafe { + self.names + .get_unchecked(hash(index).nat()) + .assume_init_ref() + } + } +} + +fn hash(x: &[u8]) -> u16 { + if let &[a, b] = x { + (a - b'a').widen() * 26 + (b - b'a').widen() + } else { + 0 + } +} + +impl<T> Hold<T> { + #[inline] + fn new() -> Self { + Self { + names: [const { MaybeUninit::uninit() }; 26 * 26], + } + } + + fn set(&mut self, index: u16, to: T) { + unsafe { self.names.get_unchecked_mut(index.nat()).write(to) }; + } +} + +fn parse<'a>(i: impl Iterator<Item = (&'a [u8], impl Iterator<Item = &'a [u8]>)>) -> Hold<Module> { + let mut modules = Hold::new(); + let mut backwards = [const { vec![] }; 26 * 26]; let mut rest = vec![]; i.map(|(mut from, to)| { - let to: Box<_> = to.collect(); - match from[0] { + let to: Box<[u16]> = to.map(hash).collect(); + let t = match C! { from[0] } { b'%' => { from.skip(1); - modules.insert( - from, - Module { - ty: ModuleT::Flip(false), - output: to, - }, - ); + Some(ModuleT::Flip(false)) } b'&' => { from.skip(1); - rest.push((from, to)); - return; - } - _ => { - modules.insert( - from, - Module { - ty: ModuleT::Untyped, - output: to, - }, - ); + None } + _ => Some(ModuleT::Untyped), }; + let f = hash(from); + for &elem in &*to { + let x = C! { &mut backwards[elem.nat()]}; + if !x.contains(&f) { + x.push(f); + }; + } + + if let Some(ty) = t { + modules.set(f, Module { ty, output: to }); + } else { + rest.push((f, to)); + } }) .Θ(); - let r = rest.clone(); for (name, output) in rest { - let mut inps: HashMap<&[u8], bool> = modules - .iter() - .filter(|(_, x)| x.output.contains(&name)) - .map(|(x, _)| (*x, false)) - .collect(); - inps.extend( - r.iter() - .filter(|(x, _)| *x != name) - .filter(|(_, x)| x.contains(&name)) - .map(|(x, _)| (*x, false)), - ); - modules.insert( + modules.set( name, Module { - ty: ModuleT::Cj(inps), + ty: ModuleT::Cj( + C! { backwards[name.nat()] } + .iter() + .map(|&x| (x, false)) + .collect(), + ), output, }, ); @@ -137,18 +191,18 @@ fn parse<'a>( fn p1(i: &str) -> usize { let mut modules = parse(split(i.行())); - fn push(modules: &mut HashMap<&[u8], Module<'_>>) -> (usize, usize) { + fn push(modules: &mut Hold<Module>) -> (usize, usize) { let (mut lo, mut hi) = (0, 0); let mut stack = VecDeque::new(); - stack.push_back((&b"upstairs"[..], &b"broadcaster"[..], false)); + stack.push_back((0, 0, false)); while let Some((m, to, x)) = stack.pop_front() { if x { hi += 1 } else { lo += 1; } - if let Some(o) = modules.get_mut(to) { - o.pass(to, m, x, &mut stack) + if to != hash(b"rx") { + modules[to].pass(to, m, x, &mut stack) }; } (lo, hi) @@ -164,21 +218,21 @@ fn p1(i: &str) -> usize { fn p2(i: &str) -> u64 { let mut modules = parse(split(i.行())); let mut from = HashMap::from([ - (&b"xp"[..], None::<u64>), - (&b"fc"[..], None), - (&b"dd"[..], None), - (&b"fh"[..], None), + (hash(&b"xp"[..]), None::<u64>), + (hash(&b"fc"[..]), None), + (hash(&b"dd"[..]), None), + (hash(&b"fh"[..]), None), ]); let mut lens = vec![]; for when in 0.. { let mut stack = VecDeque::new(); - stack.push_back((&b"upstairs"[..], &b"broadcaster"[..], false)); + stack.push_back((0, 0, false)); while let Some((m, to, x)) = stack.pop_front() { - if !x && let Some(x) = from.get_mut(to) { + if !x && let Some(x) = from.get_mut(&to) { if let Some(y) = x { lens.push(when - *y); - from.remove(to); + from.remove(&to); if from.len() == 0 { return lens.iter().product(); } @@ -186,8 +240,8 @@ fn p2(i: &str) -> u64 { *x = Some(when); } } - if let Some(o) = modules.get_mut(to) { - o.pass(to, m, x, &mut stack) + if to != hash(b"rx") { + modules[to].pass(to, m, x, &mut stack) }; } } diff --git a/src/util.rs b/src/util.rs index eeea84e..30362ff 100644 --- a/src/util.rs +++ b/src/util.rs @@ -46,7 +46,13 @@ macro_rules! C { ($buf:ident[$n:expr]) => {{ #[allow(unused_unsafe)] unsafe { - *$buf.get_unchecked($n) + $buf.get_unchecked($n) + } + }}; + (&mut $buf:ident[$n:expr]) => {{ + #[allow(unused_unsafe)] + unsafe { + $buf.get_unchecked_mut($n) } }}; ($buf:ident[$a:expr] = $rbuf:ident[$b:expr]) => { @@ -1032,17 +1038,29 @@ impl std::fmt::Display for PrintU8s<'_> { } } +struct PrintManyU8s<'a, T: AsRef<[u8]>>(&'a [T]); +impl<T: AsRef<[u8]>> std::fmt::Display for PrintManyU8s<'_, T> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + for row in self.0.as_ref() { + write!(f, "{},", row.as_ref().p())?; + } + Ok(()) + } +} +impl Printable for [Vec<u8>] { + fn p(&self) -> impl std::fmt::Display { + PrintManyU8s(self) + } +} + +impl Printable for [&&[u8]] { + fn p(&self) -> impl std::fmt::Display { + PrintManyU8s(self) + } +} + impl Printable for [&[u8]] { fn p(&self) -> impl std::fmt::Display { - struct PrintManyU8s<'a>(&'a [&'a [u8]]); - impl std::fmt::Display for PrintManyU8s<'_> { - fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { - for row in self.0 { - write!(f, "{},", row.p())?; - } - Ok(()) - } - } PrintManyU8s(self) } } |