| -rw-r--r-- | Cargo.lock | 12 | ||||
| -rw-r--r-- | Cargo.toml | 1 | ||||
| -rw-r--r-- | src/lib.rs | 214 | ||||
| -rw-r--r-- | src/util.rs | 116 |
4 files changed, 144 insertions, 199 deletions
@@ -32,11 +32,23 @@ dependencies = [ ] [[package]] +name = "car" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d0122f0f55893530a647617887ebb7ff0888c62966817d81de4454dcee95e1c5" +dependencies = [ + "proc-macro2 1.0.92", + "quote 1.0.37", + "syn 2.0.90", +] + +[[package]] name = "codspeed-aoc" version = "0.1.0" dependencies = [ "aoc-runner", "aoc-runner-derive", + "car", "memchr", "rayon", "rustc-hash", @@ -6,6 +6,7 @@ edition = "2021" [dependencies] aoc-runner = "0.1.0" aoc-runner-derive = "0.1.0" +car = "0.1.1" memchr = "2.7.4" rayon = "1.10.0" rustc-hash = "2.1.0" @@ -22,190 +22,62 @@ array_chunks, slice_split_once, core_intrinsics, - portable_simd + portable_simd, + hint_assert_unchecked )] mod util; -pub mod day6 { - use crate::util::prelude::*; +pub mod day7 { + use super::util::prelude::*; - 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) }; - } - #[inline(always)] - fn get(&self, index: usize) -> bool { - unsafe { *self.0.get_unchecked(index >> 6) & 1u64.wrapping_shl(index as u32) != 0 } - } - #[inline(always)] - fn popcnt(self) -> u32 { - self.0.into_iter().map(u64::count_ones).sum::<u32>() + #[inline] + fn do_(i: &str, search: fn(&[u64], u64) -> bool) -> u64 { + let mut v = [0u64; 12]; + let mut i = i.as_bytes(); + let mut sum = 0; + while !i.is_empty() { + let should = reading::until(&mut i, b':'); + i.skip(1); + let i = i.take_line().ψ(); + let read = reading::κ(i, &mut v); + sum += should * search(C! { &v[..read] }, should) as u64; } + sum } - // 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!(), + pub fn part1(i: &str) -> impl Display { + // go backwards for extreme pruning ability + fn search(nums: &[u64], tv: u64) -> bool { + match nums { + &[tail] => tv == tail, + [head @ .., tail] => { + let tail = *tail; + unsafe { core::hint::assert_unchecked(tail != 0) }; + (tv % tail == 0 && search(head, tv / tail)) + || (tv > tail && search(head, tv - tail)) + } + [] => shucks!(), } - pointing += 1; - pointing %= 4; } - (guard, marked) - } - - #[no_mangle] - pub fn part1(i: &str) -> impl Display { - follow(i.as_bytes()).1.popcnt() + do_(i, search) } - #[no_mangle] pub fn part2(i: &str) -> impl Display { - let i = i.as_bytes(); - 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) - } - }; - } - 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, - }; - } - }; - } - - 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!(), + fn search(nums: &[u64], tv: u64) -> bool { + match nums { + &[tail] => tv == tail, + [head @ .., tail] => { + let &d = unsafe { + crate::util::powers + .get_unchecked((((tail + 0xbf6) & (tail + 0x79c)) >> 10) as usize + 1) + }; + let tail = *tail; + (tv % tail == 0 && search(head, tv / tail)) + || ((tv - tail) % d == 0 && search(head, tv / d)) + || (tv > tail && search(head, tv - tail)) } - pointing += 1; - pointing %= 4; + [] => shucks!(), } } - 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() + do_(i, |n, should| search(n, should)) } } diff --git a/src/util.rs b/src/util.rs index 756b6cb..b8a3d87 100644 --- a/src/util.rs +++ b/src/util.rs @@ -1,4 +1,4 @@ -#![allow(non_snake_case, unused_macros, warnings)] +#![allow(non_snake_case, unused_macros)] use rustc_hash::FxHashMap as HashMap; use rustc_hash::FxHashSet as HashSet; @@ -16,10 +16,10 @@ pub mod prelude { #[allow(unused_imports)] pub(crate) use super::{bits, dang, leek, mat, shucks, C}; pub use super::{ - even, gcd, gt, l, lcm, lt, pa, r, rand, reading, reading::Ext, sort, Dir, FilterBy, - FilterBy3, GreekTools, IntoCombinations, IntoLines, IterͶ, NumTupleIterTools, ParseIter, - Printable, Skip, TakeLine, TupleIterTools2, TupleIterTools2R, TupleIterTools3, TupleUtils, - UnifiedTupleUtils, UnsoundUtilities, Widen, Ͷ, Α, Κ, Λ, Μ, + even, gcd, gt, l, lcm, lt, nail, pa, r, rand, reading, reading::Ext, sort, DigiCount, Dir, + FilterBy, FilterBy3, GreekTools, IntoCombinations, IntoLines, IterͶ, NumTupleIterTools, + ParseIter, Printable, Skip, TakeLine, TupleIterTools2, TupleIterTools2R, TupleIterTools3, + TupleUtils, UnifiedTupleUtils, UnsoundUtilities, Widen, Ͷ, Α, Κ, Λ, Μ, }; pub use rustc_hash::FxHashMap as HashMap; pub use rustc_hash::FxHashSet as HashSet; @@ -425,6 +425,17 @@ impl std::ops::Add<(u8, u8)> for Dir { } } +impl Dir { + pub fn turn_90(&mut self) { + match self { + Dir::N => *self = Dir::E, + Dir::E => *self = Dir::S, + Dir::S => *self = Dir::W, + Dir::W => *self = Dir::N, + } + } +} + pub fn pa<T: std::fmt::Debug>(a: &[T]) { for e in a { print!("{e:?}"); @@ -539,30 +550,72 @@ impl<T> Α<T> for Option<T> { } } -pub trait Ͷ { +pub trait DigiCount { + fn ͱ(self) -> u32; +} + +pub const powers: [u64; 20] = car::from_fn!(|x| 10u64.pow(x as u32)); +// https://stackoverflow.com/a/9721570 +impl DigiCount for u64 { + fn ͱ(self) -> u32 { + static powers: [u64; 20] = car::from_fn!(|x| 10u64.pow(x as u32)); + static mdigs: [u32; 65] = car::from_fn!(|x| 2u128.pow(x as u32).ilog10() + 1); + let bit = std::mem::size_of::<Self>() * 8 - self.leading_zeros() as usize; + let mut digs = mdigs[bit]; + if self < C! { powers[digs as usize - 1] } { + digs -= 1; + } + digs + } +} + +impl DigiCount for u32 { + fn ͱ(self) -> Self { + static powers: [u32; 10] = car::from_fn!(|x| 10u32.pow(x as u32)); + static mdigs: [u32; 33] = car::from_fn!(|x| 2u128.pow(x as u32).ilog10() + 1); + let bit = std::mem::size_of::<Self>() * 8 - self.leading_zeros() as usize; + let mut digs = mdigs[bit]; + if self < C! { powers[digs as usize - 1] } { + digs -= 1; + } + digs + } +} + +impl DigiCount for u16 { + fn ͱ(self) -> u32 { + self.checked_ilog10().ψ() + 1 + } +} + +impl DigiCount for u8 { + fn ͱ(self) -> u32 { + self.checked_ilog10().ψ() + 1 + } +} + +pub trait Ͷ: DigiCount { fn ͷ(self) -> impl Iterator<Item = u8>; + fn Ͷ(self, i: u8) -> u8; } macro_rules! digs { ($for:ty) => { impl Ͷ for $for { fn ͷ(self) -> impl Iterator<Item = u8> { - let digits = (self.ilog10() + 1) as u8; - (0..digits) - .rev() - .map(move |n| ((self / (10 as $for).pow(n as _)) % 10) as u8) + let digits = self.ͱ() as u8; + (0..digits).rev().map(move |n| self.Ͷ(n)) + } + fn Ͷ(self, i: u8) -> u8 { + ((self / (10 as $for).pow(i as _)) % 10) as u8 } } }; } digs!(u64); -digs!(i64); -digs!(i32); digs!(u32); digs!(u16); -digs!(i16); digs!(u8); -digs!(i8); #[derive(Copy, Clone, PartialEq, PartialOrd)] pub struct Ronge { @@ -678,9 +731,7 @@ pub trait Μ where impl Μ for &[u8] { fn μ(self, d: char) -> (Self, Self) { - let i = self - .iter() - .position(|&x| x == d as u8) + let i = memchr::memchr(d as u8, self) .unwrap_or_else(|| shucks!("{} should split at {d} fine", self.p())); (&self[..i], &self[i + 1..]) } @@ -897,6 +948,7 @@ pub fn nail<const N: usize, T: Copy>(x: &[T]) -> [T; N] { } pub mod reading { + #[inline] pub fn 八(n: u64) -> u64 { // reinterpret as u64 ("92233721" => 92233721) // let n = u64::from_le_bytes(s); @@ -941,19 +993,28 @@ pub mod reading { } } use crate::util::prelude::*; - pub fn κ(x: &[u8], v: &mut Vec<u64>) { - let mut s = 0; + pub fn κ< + T: Default + std::ops::Mul<T, Output = T> + Add<T, Output = T> + From<u8> + Copy + Ten + Debug, + >( + x: &[u8], + v: &mut [T], + ) -> usize { + let mut n = 0; + let mut s = T::default(); for &b in x { match b { b' ' => { - v.push(s); - s = 0; + C! { v[n] = s }; + n += 1; + s = T::default(); } b => { - s = s * 10 + (b - b'0') as u64; + s = s * T::ten() + T::from(b - b'0'); } } } + C! {v[n] = s}; + n + 1 } pub trait Ten { fn ten() -> Self; @@ -1047,13 +1108,11 @@ pub mod reading { } } - pub fn 迄< - T: Default + std::ops::Mul<T, Output = T> + Add<T, Output = T> + From<u8> + Copy + Ten, - >( + pub fn until<T: std::ops::Mul<T, Output = T> + Add<T, Output = T> + From<u8> + Copy + Ten>( x: &mut &[u8], until: u8, ) -> T { - let mut n = T::default(); + let mut n = T::from(x.by().ψ() - b'0'); loop { let byte = x.by().ψ(); if byte == until { @@ -1063,6 +1122,7 @@ pub mod reading { } } + #[cfg_attr(debug_assertions, track_caller)] pub fn all< T: Default + std::ops::Mul<T, Output = T> + Add<T, Output = T> + From<u8> + Copy + Ten, >( @@ -1309,8 +1369,8 @@ impl<'b> TakeLine<'b> for &'b [u8] { None if self.is_empty() => None, None => Some(std::mem::replace(self, b"")), Some(end) => { - let line = &self[..end]; - *self = &self[end + 1..]; + let line = C! { &self[..end]}; + *self = C! { &self[end + 1..]}; Some(line) } } |