| -rw-r--r-- | Cargo.lock | 52 | ||||
| -rw-r--r-- | Cargo.toml | 1 | ||||
| -rw-r--r-- | src/lib.rs | 256 |
3 files changed, 218 insertions, 91 deletions
@@ -38,10 +38,42 @@ dependencies = [ "aoc-runner", "aoc-runner-derive", "memchr", + "rayon", "rustc-hash", ] [[package]] +name = "crossbeam-deque" +version = "0.8.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "613f8cc01fe9cf1a3eb3d7f488fd2fa8388403e97039e2f73692932e291a770d" +dependencies = [ + "crossbeam-epoch", + "crossbeam-utils", +] + +[[package]] +name = "crossbeam-epoch" +version = "0.9.18" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5b82ac4a3c2ca9c3460964f020e1402edd5753411d7737aa39c3714ad1b5420e" +dependencies = [ + "crossbeam-utils", +] + +[[package]] +name = "crossbeam-utils" +version = "0.8.20" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "22ec99545bb0ed0ea7bb9b8e1e9122ea386ff8a48c0922e43f36d45ab09e0e80" + +[[package]] +name = "either" +version = "1.13.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "60b1af1c220855b6ceac025d3f6ecdd2b7c4894bfe9cd9bda4fbb4bc7c0d4cf0" + +[[package]] name = "itoa" version = "1.0.14" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -90,6 +122,26 @@ dependencies = [ ] [[package]] +name = "rayon" +version = "1.10.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b418a60154510ca1a002a752ca9714984e21e4241e804d32555251faf8b78ffa" +dependencies = [ + "either", + "rayon-core", +] + +[[package]] +name = "rayon-core" +version = "1.12.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1465873a3dfdaa8ae7cb14b4383657caab0b3e8a0aa9ae8e04b044854c8dfce2" +dependencies = [ + "crossbeam-deque", + "crossbeam-utils", +] + +[[package]] name = "rustc-hash" version = "2.1.0" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -7,4 +7,5 @@ edition = "2021" aoc-runner = "0.1.0" aoc-runner-derive = "0.1.0" memchr = "2.7.4" +rayon = "1.10.0" rustc-hash = "2.1.0" @@ -25,113 +25,187 @@ portable_simd )] mod util; -pub mod day5 { +pub mod day6 { use crate::util::prelude::*; - struct Setz { - bits: [u128; 100], - } - impl Setz { - fn new() -> Self { - Self { bits: [0; 100] } + + const SIZE: usize = 130; + + #[derive(Clone, Copy)] + struct bitset17030([u64; 267]); + impl bitset17030 { + const fn new() -> Self { + Self([0; 267]) + } + #[inline(always)] + fn set(&mut self, index: usize) { + unsafe { *self.0.get_unchecked_mut(index >> 6) |= 1u64.wrapping_shl(index as u32) }; } - fn insert(&mut self, a: u8, b: u8) { - unsafe { *self.bits.get_unchecked_mut(a as usize) |= 1 << b }; + #[inline(always)] + fn get(&self, index: usize) -> bool { + unsafe { *self.0.get_unchecked(index >> 6) & 1u64.wrapping_shl(index as u32) != 0 } } - fn test(&self, a: u8, b: u8) -> bool { - unsafe { (*self.bits.get_unchecked(a as usize) & 1 << b) != 0 } + #[inline(always)] + fn popcnt(self) -> u32 { + self.0.into_iter().map(u64::count_ones).sum::<u32>() } } - #[no_mangle] - pub fn part1(i: &str) -> impl Display { - 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; - 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, - }) + // type bits = bitvec::BitArr!(for 16960, in u64); + // #[derive(Clone, Copy)] + // struct bitset17030(bits); + // impl bitset17030 { + // fn new() -> Self { + // Self(bits::default()) + // } + // #[inline(always)] + // #[no_mangle] + // fn set(&mut self, index: usize) { + // unsafe { self.0.set_unchecked(index, true) }; + // } + // #[inline(always)] + // #[no_mangle] + // fn get(&self, index: usize) -> bool { + // unsafe { *self.0.get_unchecked(index) } + // } + // #[inline(always)] + // fn popcnt(self) -> u32 { + // self.0.count_ones() as _ + // } + // } + + fn follow(i: &[u8]) -> (i64, bitset17030) { + let mut marked = bitset17030::new(); + let mut position = memchr::memchr(b'^', i).ψ() as i64; + let guard = position; + let mut pointing = 0u8; + + 'outer: loop { + match pointing { + 0 => loop { + marked.set(position as usize); + let check = position - SIZE as i64 - 1; + if check < 0 { + break 'outer; + } + match C! { i[check as usize] } { + b'\n' => break 'outer, + b'#' => break, + _ => position = check, + }; + }, + 1 => loop { + marked.set(position as usize); + let check = position + 1; + match C! { i[check as usize] } { + b'\n' => break 'outer, + b'#' => break, + _ => position = check, + }; + }, + 2 => loop { + marked.set(position as usize); + let check = position + SIZE as i64 + 1; + match C! { i[check as usize] } { + b'\n' => break 'outer, + b'#' => break, + _ => position = check, + }; + }, + 3 => loop { + marked.set(position as usize); + let check = position - 1; + if check < 0 { + break 'outer; + } + match C! { i[check as usize] } { + b'\n' => break 'outer, + b'#' => break, + _ => position = check, + }; + }, + _ => shucks!(), } - sum += C! { v[(v.len() - 1) / 2] } as u32; + pointing += 1; + pointing %= 4; } - leek!(v); - sum + (guard, marked) + } + + #[no_mangle] + pub fn part1(i: &str) -> impl Display { + follow(i.as_bytes()).1.popcnt() } #[no_mangle] pub fn part2(i: &str) -> impl Display { 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; - 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, - }) + fn run(i: &[u8], guard: i64, obstacle: i64) -> bool { + let mut marked = [bitset17030::new(); 4]; + let mut position = guard; + let mut pointing = 0u8; + + macro_rules! check { + () => { + if marked[pointing as usize].get(position as usize) { + return true; + } else { + marked[pointing as usize].set(position as usize) + } + }; } - if faults == 0 { - continue; + macro_rules! entry { + (sub $check:expr) => { + loop { + check!(); + let check = $check; + if check < 0 { + return false; + } + if check == obstacle { + break; + } + match C! { i[check as usize] } { + b'\n' => return false, + b'#' => break, + _ => position = check, + }; + } + }; + (add $check:expr) => { + loop { + check!(); + let check = $check; + if check == obstacle { + break; + } + match i.get(check as usize) { + None | Some(b'\n') => return false, + Some(b'#') => break, + _ => position = check, + }; + } + }; } - 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 + + loop { + match pointing { + 0 => entry!(sub position - SIZE as i64 - 1), + 1 => entry!(add position + 1), + 2 => entry!(add position + SIZE as i64 + 1), + 3 => entry!(sub position - 1), + _ => shucks!(), } - }); - sum += mid as u32; + pointing += 1; + pointing %= 4; + } } - leek!(v); - sum + let (guard, marked) = follow(&i); + use rayon::prelude::*; + (0..SIZE * (SIZE + 1)) + .filter(|&i| marked.get(i)) + .filter(|&j| C! { i[j] } == b'.') + .par_bridge() + .filter(|&j| run(&i, guard, j as i64)) + .count() } } |