heh
unionfinding
| -rw-r--r-- | src/main.rs | 97 | ||||
| -rw-r--r-- | src/util.rs | 10 |
2 files changed, 94 insertions, 13 deletions
diff --git a/src/main.rs b/src/main.rs index 74ca80c..f90282c 100644 --- a/src/main.rs +++ b/src/main.rs @@ -13,6 +13,7 @@ generic_const_exprs, iter_array_chunks, if_let_guard, + const_mut_refs, get_many_mut, maybe_uninit_uninit_array, once_cell_get_mut, @@ -33,17 +34,12 @@ )] extern crate test; pub mod util; -use atools::CollectArray; -use std::cmp::Reverse; pub use util::prelude::*; -const WIDTH: usize = 70; +const WIDTH: usize = 71; pub unsafe fn run(x: &str) -> impl Display { let mut grid = [[0; WIDTH + 1]; WIDTH + 1]; - let mut add = x.行().map(|x| { - let (x, y) = x.μ(',').mb(|x| x.λ::<u8>()); - (x, y) - }); + let mut add = x.行().map(|x| x.μ(',').mb(|x| x.λ::<u8>())); loop { let x = add.next().unwrap(); grid[x.1.nat()][x.0.nat()] = 1; @@ -65,8 +61,93 @@ pub unsafe fn run(x: &str) -> impl Display { // 0 } + +pub struct UnionFind { + pub p: [u16; 5184], + pub s: [u16; 5184], +} + +impl UnionFind { + pub const fn new() -> Self { + Self { + s: [1; 5184], + p: car::map!(atools::range(), |x| x as u16), + } + } + + pub const fn find(&mut self, key: u16) -> u16 { + if unsafe { *self.p.as_ptr().add(key as usize) } == key { + return key; + } + let parent = self.find(unsafe { *self.p.as_ptr().add(key as usize) }); + unsafe { *self.p.as_mut_ptr().add(key as usize) = parent }; + parent + } + + pub const fn union(&mut self, a: u16, b: u16) -> bool { + let α = self.find(a); + let β = self.find(b); + if α == β { + return false; + } + let a = unsafe { *self.s.as_ptr().add(α as usize) }; + let b = unsafe { *self.s.as_ptr().add(β as usize) }; + if a >= b { + unsafe { *self.s.as_mut_ptr().add(α as usize) += b }; + unsafe { *self.p.as_mut_ptr().add(β as usize) = α }; + } else { + unsafe { *self.s.as_mut_ptr().add(β as usize) += a }; + unsafe { *self.p.as_mut_ptr().add(α as usize) = β }; + } + true + } +} + +pub fn part2(x: &str) -> impl Display { + let add = x.行().map(|x| x.μ(',').mb(|x| x.λ::<u8>())); + macro_rules! dex { + ($x:expr, $y:expr) => { + unsafe { + (($y as u16) + .unchecked_mul((WIDTH as u16 + 1)) + .unchecked_add($x as u16)) + } + }; + } + const W: u8 = WIDTH as u8; + const UF: UnionFind = { + let mut f = UnionFind::new(); + let mut i = 0; + while i < W - 1 { + f.union(dex!(i + 1, 0), dex!(i + 2, 0)); + f.union(dex!(i, W), dex!(i + 1, W)); + f.union(dex!(0, i + 1), dex!(0, i + 2)); + f.union(dex!(W, i), dex!(W, i + 1)); + i += 1; + } + f + }; + let mut uf = UF; + for (x, y) in add { + let i = dex!(x, y); + uf.union(i, dex!(x + 1, y)); + uf.union(i, dex!(x, y + 1)); + uf.union(i, dex!(x + 1, y + 1)); + + if uf.find(dex!(0, 1)) == uf.find(dex!(1, 0)) { + return format!("{},{}", x, y); + } + } + dang!(); +} + fn main() { let s = include_str!("inp.txt"); - println!("{}", unsafe { run(s) }); + println!("{}", unsafe { part2(s) }); // dbg!(exec(&program, regi)); } +#[bench] +fn benc(b: &mut test::Bencher) { + let i = boxd(include_str!("inp.txt")); + b.iter(|| part2(i)); +} diff --git a/src/util.rs b/src/util.rs index b3efe19..4fbb7a9 100644 --- a/src/util.rs +++ b/src/util.rs @@ -549,14 +549,14 @@ impl std::ops::Add<(i16, i16)> for Dir { } impl std::ops::Add<(u8, u8)> for Dir { - type Output = Option<(u8, u8)>; + type Output = (u8, u8); fn add(self, (x, y): (u8, u8)) -> Self::Output { match self { - Dir::N => Some((x, y.checked_sub(1)?)), - Dir::E => Some((x + 1, y)), - Dir::S => Some((x, y + 1)), - Dir::W => Some((x.checked_sub(1)?, y)), + Dir::N => (x, y.wrapping_sub(1)), + Dir::E => (x.wrapping_add(1), y), + Dir::S => (x, y.wrapping_add(1)), + Dir::W => (x.wrapping_sub(1), y), } } } |