heh
d14p2
| -rw-r--r-- | src/main.rs | 108 | ||||
| -rw-r--r-- | src/util.rs | 44 |
2 files changed, 128 insertions, 24 deletions
diff --git a/src/main.rs b/src/main.rs index 3498a82..ebea405 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,5 +1,6 @@ #![allow(confusable_idents, uncommon_codepoints, mixed_script_confusables)] #![feature( + slice_flatten, iter_collect_into, let_chains, anonymous_lifetime_in_impl_trait, @@ -13,44 +14,113 @@ byte_slice_trim_ascii )] extern crate test; -mod util; -pub use util::prelude::*; +pub mod util; -fn weigh(mat: Vec<[u8; 100]>) -> usize { - mat.iter() - .ι::<usize>() - .map(|(row, i)| util::count::<100>(&row, b'O') * (100 - i)) - .sum() -} +pub use util::prelude::*; -#[no_mangle] -pub fn run(i: &str) -> impl Display { - let mut v = Vec::with_capacity(100); +pub fn p1(i: &str) -> usize { + let mut mat = Vec::with_capacity(100); let mut i = i.as_bytes(); for _ in 0..100 { - v.push(unsafe { <&[u8; 100]>::try_from(i.get_unchecked(..100)).unwrap() }); + mat.push(unsafe { <&[u8; 100]>::try_from(i.get_unchecked(..100)).unwrap() }); i = unsafe { i.get_unchecked(100..) }; if i.len() != 0 { i = unsafe { i.get_unchecked(1..) }; } } - weigh(pushhh(v)) -} - -fn pushhh(mat: Vec<&[u8; 100]>) -> Vec<[u8; 100]> { - let mut new = vec![[0; 100]; 100]; + let mut rows = [0u8; 100]; for j in 0..100 { let mut count = 0; for i in 0..100 { if *unsafe { mat.get_unchecked(i).get_unchecked(j) } == b'O' { - *unsafe { new.get_unchecked_mut(count).get_unchecked_mut(j) } = b'O'; + *unsafe { rows.get_unchecked_mut(count) } += 1; count += 1; } else if mat[i][j] == b'#' { count = i + 1; } } } - new + rows.iter() + .ι::<usize>() + .map(|(&x, i)| (x.nat()) * (100 - i)) + .sum::<usize>() +} + +fn pushhhh(mat: &mut Vec<[u8; 100]>) { + for j in 0..100 { + let mut count = 0; + for i in 0..100 { + let curr = C! { mat[i][j] }; + mat!(curr { + b'O' => { + C! { mat[i][j] = mat[count][j] }; + C! { mat[count][j] = curr }; + count += 1; + }, + b'#' => count = i + 1, + b'.' => {}, + }); + } + } +} + +#[no_mangle] +pub fn run(i: &str) -> impl Display { + p2(i) +} + +fn weigh(mat: &[[u8; 100]]) -> u32 { + mat.iter() + .ι::<usize>() + .map(|(row, i)| (util::count::<100>(&row, b'O') * (100 - i)) as u32) + .sum() +} + +pub fn h(data: &[u8; 10000]) -> u16 { + let mut buffer = 509; + let mut data = &data[..]; + while data.len() > 16 { + let (value, rest) = data.split_at(16); + let [a, b]: [u64; 2] = unsafe { rint(<[u8; 16]>::try_from(value).unwrap()) }; + buffer ^= a.wrapping_mul(b) ^ a; + data = rest; + } + (buffer ^ buffer.swap_bytes()) as u16 +} + +fn hash(x: &[[u8; 100]]) -> u16 { + h(&unsafe { *x.as_ptr().cast() }) +} + +pub fn p2(i: &str) -> impl Display { + let mut mat = Vec::with_capacity(100); + let mut i = i.as_bytes(); + for _ in 0..100 { + mat.push(unsafe { <[u8; 100]>::try_from(i.get_unchecked(..100)).unwrap() }); + i = unsafe { i.get_unchecked(100..) }; + if i.len() != 0 { + i = unsafe { i.get_unchecked(1..) }; + } + } + let mut map = vec![(hash(&mat), weigh(&mat))]; + loop { + for _ in 0..4 { + pushhhh(&mut mat); + let mut new = vec![[0; 100]; 100]; + for row in 0..100 { + for col in 0..100 { + C! { new[col][99 - row] = mat[row][col] }; + } + } + mat = new; + } + let c = hash(&mat); + if let Some(y) = map.iter().position(|&(x, _)| x == c) { + let c = map.len() - y; + return C! { map[y + (1e9 as usize - y) % c] }.1; + } + map.push((c, weigh(&mat))); + } } fn main() { diff --git a/src/util.rs b/src/util.rs index e697233..ee4eb7f 100644 --- a/src/util.rs +++ b/src/util.rs @@ -6,6 +6,8 @@ use std::{ }; pub mod prelude { + #[allow(unused_imports)] + pub(crate) use super::{bits, dang, leek, mat, shucks, C}; pub use super::{ even, gcd, lcm, pa, GreekTools, IntoCombinations, IntoLines, IterͶ, NumTupleIterTools, ParseIter, Printable, Skip, TakeLine, TupleIterTools, TupleUtils, UnifiedTupleUtils, Widen, @@ -20,13 +22,45 @@ pub mod prelude { fmt::{Debug, Display}, hint::black_box as boxd, iter, - mem::transmute as rint, + mem::{replace as rplc, swap, transmute as rint}, ops::Range, }; - #[allow(unused_imports)] - pub(crate) use {super::bits, super::dang, super::leek, super::mat}; } +macro_rules! C { + ($buf:ident[$n:expr]) => { + unsafe { *$buf.get_unchecked($n) } + }; + ($buf:ident[$n:expr] = $e:expr) => { + *unsafe { $buf.get_unchecked_mut($n) } = $e + }; + ($buf:ident[$a:expr][$b:expr]) => { + unsafe { *$buf.get_unchecked($a).get_unchecked($b) } + }; + ($buf:ident[$a:expr][$b:expr] = $rbuf:ident[$ra:expr][$rb:expr]) => { + *unsafe { $buf.get_unchecked_mut($a).get_unchecked_mut($b) } = + unsafe { *$rbuf.get_unchecked($ra).get_unchecked($rb) } + }; + ($buf:ident[$a:expr][$b:expr] = $c:expr) => {{ + #[allow(unused_unsafe)] + { + *unsafe { $buf.get_unchecked_mut($a).get_unchecked_mut($b) } = unsafe { $c } + } + }}; +} +pub(crate) use C; + +macro_rules! shucks { + () => { + if cfg!(debug_assertions) { + unreachable!(); + } else { + unsafe { std::hint::unreachable_unchecked() } + } + }; +} +pub(crate) use shucks; + macro_rules! dang { () => { panic!() @@ -43,7 +77,7 @@ pub(crate) use leek; macro_rules! mat { ($thing:ident { $($what:pat => $b:expr,)+ }) => { - match $thing { $($what => { $b })+ _ => unsafe { std::hint::unreachable_unchecked() } } + match $thing { $($what => { $b })+ _ => shucks!() } }; } pub(crate) use mat; @@ -87,7 +121,7 @@ unsafe fn count_avx<const N: usize>(hay: &[u8; N], needle: u8) -> usize { pub fn count<const N: usize>(hay: &[u8; N], what: u8) -> usize { #[cfg(target_feature = "avx2")] - return count_avx(hay, what); + return unsafe { count_avx(hay, what) }; #[cfg(not(target_feature = "avx2"))] hay.iter().filter(|&&x| x == what).count() } |