heh
| -rw-r--r-- | src/main.rs | 76 |
1 files changed, 65 insertions, 11 deletions
diff --git a/src/main.rs b/src/main.rs index 346f386..ccb655b 100644 --- a/src/main.rs +++ b/src/main.rs @@ -37,11 +37,10 @@ pub use util::prelude::*; #[no_mangle] pub fn run(i: &str) -> impl Display { let i = i.as_bytes(); - // let set = [0; i.len()] let size = memchr::memchr(b'\n', i).ψ(); let max = size * (size + 1); unsafe { core::hint::assert_unchecked(i.len() == max) }; - let get = |j: usize| (j < max).then(|| i[j]); + let get = |j: u16| (j < max as u16).then(|| i[j as usize]); // fimg::Image::<Vec<u8>, 1>::build(SIZE as _, SIZE as _) // .buf( @@ -53,28 +52,83 @@ pub fn run(i: &str) -> impl Display { // .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() + } + } + + 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() + } + } + + let mut dp = vec![0; max]; + // let mut dp = vec![u16::MAX; max]; for i in memchr::memchr_iter(b'9', i) { - // if get(i) == Some(b'9') { - util::countg_with_check( - i, + dp.fill(0); + tot += p1( + i as u16, &mut |i| { [ i.wrapping_add(1), i.wrapping_sub(1), - i.wrapping_add(size + 1), - i.wrapping_sub(size + 1), + i.wrapping_add(size as u16 + 1), + i.wrapping_sub(size as u16 + 1), ] - .into_iter() }, &mut |i1, i2| match get(i2) { Some(x) => get(i1).ψ().wrapping_sub(x) == 1, None => false, }, - &mut tot, &mut |i| get(i) == Some(b'0'), - // &mut HashSet::default(), + &mut dp, ); - // } } tot } |