heh
| -rw-r--r-- | src/main.rs | 40 | ||||
| -rw-r--r-- | src/util.rs | 31 |
2 files changed, 46 insertions, 25 deletions
diff --git a/src/main.rs b/src/main.rs index ca96c2e..0794e36 100644 --- a/src/main.rs +++ b/src/main.rs @@ -56,33 +56,27 @@ use std::{ }; pub use util::prelude::*; -#[allow(warnings)] -type u32x3 = Simd<u32, 3>; +fn status(x: u32, y: u32) -> bool { + (x * x + 3 * x + 2 * x * y + y + y * y + 1350).count_ones() % 2 == 0 +} #[unsafe(no_mangle)] #[implicit_fn::implicit_fn] pub unsafe fn p1(x: &'static str) -> impl Display { - let x = x.行().collect::<Vec<_>>(); - let mut ptr = 0i32; - let mut regis = - HashMap::<&[u8], i32>::from_iter([(&b"a"[..], 0), (b"b", 0), (b"c", 1), (b"d", 0)]); - while let Some(i) = x.get(ptr as usize) { - let i = i.μₙ(b' ').collect::<Vec<_>>(); - let p = |j: usize| i[j].str().parse::<i32>().unwrap_or_else(|_| regis[i[j]]); - match i[0] { - b"cpy" => *regis.get_mut(i[2]).unwrap() = p(1), - b"inc" => *regis.get_mut(i[1]).unwrap() += 1, - b"dec" => *regis.get_mut(i[1]).unwrap() -= 1, - b"jnz" if p(1) != 0 => { - ptr += p(2); - continue; - } - _ => (), - } - ptr += 1; - } - - regis[&b"a"[..]] + // 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() } fn main() { diff --git a/src/util.rs b/src/util.rs index b966bba..7bcf4a9 100644 --- a/src/util.rs +++ b/src/util.rs @@ -4,6 +4,7 @@ use Default::default; use regex::Regex; use rustc_hash::FxHashMap as HashMap; use rustc_hash::FxHashSet as HashSet; +use std::collections::VecDeque; use std::iter::successors; use std::sync::LazyLock; use std::{ @@ -208,6 +209,7 @@ pub enum Dir { } impl Dir { + pub const ALL: [Self; 4] = [Self::N, Self::E, Self::S, Self::W]; pub fn urdl(x: u8) -> Self { match x { b'U' => Self::N, @@ -452,9 +454,23 @@ pub fn show<N: Debug + Eq + Hash + Copy + Ord, I: Iterator<Item = (N, u16)>, D: dang!(); } +pub fn reachable<D: Hash + Copy, N: Debug + Eq + Hash + Copy + Ord, I: Iterator<Item = (N, D)>>( + start: (N, D), + graph: impl Fn((N, D)) -> I, +) -> HashSet<N> { + let mut map = HashSet::default(); + let mut stack = VecDeque::from_iter([start]); + while let Some((x, d)) = stack.pop_front() { + if map.insert(x) { + stack.extend(graph((x, d))); + } + } + map +} + pub fn dijkstra_h<N: Debug + Eq + Hash + Copy + Ord, I: Iterator<Item = (N, u16)>>( - graph: impl Fn(N) -> I, start: N, + graph: impl Fn(N) -> I, end: impl Fn(N) -> bool, h: impl Fn(N) -> u16, ) -> u16 { @@ -479,8 +495,8 @@ pub fn dijkstra_h<N: Debug + Eq + Hash + Copy + Ord, I: Iterator<Item = (N, u16) } pub fn dijkstra<N: Debug + Eq + Hash + Copy + Ord, I: Iterator<Item = (N, u16)>>( - graph: impl Fn(N) -> I, start: N, + graph: impl Fn(N) -> I, end: impl Fn(N) -> bool, ) -> Option<u16> { let mut q = BinaryHeap::new(); @@ -515,6 +531,17 @@ impl std::ops::Add<(i64, i64)> for Dir { } } } +impl std::ops::Add<(u32, u32)> for Dir { + type Output = Option<(u32, u32)>; + fn add(self, (x, y): (u32, u32)) -> Self::Output { + Some(match self { + Dir::N => (x, y.checked_sub(1)?), + Dir::E => (x + 1, y), + Dir::S => (x, y + 1), + Dir::W => (x.checked_sub(1)?, y), + }) + } +} impl Dir { pub fn lim_add( |