| -rw-r--r-- | Cargo.lock | 7 | ||||
| -rw-r--r-- | Cargo.toml | 1 | ||||
| -rw-r--r-- | src/lib.rs | 241 |
3 files changed, 91 insertions, 158 deletions
@@ -38,7 +38,6 @@ dependencies = [ "aoc-runner", "aoc-runner-derive", "memchr", - "radsort", "rustc-hash", ] @@ -91,12 +90,6 @@ dependencies = [ ] [[package]] -name = "radsort" -version = "0.1.1" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "019b4b213425016d7d84a153c4c73afb0946fbb4840e4eece7ba8848b9d6da22" - -[[package]] name = "rustc-hash" version = "2.1.0" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -7,5 +7,4 @@ edition = "2021" aoc-runner = "0.1.0" aoc-runner-derive = "0.1.0" memchr = "2.7.4" -radsort = "0.1.1" rustc-hash = "2.1.0" @@ -25,172 +25,113 @@ portable_simd )] mod util; -pub mod day4 { +pub mod day5 { use crate::util::prelude::*; - const SIZE: usize = 140; - - #[derive(Copy, Clone, Default, Debug, PartialEq, Eq)] - struct bitset140([u64; 3]); - impl bitset140 { - #[inline] - fn count_ones(self) -> u32 { - self.0.iter().copied().map(u64::count_ones).sum() - } + struct Setz { + bits: [u128; 100], } - - impl std::ops::Shr<u32> for bitset140 { - type Output = Self; - - #[inline] - fn shr(self, rhs: u32) -> Self::Output { - let bitset140([a, b, c]) = self; - Self([ - a >> rhs, - b >> rhs | a << (u64::BITS - rhs), - c >> rhs | b << (u64::BITS - rhs), - ]) + impl Setz { + fn new() -> Self { + Self { bits: [0; 100] } } - } - impl std::ops::Shl<u32> for bitset140 { - type Output = Self; - - #[inline] - fn shl(self, rhs: u32) -> Self::Output { - let bitset140([a, b, c]) = self; - Self([ - a << rhs | b >> (u64::BITS - rhs), - b << rhs | c >> (u64::BITS - rhs), - c << rhs, - ]) + fn insert(&mut self, a: u8, b: u8) { + unsafe { *self.bits.get_unchecked_mut(a as usize) |= 1 << b }; } - } - - impl std::ops::BitAnd<bitset140> for bitset140 { - type Output = Self; - - #[inline] - fn bitand(self, bitset140([a, b, c]): bitset140) -> Self::Output { - let [d, e, f] = self.0; - bitset140([a & d, b & e, c & f]) + fn test(&self, a: u8, b: u8) -> bool { + unsafe { (*self.bits.get_unchecked(a as usize) & 1 << b) != 0 } } } - use std::simd::prelude::*; - + #[no_mangle] pub fn part1(i: &str) -> impl Display { - fn load(i: &[u8; SIZE + 1]) -> [bitset140; 4] { - let loaded = [ - u8x64::load_or_default(&i[128..]), - u8x64::from_slice(&i[64..128]), - u8x64::from_slice(&i[..64]), - ]; - - [ - bitset140(loaded.map(|x| x.simd_eq(Simd::splat(b'X')).to_bitmask())), - bitset140(loaded.map(|x| x.simd_eq(Simd::splat(b'M')).to_bitmask())), - bitset140(loaded.map(|x| x.simd_eq(Simd::splat(b'A')).to_bitmask())), - bitset140(loaded.map(|x| x.simd_eq(Simd::splat(b'S')).to_bitmask())), - ] + let i = i.as_bytes(); + let c = unsafe { C! { &i[..1176 * 6]}.as_chunks_unchecked::<6>() }; + let mut bitsets = Setz::new(); + for i in 0..1176 { + let [a, b, _, c, d, _] = C! { c[i] }; + bitsets.insert((a - b'0') * 10 + (b - b'0'), (c - b'0') * 10 + (d - b'0')); } - unsafe { - let grid = i.as_bytes().as_chunks_unchecked::<{ SIZE + 1 }>(); - // let masked: [masks; SIZE] = std::array::from_fn(|i| load(grid.get_unchecked(i))); - let mut sum = 0; - let mut prev_x = [bitset140::default(); 4]; - let mut prev_m = [bitset140::default(); 4]; - let mut prev_a = [bitset140::default(); 4]; - let mut prev_s = [bitset140::default(); 4]; - - for y in 0..=2 { - let [x, m, a, s] = load(grid.get_unchecked(y)); - sum += (x & m << 1 & a << 2 & s << 3).count_ones(); - sum += (x & m >> 1 & a >> 2 & s >> 3).count_ones(); - prev_x[y + 1] = x; - prev_m[y + 1] = m; - prev_a[y + 1] = a; - prev_s[y + 1] = s; - // prev[y + 1] = masks; - } - for y in 3..SIZE { - let [x, m, a, s] = load(grid.get_unchecked(y)); - let [_, p1, p2, p3] = prev_x; - prev_x = [p1, p2, p3, x]; - let [_, p1, p2, p3] = prev_m; - prev_m = [p1, p2, p3, m]; - let [_, p1, p2, p3] = prev_a; - prev_a = [p1, p2, p3, a]; - let [_, p1, p2, p3] = prev_s; - prev_s = [p1, p2, p3, s]; - - // println!("{a:?}"); - // // ↘→←↓↙→←↑↗↖↗↖↗→↖↗↑↖18 - // // overlap right - sum += (x & m << 1 & a << 2 & s << 3).count_ones(); - // // overlap left - sum += (x & m >> 1 & a >> 2 & s >> 3).count_ones(); - - // // idea is to overlap and then count - // // idea comes from gioschii - // if y >= 3 - // - { - let x = x; - let m = prev_m[3 - 1]; - let a = prev_a[3 - 2]; - let s = prev_s[3 - 3]; - - // down diagonal - sum += (x & m << 1 & a << 2 & s << 3).count_ones(); - sum += (x & m >> 1 & a >> 2 & s >> 3).count_ones(); - - // vertical - sum += (x & m & a & s).count_ones(); - } - // - { - let s = s; - let a = prev_a[3 - 1]; - let m = prev_m[3 - 2]; - let x = prev_x[3 - 3]; - - // up diagonals - sum += (x & m << 1 & a << 2 & s << 3).count_ones(); - sum += (x & m >> 1 & a >> 2 & s >> 3).count_ones(); - - sum += (x & m & a & s).count_ones(); - } - // println!( - // "{y}: {:064b}{:064b}{:064b}", - // // sum - sum_, - // x.0[0], - // x.0[1], - // x.0[2] - // ); + let mut sum = 0; + let mut v = Vec::with_capacity(25); + 'out: for mut pages in C!(&i[1176 * 6 + 1..]).行() { + v.clear(); + let [a, b, rest @ ..] = pages else { + unsafe { std::hint::unreachable_unchecked() } + }; + pages = rest; + v.push((a - b'0') * 10 + (b - b'0')); + let mut i = 0; + loop { + mat!(pages { + [b',', a, b, rest @ ..] => { + v.push((a - b'0') * 10 + (b - b'0')); + if let &[a, b] = C!{ &v[i..] } { + // valid ones always have a rule + if !bitsets.test(a, b) { + continue 'out; + } + i += 1; + } + pages = rest; + }, + [] => break, + }) } - sum + sum += C! { v[(v.len() - 1) / 2] } as u32; } + leek!(v); + sum } + #[no_mangle] pub fn part2(i: &str) -> impl Display { - let g = i.as_bytes(); - assert_eq!(g.len(), 141 * 140); + let i = i.as_bytes(); + let c = unsafe { C! { &i[..1176 * 6]}.as_chunks_unchecked::<6>() }; + let mut bitsets = Setz::new(); + for i in 0..1176 { + let [a, b, _, c, d, _] = C! { c[i]}; + bitsets.insert((a - b'0') * 10 + (b - b'0'), (c - b'0') * 10 + (d - b'0')); + } let mut sum = 0; - // chunks of 64 - for i in 0..304 { - // tl - let a = u8x64::from_slice(&g[64 * i..]); - // trd - let b = u8x64::from_slice(&g[64 * i + 2..]); - // mid - let current = u8x64::from_slice(&g[141 + 64 * i + 1..]); - // bl - let d = u8x64::from_slice(&g[141 * 2 + 64 * i..]); - // br - let c = u8x64::from_slice(&g[141 * 2 + 64 * i + 2..]); - let wz = ((a ^ c) + (b ^ d)).simd_eq(u8x64::splat(60)); - let a = current.simd_eq(u8x64::splat(b'A')); - sum += (wz & a).to_bitmask().count_ones(); + let mut v = Vec::with_capacity(25); + for mut pages in C!(&i[1176 * 6 + 1..]).行() { + v.clear(); + let [a, b, rest @ ..] = pages else { + unsafe { std::hint::unreachable_unchecked() } + }; + pages = rest; + v.push((a - b'0') * 10 + (b - b'0')); + let mut i = 0; + let mut faults = 0; + loop { + mat!(pages { + [b',', a, b, rest @ ..] => { + v.push((a - b'0') * 10 + (b - b'0')); + if let &[a, b] = C! { &v[i..] } { + if !bitsets.test(a, b) { + faults += 1; + } + i += 1; + } + pages = rest; + }, + [] => break, + }) + } + if faults == 0 { + continue; + } + let mid = (v.len() - 1) / 2; + let (_, &mut mid, _) = v.select_nth_unstable_by(mid, |&a, &b| { + if bitsets.test(a, b) { + std::cmp::Ordering::Greater + } else { + std::cmp::Ordering::Less + } + }); + sum += mid as u32; } + leek!(v); sum } } |