| -rw-r--r-- | src/lib.rs | 167 | ||||
| -rw-r--r-- | src/util.rs | 1 |
2 files changed, 124 insertions, 44 deletions
@@ -26,58 +26,137 @@ hint_assert_unchecked )] mod util; -pub mod day7 { +pub mod day8 { use super::util::prelude::*; - - #[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; + const SIZE: usize = 50; + #[no_mangle] + pub fn part2(i: &str) -> impl Display { + let i = i.as_bytes(); + let mut big: [[(u8, u8); 4]; 123] = [[(0, 0); 4]; 123]; + let mut lengths = [0; 123]; + for (row_, i) in unsafe { i.as_chunks_unchecked::<{ SIZE + 1 }>() } + .iter() + .ι::<u8>() + { + let row = u8x64::load_or_default(row_); + let mut row = row.simd_ne(Simd::splat(b'.')).to_bitmask() & ((1 << 50) - 1); + while row != 0 { + let x = row.trailing_zeros(); + row &= !(1 << x); + let &el = &row_[x as usize]; + let l = unsafe { lengths.get_unchecked_mut(el as usize) }; + C! { big[el as usize][*l] = (i, x as u8) }; + *l += 1; + } } - sum - } - - 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)) + let mut anti = [0u64; SIZE]; + for char in (b'A'..=b'Z').chain(b'a'..=b'z').chain(b'0'..=b'9') { + // let memchr = memchr::Memchr::new(char, i); + // let wat = memchr.map(split).collect_vec(); + let all = unsafe { + big.get_unchecked(char as usize) + .get_unchecked(..*lengths.get_unchecked(char as usize)) + }; + let mut anti = |(x1, y1), (x2, y2)| { + let mut x3 = x2 + (x2 - x1); + let mut y3 = y2 + (y2 - y1); + *C! { &mut anti[y2 as usize] } |= 1 << x2 as u64; + while (x3 < SIZE as u8) & (y3 < SIZE as u8) { + anti[y3 as usize] |= 1 << x3 as u64; + x3 += x2 - x1; + y3 += y2 - y1; + } + }; + match all { + &[] => continue, + &[a, b, c, d] => { + let mut one = |i, j| { + anti(i, j); + anti(j, i); + }; + one(b, a); + one(c, a); + one(c, b); + one(d, a); + one(d, b); + one(d, c); + } + &[a, b, c] => { + let mut one = |i: (u8, u8), j: (u8, u8)| { + anti(i, j); + anti(j, i); + }; + one(b, a); + one(c, a); + one(c, b); } - [] => shucks!(), + _ => shucks!(), } } - do_(i, search) + anti.into_iter().map(u64::count_ones).sum::<u32>() } - - pub fn part2(i: &str) -> impl Display { - 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)) + use std::simd::prelude::*; + #[no_mangle] + pub fn part1(i: &str) -> u32 { + let mut big: [[(u8, u8); 4]; 123] = [[(0, 0); 4]; 123]; + let mut lengths = [0; 123]; + let i = i.as_bytes(); + for (row_, i) in unsafe { i.as_chunks_unchecked::<{ SIZE + 1 }>() } + .iter() + .ι::<u8>() + { + let row = u8x64::load_or_default(row_); + let mut row = row.simd_ne(Simd::splat(b'.')).to_bitmask() & ((1 << 50) - 1); + while row != 0 { + let x = row.trailing_zeros(); + row &= !(1 << x); + let &el = &row_[x as usize]; + let l = unsafe { lengths.get_unchecked_mut(el as usize) }; + C! { big[el as usize][*l] = (i, x as u8) }; + *l += 1; + } + } + let mut anti = [0u64; SIZE]; + for char in (b'A'..=b'Z').chain(b'a'..=b'z').chain(b'0'..=b'9') { + // let memchr = memchr::Memchr::new(char, i); + // let wat = memchr.map(split).collect_vec(); + let all = unsafe { + big.get_unchecked(char as usize) + .get_unchecked(..*lengths.get_unchecked(char as usize)) + }; + // assert_eq!(wat, all); + let mut anti = |(x1, y1), (x2, y2): (u8, u8)| { + let x3 = x2.wrapping_add(x2.wrapping_sub(x1)); + let y3 = y2.wrapping_add(y2.wrapping_sub(y1)); + if (x3 < SIZE as u8) & (y3 < SIZE as u8) { + anti[y3 as usize] |= 1 << x3 as u64; + } + }; + match all.len() { + 0 => continue, + 4 => { + for i in 0..4 { + for j in 0..i { + let i = all[i]; + let j = all[j]; + anti(i, j); + anti(j, i); + } + } + } + 3 => { + for i in 0..3 { + for j in 0..i { + let i = all[i]; + let j = all[j]; + anti(i, j); + anti(j, i); + } + } } - [] => shucks!(), + _ => shucks!(), } } - do_(i, |n, should| search(n, should)) + anti.into_iter().map(u64::count_ones).sum::<u32>() } } diff --git a/src/util.rs b/src/util.rs index b8a3d87..41aef47 100644 --- a/src/util.rs +++ b/src/util.rs @@ -937,6 +937,7 @@ macro_rules! ι { } }; } +ι!(i8); ι!(u8); ι!(u16); ι!(u32); |