heh
| -rw-r--r-- | Cargo.toml | 3 | ||||
| -rw-r--r-- | src/inp.txt | 24 | ||||
| -rw-r--r-- | src/main.rs | 54 | ||||
| -rw-r--r-- | src/util.rs | 13 |
4 files changed, 46 insertions, 48 deletions
@@ -9,13 +9,14 @@ edition = "2024" atools = "0.1.5" car = "0.1.1" collar = "1.0.1" +fancy-regex = "0.15.0" implicit-fn = "0.1.0" # hinted = "0.0.1" itertools = "0.12.0" lower = "0.2.0" lower-macros = "0.2.3" mattr = "1.0.0" -# md-5 = "0.10.6" +md-5 = "0.10.6" memchr = "2.6.4" regex = { version = "1.11.1", default-features = false, features = [ "unstable", diff --git a/src/inp.txt b/src/inp.txt index 7b0f5e2..b5fc5ff 100644 --- a/src/inp.txt +++ b/src/inp.txt @@ -1,23 +1 @@ -cpy 1 a -cpy 1 b -cpy 26 d -jnz c 2 -jnz 1 5 -cpy 7 c -inc d -dec c -jnz c -2 -cpy a c -inc a -dec b -jnz b -2 -cpy c b -dec d -jnz d -6 -cpy 19 c -cpy 14 d -inc a -dec d -jnz d -2 -dec c -jnz c -5 +ngcjuoqr
\ No newline at end of file diff --git a/src/main.rs b/src/main.rs index 0794e36..56782c5 100644 --- a/src/main.rs +++ b/src/main.rs @@ -47,38 +47,50 @@ pub mod util; use atools::prelude::*; use collar::CollectArray; use lower::apply; +use md5::{Digest, Md5}; use memchr::memmem; use regex::bytes::Regex; +use rustc_hash::FxBuildHasher; use std::{ cmp::{Reverse, minmax}, mem::take, simd::prelude::*, }; -pub use util::prelude::*; - -fn status(x: u32, y: u32) -> bool { - (x * x + 3 * x + 2 * x * y + y + y * y + 1350).count_ones() % 2 == 0 -} +pub use util::prelude::*; #[unsafe(no_mangle)] #[implicit_fn::implicit_fn] -pub unsafe fn p1(x: &'static str) -> impl Display { - // dijkstra - util::reachable( - ((1u32, 1u32), 0), - |((x, y), s)| { - Dir::ALL - .into_iter() - .flat_map(move |d| d + (x, y)) - .filter(|&(x, y)| status(x, y)) - .map(move |x| (x, s + 1)) - .filter(_.1 <= 50) - }, - // |x| (x == (31, 39)), - ) - .len() -} +pub unsafe fn p1(i: &'static str) -> impl Display { + // let hash = |x: u32| util::md5s(format!("{i}{x}").as_bytes()); + let mut memo = + HashMap::<u32, String>::with_capacity_and_hasher(92859, FxBuildHasher::default()); + macro_rules! hash { + ($x:expr) => {{ + let x = $x; + memo.entry(x) + .or_insert_with(|| { + successors(format!("{i}{x}").into(), |x| Some(util::md5s(x.as_bytes()))) + .nth(2017) + .unwrap() + }) + .as_bytes() + }}; + } + // dbg!(hash(0)); + (0u32..) + .filter(|&x| { + let Some(&c) = hash!(x) + .array_windows::<3>() + .find(|x| x.iter().all(|&y| y == x[0])) + else { + return false; + }; + (x..=x + 1000).any(|x| memmem::find(hash!(x), &[c[0]; 5]).is_some()) + }) + .nth(74) + .unwrap() +} fn main() { unsafe { println!("{}", p1(include_str!("inp.txt"))) }; } diff --git a/src/util.rs b/src/util.rs index 7bcf4a9..6bc8577 100644 --- a/src/util.rs +++ b/src/util.rs @@ -1870,12 +1870,19 @@ impl<T: Copy, I: Iterator<Item = T>> MapWith<T> for I { } } -#[cfg(never)] -fn md5(x: &[u8]) -> [u8; 16] { +pub fn md5(x: &[u8]) -> [u8; 16] { use md5::Digest; let mut hasher = md5::Md5::new(); hasher.update(x); - *hasher.finalize().as_array::<16>().unwrap() + hasher.finalize().into() +} + +pub fn md5s(x: &[u8]) -> String { + let mut s = String::with_capacity(32); + for element in md5(x) { + write!(s, "{element:02x}").unwrap(); + } + s } pub trait PartitionByKey<T> { fn partition_by_key<V, U: Extend<V> + Default>( |