bendns' repos / aoc
heh
Diffstat (limited to 'src/main.rs')
-rw-r--r--src/main.rs196
1 files changed, 57 insertions, 139 deletions
diff --git a/src/main.rs b/src/main.rs
index 64ec9dd..c2985be 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -11,149 +11,67 @@
)]
extern crate test;
mod util;
-pub use util::prelude::*;
-
-#[repr(u8)]
-#[derive(Copy, Clone, PartialEq, Eq)]
-enum Element {
- #[allow(dead_code)]
- Space = b'.',
- Galaxy = b'#',
- #[allow(dead_code)]
- New = 10,
-}
-
-impl Element {
- #[inline]
- fn galaxy(self) -> bool {
- self == Self::Galaxy
- }
-}
-
-impl std::fmt::Debug for Element {
- fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
- if *self as u8 == 10 {
- return write!(f, "@");
- }
- write!(f, "{}", *self as u8 as char)
- }
-}
-
-const S: u8 = 140;
-const W: u16 = S as u16 + 1;
-
-struct Map<'a> {
- map: &'a [Element],
-}
-
-impl<'a> std::ops::Index<u16> for Map<'a> {
- type Output = Element;
-
- fn index(&self, index: u16) -> &'a Self::Output {
- unsafe { self.map.get_unchecked(index.nat()) }
- }
-}
-
-pub unsafe fn galaxies(line: &[u8]) -> usize {
- use std::arch::x86_64::*;
- let galaxy = _mm256_set1_epi8(b'#' as i8);
- let mut counts = _mm256_setzero_si256();
- for i in 0..4 {
- counts = _mm256_sub_epi8(
- counts,
- _mm256_cmpeq_epi8(
- _mm256_loadu_si256(line.as_ptr().add(i * 32) as *const _),
- galaxy,
- ),
- );
- }
- const MASK: [u8; 64] = [
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
- 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
- ];
- counts = _mm256_sub_epi8(
- counts,
- _mm256_and_si256(
- _mm256_cmpeq_epi8(
- _mm256_loadu_si256(line.as_ptr().add(108) as *const _),
- galaxy,
- ),
- _mm256_loadu_si256(MASK.as_ptr().add(12) as *const _),
- ),
- );
-
- let sums = _mm256_sad_epu8(counts, _mm256_setzero_si256());
- (_mm256_extract_epi64(sums, 0)
- + _mm256_extract_epi64(sums, 1)
- + _mm256_extract_epi64(sums, 2)
- + _mm256_extract_epi64(sums, 3)) as usize
-}
+use std::ops::ControlFlow;
-impl Map<'_> {
- fn at(&self, x: u8, y: u8) -> Element {
- self[y.widen() * W + x.widen()]
- }
+pub use util::prelude::*;
- fn solve(&self) -> usize {
- let mut sum = 0;
- let mut above = 0;
- let mut upward = 0;
- // const FACTOR: usize = 2;
- const FACTOR: usize = 1000000;
- for has in self.map.chunks(W.nat()).map(|x| {
- #[cfg(target_feature = "avx")]
- return unsafe { galaxies(std::mem::transmute(x)) };
- #[cfg(not(target_feature = "avx"))]
- return x.iter().filter(|x| x.galaxy()).count();
- }) {
- if has == 0 {
- upward += above * FACTOR;
- } else {
- sum += upward * has;
- above += has;
- upward += above;
+pub fn run(i: &str) -> impl Display {
+ i.行()
+ .map(|x| {
+ // AAA?
+ let (r, c) = x
+ .μ(' ')
+ .mr(|x| x.split(|&x| x == b',').κ::<u8>().collect::<Box<_>>());
+ fn kill_me(
+ s: Vec<u8>,
+ n: usize,
+ max: usize,
+ p: &mut impl FnMut(&[u8]) -> ControlFlow<(), bool>,
+ ) -> Vec<Vec<u8>> {
+ if n == max {
+ return vec![s];
+ }
+ let mut combinations = vec![];
+ for c in [b'.', b'#'] {
+ let mut s = s.clone();
+ s.push(c);
+ for thing in kill_me(s, n + 1, max, p) {
+ match p(&thing) {
+ ControlFlow::Break(()) => break,
+ ControlFlow::Continue(true) => combinations.push(thing),
+ _ => {}
+ }
+ }
+ }
+ combinations
}
- }
- let mut beside = 0;
- let mut left = 0;
- #[cfg(target_feature = "avx")]
- let mut x = [Element::Space; 140];
- for has in (0..S)
- .map(move |x| (0..S).map(move |y| self.at(x, y)))
- .map(|mut y| {
- #[cfg(not(target_feature = "avx"))]
- return y.filter(|x| x.galaxy()).count();
- #[cfg(target_feature = "avx")]
- return {
- y.ν(&mut x);
- unsafe { galaxies(&std::mem::transmute::<_, [u8; 140]>(x)) }
- };
+ let why = kill_me(vec![], 0, r.len(), &mut |x| {
+ for (&x, &y) in r.iter().zip(x.iter()) {
+ if matches!(x, b'.' | b'#' if y != x) {
+ return ControlFlow::Break(());
+ }
+ }
+ let mut huh = vec![];
+ let mut len = 0;
+ for &x in x {
+ match x {
+ b'#' => len += 1,
+ b'.' if len != 0 => {
+ huh.push(len);
+ len = 0;
+ }
+ _ => {}
+ }
+ }
+ if len != 0 {
+ huh.push(len);
+ }
+ ControlFlow::Continue(&*huh == &*c)
})
- {
- if has == 0 {
- left += beside * FACTOR;
- } else {
- sum += left * has;
- beside += has;
- left += beside;
- }
- }
- sum
- }
-}
-
-impl From<&[u8]> for Map<'_> {
- fn from(i: &[u8]) -> Self {
- Self {
- map: &unsafe { core::mem::transmute::<_, &[Element]>(i) }[..(W.nat() * S.nat()) - 1],
- }
- }
-}
-
-pub fn run(i: &str) -> impl Display {
- let map = Map::from(i.as_bytes());
- map.solve()
+ .len();
+ why
+ })
+ .sum::<usize>()
}
fn main() {