heh
| -rw-r--r-- | src/inp.txt | 42 | ||||
| -rw-r--r-- | src/main.rs | 160 | ||||
| -rw-r--r-- | src/util.rs | 62 |
3 files changed, 117 insertions, 147 deletions
diff --git a/src/inp.txt b/src/inp.txt index c0caf6e..ba75626 100644 --- a/src/inp.txt +++ b/src/inp.txt @@ -1,41 +1 @@ -21056789894321015012980123498787601045687 -32346543765601156703474544567896012138796 -10107632659892349821563678989345643029655 -23218101256781015430412101071234754910544 -14569870345432016321003012560109867801033 -05678963256789127879854303456078105932122 -18723450109898038910765210010563254541001 -69011201298788945125898998323454569679852 -78760345345654876034787677401235378089760 -89456896012503876965014586512765432123601 -32387987003412965872123298703890101984512 -01291876121101234989456107654965278854603 -00180145030980325678327890217874369763254 -14343232145671013454310691307893454610169 -23432165430110302169234582456732108905678 -96547078923231231078105673454321097214523 -87678432214348940987017894765870986341014 -96589541009857654320123765891963475498765 -01434630111766789010432143210452560167876 -32345721210951999016549054789301001456965 -21076890129810878321678945643219812332109 -78789001234723765430321238756106734323458 -09654160345654210389210109987005125010767 -12323271657601345678780125678014056541893 -25414987798542343456690034329123987932012 -56905677810439652987501145016510345801101 -67856298923128721987432156987421256789210 -22347107654098910876543087870330107654301 -11298231012347654305678898981278798987652 -00109545691056763211219767874569678690343 -12065456783345894320105656913450569541289 -43874321092132101899234541002321256632176 -54930010561001234788765432211056746789045 -67821123472390545654123101347849839874330 -78934010589487698763034567456931028765221 -67785697696590101672105698741022210540100 -58696788787781234589789789012013307632101 -49545459810170301075674654323454458989032 -30432365923965432165463210498569567976543 -21021876854876523678354112347678678875301 -30010966763987014589210001456565589765432 +4022724 951333 0 21633 5857 97 702 6 diff --git a/src/main.rs b/src/main.rs index ccb655b..38c0cdd 100644 --- a/src/main.rs +++ b/src/main.rs @@ -12,8 +12,10 @@ slice_swap_unchecked, generic_const_exprs, iter_array_chunks, + if_let_guard, get_many_mut, maybe_uninit_uninit_array, + once_cell_get_mut, iter_collect_into, hint_assert_unchecked, let_chains, @@ -31,106 +33,80 @@ )] extern crate test; pub mod util; -use util::countg; +use std::sync::OnceLock; + pub use util::prelude::*; #[no_mangle] pub fn run(i: &str) -> impl Display { let i = i.as_bytes(); - let size = memchr::memchr(b'\n', i).ψ(); - let max = size * (size + 1); - unsafe { core::hint::assert_unchecked(i.len() == max) }; - let get = |j: u16| (j < max as u16).then(|| i[j as usize]); - - // fimg::Image::<Vec<u8>, 1>::build(SIZE as _, SIZE as _) - // .buf( - // grid.iter() - // .flat_map(|x| &x[..SIZE]) - // .map(|x| (((*x - b'0') as f32 / 10.0) * 255.0) as u8) - // .collect_vec(), - // ) - // .scale::<fimg::scale::Nearest>(SIZE as u32 * 8, SIZE as u32 * 8) - // .save("hmm.png"); - let mut tot = 0; - - pub fn p2( - start: u16, - graph: &mut impl Fn(u16) -> [u16; 4], - ok: &mut impl Fn(u16, u16) -> bool, - end: &mut impl Fn(u16) -> bool, - dp: &mut [u16], - ) -> u16 { - if end(start) { - return 1; - } else { - graph(start) - .into_iter() - .map(|x| { - if ok(start, x) { - #[allow(irrefutable_let_patterns)] - if let x = dp[x as usize] - && x != 0xffff - { - return x; - } - let n = p2(x, graph, ok, end, dp); - dp[x as usize] = n; - n - } else { - 0 - } - }) - .sum() + let mut input = i.κ::<u64>().collect_vec(); + input.reserve_exact(30000); + for _ in 0..25 { + let i = input.clone(); + unsafe { input.set_len(0) }; + for stone in i { + match stone { + 0 => input.push(1), + n if let ͱ = n.ͱ() as usize + && ͱ % 2 == 0 => + { + let pow = util::powers[ͱ / 2]; + input.push(n % pow); + input.push(n / pow); + } + n => input.push(n * 2024), + } } } + input.len() +} - pub fn p1( - start: u16, - graph: &mut impl Fn(u16) -> [u16; 4], - ok: &mut impl Fn(u16, u16) -> bool, - end: &mut impl Fn(u16) -> bool, - reached: &mut [u8], - ) -> u16 { - if end(start) && reached[start as usize] == 0 { - reached[start as usize] = 1; - return 1; - } else { - graph(start) - .into_iter() - .map(|x| { - if ok(start, x) { - p1(x, graph, ok, end, reached) - } else { - 0 - } - }) - .sum() +#[no_mangle] +pub unsafe fn p2(i: &str) -> impl Display { + let i = i.as_bytes().trim_ascii_end(); + let mut o = [0u64; 10]; + let n = reading::κ(i, &mut o); + static mut map: OnceLock<HashMap<(u64, u8), u64>> = OnceLock::new(); + unsafe { + match map.get_mut() { + Some(x) => x.clear(), + None => drop(map.get_or_init(|| { + HashMap::with_capacity_and_hasher(150000, rustc_hash::FxBuildHasher::default()) + })), } + }; + fn rocc(one: u64, iters: u8) -> u64 { + if let Some(&x) = unsafe { map.get_mut().ψ().get(&(one, iters)) } { + return x; + } + let answer = { + match iters.checked_sub(1) { + Some(iters) if one == 0 => rocc(1, iters), + Some(iters) + if let ͱ = one.ͱ() as usize + && ͱ % 2 == 0 => + { + let pow = util::powers[ͱ / 2]; + rocc(one / pow, iters) + rocc(one % pow, iters) + } + Some(iters) if iters > 1 && (one * 2024).ͱ() % 2 == 1 => { + // skip + let one = one * 2024 * 2024; + let pow = util::powers[one.ͱ() as usize / 2]; + rocc(one / pow, iters - 2) + rocc(one % pow, iters - 2) + } + Some(iters) => rocc(one * 2024, iters), + None => 1, + } + }; + unsafe { map.get_mut().ψ() }.insert((one, iters), answer); + answer } - - let mut dp = vec![0; max]; - // let mut dp = vec![u16::MAX; max]; - for i in memchr::memchr_iter(b'9', i) { - dp.fill(0); - tot += p1( - i as u16, - &mut |i| { - [ - i.wrapping_add(1), - i.wrapping_sub(1), - i.wrapping_add(size as u16 + 1), - i.wrapping_sub(size as u16 + 1), - ] - }, - &mut |i1, i2| match get(i2) { - Some(x) => get(i1).ψ().wrapping_sub(x) == 1, - None => false, - }, - &mut |i| get(i) == Some(b'0'), - &mut dp, - ); - } - tot + o.into_iter() + .take(n) + .map(|stone| rocc(stone, 75)) + .sum::<u64>() } fn main() { @@ -142,12 +118,12 @@ fn main() { // } // std::fs::write("src/inp.txt", s); // println!("{}", p2(i)); - println!("{}", run(i)); + println!("{}", unsafe { p2(i) }); // println!("{}", p1(i)); } #[bench] fn bench(b: &mut test::Bencher) { let i = boxd(include_str!("inp.txt")); - b.iter(|| run(i)); + b.iter(|| unsafe { p2(i) }); } diff --git a/src/util.rs b/src/util.rs index 41a6afa..40993d8 100644 --- a/src/util.rs +++ b/src/util.rs @@ -222,32 +222,59 @@ impl<T, E> UnsoundUtilities<T> for Result<T, E> { } } -pub struct LMap<K, V, F>(HashMap<K, V>, F) +pub struct LMap<K, V>(HashMap<K, V>, fn(K) -> V) where - F: Fn(K) -> Option<V>, K: Eq + Hash + Copy; -impl<K: Eq + Hash + Copy, V, F> LMap<K, V, F> -where - F: Fn(K) -> Option<V>, -{ - pub fn new(f: F) -> Self { +impl<K: Ord + Eq + Debug + Hash + Copy, V: Copy + Debug> LMap<K, V> { + pub fn new(f: fn(K) -> V) -> Self { Self { 0: HashMap::default(), 1: f, } } - pub fn get(&mut self, k: K) -> Option<&mut V> { - match self.0.entry(k) { - Entry::Occupied(x) => Some(x.into_mut()), - Entry::Vacant(e) => match self.1(k) { - Some(v) => Some(e.insert(v)), - None => None, - }, + pub fn with_cap(f: fn(K) -> V, cap: usize) -> Self { + Self { + 0: HashMap::with_capacity_and_hasher(cap, rustc_hash::FxBuildHasher::default()), + 1: f, } } + + pub fn get(&mut self, k: K) -> V { + if let Some(x) = self.0.get(&k) { + return *x; + } + // let mut ks = self.0.keys().collect::<Vec<_>>(); + // ks.sort(); + // println!("{ks:?}"); + let elm = self.1(k); + self.0.insert(k, elm); + elm + } } +macro_rules! memoize { + (|$pat:pat_param in $in:ty| -> $out:ty $body:block; $arg:expr) => {{ + static mut MEMOIZER: std::sync::OnceLock<crate::util::LMap<$in, $out>> = + std::sync::OnceLock::new(); + unsafe { + MEMOIZER.get_mut_or_init(|| crate::util::LMap::new(|$pat: $in| -> $out { $body })) + } + .get($arg) + }}; + (|$pat:pat_param in $in:ty| -> $out:ty $body:block; $arg:expr; with cap $cap:literal) => {{ + static mut MEMOIZER: std::sync::OnceLock<crate::util::LMap<$in, $out>> = + std::sync::OnceLock::new(); + unsafe { + MEMOIZER.get_mut_or_init(|| { + crate::util::LMap::with_cap(|$pat: $in| -> $out { $body }, $cap) + }) + } + .get($arg) + }}; +} +pub(crate) use memoize; + pub fn countg_with_check<N: Debug + PartialEq + Hash + Eq + Copy, I: Iterator<Item = N>>( start: N, graph: &mut impl Fn(N) -> I, @@ -638,6 +665,12 @@ impl DigiCount for u8 { } } +impl DigiCount for u128 { + fn ͱ(self) -> u32 { + self.checked_ilog10().ψ() + 1 + } +} + pub trait Ͷ: DigiCount { fn ͷ(self) -> impl Iterator<Item = u8>; fn Ͷ(self, i: u8) -> u8; @@ -656,6 +689,7 @@ macro_rules! digs { } }; } +digs!(u128); digs!(u64); digs!(u32); digs!(u16); |