heh
2017/14: 53:56
| -rw-r--r-- | src/main.rs | 89 | ||||
| -rw-r--r-- | src/util.rs | 34 |
2 files changed, 95 insertions, 28 deletions
diff --git a/src/main.rs b/src/main.rs index 8735208..94f7296 100644 --- a/src/main.rs +++ b/src/main.rs @@ -66,34 +66,75 @@ use std::{ use swizzle::array; pub use util::prelude::*; +use crate::util::{MapF, UnionFind}; +#[implicit_fn::implicit_fn] +fn kh(x: impl Iterator<Item = u8> + Clone) -> [u8; 32] { + let lengths = x.map(_ as usize).chain([17, 31, 73, 47, 23]); + + let mut x = range::<256>(); + let mut c = 0; + let mut s = 0; + + for _ in 0..64 { + for l in lengths.clone() { + if (c + l) > 256 { + let mut i = x + .into_iter() + .cycle() + .skip(c) + .take(l) + .collect::<Vec<_>>() + .into_iter() + .rev(); + x.get_mut(c..(c + l).min(256)) + .map(|s| s.copy_from_slice(&i.by_ref().take(s.len()).collect::<Vec<_>>())); + x[..c + l - 256].copy_from_slice(&i.by_ref().take(c + l - 256).collect::<Vec<_>>()); + assert_eq!(i.collect::<Vec<_>>(), &[]); + } else { + x.get_mut(c..(c + l).min(256)).map(_.reverse()); + } + + c += l + s; + c %= 256; + s += 1; + } + } + + x.chunked::<16>() + .map(|x| x.into_iter().reduce(_ ^ _).ψ() as u8) + .map(|x| [x >> 4, x & 0x0f]) + .flatten() +} + #[unsafe(no_mangle)] #[implicit_fn::implicit_fn] pub unsafe fn p1(x: &'static [u8; ISIZE]) -> impl Debug { - let x = x.行().map(|x| util::ints(x).carr::<2>()).carr::<43>(); - fn at_t<const N: usize>(x: [[i64; 2]; N], t: i64) -> [i64; N] { - x.map(|[_, depth]| { - let k = t % (2 * (depth - 1)); - k.min(2 * depth - 1 - k) + let grid: [[bool; 128]; 128] = (0..128) + .map(|x| { + kh(format!("ugkiagan-{x}").bytes()) + .map(|b| util::each_bit(b).drop::<4>()) + .flatten() }) - } - fn passes<const N: usize>(position: i64, x: [[i64; 2]; N], t: i64) -> bool { - x.into_iter() - .position(|[p, _]| p == position) - .map(|y| at_t(x, t)[y] != 0) - .unwrap_or(true) - } - [ - (0..) - .zip(0..) - .take(100) - .filter(move |&(p, t)| !passes(p, x, t)) - .map(|(p, _)| x.into_iter().find(|&[p2, _]| p == p2).unwrap()) - .map(|[a, b]| a * b) - .sum::<i64>(), - (0..) - .find(|&t| (0..).zip(t..).take(100).all(|(p, t)| passes(p, x, t))) - .ψ(), - ] + .carr::<128>(); + + let on = (0..128usize) + .flat_map(move |y| (0..128).map(move |x| (x, y))) + .filter(|&(x, y)| grid[y][x]); + ( + on.clone().count(), + on.clone() + .fold(UnionFind::new(128 * 128), |mut uf, (x, y)| { + Dir::ALL + .into_iter() + .flat_map(|d| d.lim_add((x, y), [0, 128], [0, 128])) + .filter(|&(x_, y_)| grid[y_][x_]) + .for_each(|(x_, y_)| { + uf.union(y_ * 128 + x_, y * 128 + x); + }); + uf + }) + .𝙢𝙖𝙥(|mut uf| on.map(|(x, y)| uf.find(y * 128 + x)).unique().count()), + ) } const ISIZE: usize = include_bytes!("inp.txt").len(); fn main() { diff --git a/src/util.rs b/src/util.rs index e64fbf1..dcec3bf 100644 --- a/src/util.rs +++ b/src/util.rs @@ -2079,20 +2079,30 @@ pub mod spiral { } pub trait AndF { - fn and<T>(self, f: impl FnMut(&Self) -> T) -> Self; + fn and<T>(self, f: impl FnOnce(&Self) -> T) -> Self; } impl<T> AndF for T { - fn and<U>(self, mut f: impl FnMut(&Self) -> U) -> Self { + fn and<U>(self, f: impl FnOnce(&Self) -> U) -> Self { f(&self); self } } +pub trait MapF: Sized { + #[doc(alias = "map")] + fn 𝙢𝙖𝙥<T>(self, f: impl FnOnce(Self) -> T) -> T; +} +impl<U> MapF for U { + fn 𝙢𝙖𝙥<T>(self, f: impl FnOnce(Self) -> T) -> T { + f(self) + } +} + pub trait Splib { - fn splib<'a>(&'a self, seq: &'static [u8]) -> impl Iterator<Item = &[u8]> + 'a; + fn splib(&'_ self, seq: &'static [u8]) -> impl Iterator<Item = &'_ [u8]> + '_; } impl Splib for [u8] { - fn splib<'a>(&'a self, seq: &'static [u8]) -> impl Iterator<Item = &[u8]> + 'a { + fn splib(&'_ self, seq: &'static [u8]) -> impl Iterator<Item = &'_ [u8]> + '_ { self.str().split(seq.str()).map(str::as_bytes) } } @@ -2233,3 +2243,19 @@ pub mod hexagon { ((q).abs() + (q + r).abs() + (r).abs()) / 2 } } + +pub fn each_bit< + T: reading::Ten + + Default + + std::ops::Shl<usize, Output = T> + + std::ops::BitAnd<T, Output = T> + + std::cmp::PartialEq + + Copy, +>( + b: T, +) -> [bool; size_of::<T>() * 8] { + use atools::prelude::*; + atools::range() + .rev() + .map(|x| b & (T::ONE << x) != T::default()) +} |