heh
| -rw-r--r-- | src/main.rs | 126 | ||||
| -rw-r--r-- | src/util.rs | 96 |
2 files changed, 85 insertions, 137 deletions
diff --git a/src/main.rs b/src/main.rs index bfa424a..2ba9db6 100644 --- a/src/main.rs +++ b/src/main.rs @@ -69,122 +69,22 @@ pub use util::prelude::*; #[allow(warnings)] type u32x3 = Simd<u32, 3>; - -impl Debug for Item { - fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { - write!(f, "{} {:?}", self.name.get(), self.kind) - } -} - -#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)] - -struct Item { - name: identifier, - kind: ItemK, -} -#[derive(Clone, Copy, Debug)] -#[repr(u8)] -enum identifier { - u1, - u2, - u3, - u4, - u5, - u6, - u7, - u8, - u9, -} -impl identifier { - fn get(self) -> u8 { - self as u8 - } -} -impl PartialEq for identifier { - fn eq(&self, other: &Self) -> bool { - self.get() == other.get() - } -} -impl Eq for identifier {} -impl PartialOrd for identifier { - fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> { - self.get().partial_cmp(&other.get()) - } -} -impl Ord for identifier { - fn cmp(&self, other: &Self) -> std::cmp::Ordering { - self.get().cmp(&other.get()) - } -} -impl Hash for identifier { - fn hash<H: std::hash::Hasher>(&self, state: &mut H) { - self.get().hash(state) - } -} -#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)] -enum ItemK { - Chip, - Gen, -} -use ItemK::*; #[unsafe(no_mangle)] #[implicit_fn::implicit_fn] pub unsafe fn p1(x: &'static [u8; ISIZE]) -> impl Debug { - let re = Regex::new(r"([0-9a-z]+) generator").unwrap(); - let rechip = Regex::new(r"([0-9a-z]+)-compatible microchip").unwrap(); - let mut floors = vec![vec![]; 4]; - x.行().zip(&mut floors).for_each(|(x, to)| { - to.extend(re.captures_iter(x).map(|x| Item { - name: transmute(x.get(1).unwrap().as_bytes()[0] - b'0'), - kind: Gen, - })); - to.extend(rechip.captures_iter(x).map(|x| Item { - name: transmute(x.get(1).unwrap().as_bytes()[0] - b'0'), - kind: Chip, - })); - }); - // if a chip is ever left in the same area as another RTG, and it's not connected to its own RTG, the chip will be fried. - fn not_fried(floor: impl Iterator<Item = Item> + Clone) -> bool { - floor.clone().all(_.kind == Chip) - || floor - .clone() - .filter(_.kind == Chip) // every chip - .all(|x| floor.clone().filter(_.kind == Gen).any(_.name == x.name)) // is connected - }; - - util::steps_astar( - (0, floors), - |(e, floor)| { - [(e < 3).then(|| e + 1), (e > 0).then(|| e - 1)] - .into_iter() - .flatten() - .flat_map(move |v| { - floor[e] - .clone() - .into_iter() - .ι() - .tuple_combinations() - .map(|(a, b)| vec![a, b]) - .chain(floor[e].clone().into_iter().ι().map(|a| vec![a])) - .map({ - let floor = floor.clone(); - move |mut x| { - let mut floor = floor.clone(); - floor[v].extend(x.iter().map(|x| x.0)); - x.sort_by_key(|x| x.1); - x.iter().rev().map(|(_, i)| floor[e].swap_remove(*i)).θ(); - floor[v].sort(); - floor[e].sort(); - (v, floor) - } - }) - }) - .filter(|(e, floor)| not_fried(floor[*e].iter().copied())) - .map(|n| (n, 1)) - }, - |x| -(x.1[3].len() as i16), - |(_, f)| f[0..3].iter().all(_.is_empty()), - ) + let mut store = Vec::with_capacity(1024); + store.push(1); + (1..) + .map(|x| { + util::nb(spiral::coordinate_of(x)) + .map(spiral::index_at) + .iter() + .flat_map(|x| store.get(*x as usize)) + .sum::<u32>() + .and(|&x| store.push(x)) + }) + .find(|x| *x > 325489) + // util::manhattan((-285, -267), (0, 0)) } const ISIZE: usize = include_bytes!("inp.txt").len(); fn main() { diff --git a/src/util.rs b/src/util.rs index 0afefa4..3795648 100644 --- a/src/util.rs +++ b/src/util.rs @@ -21,12 +21,12 @@ use std::{ pub mod prelude { pub use super::{ - BoolTools, DigiCount, Dir, FilterBy, FilterBy3, GreekTools, GridFind, IntoCombinations, - IntoLines, IterͶ, MapWith, NumTupleIterTools, ParseIter, PartitionByKey, Printable, Skip, - SplitU8, Str, TakeLine, TupleIterTools2, TupleIterTools2R, TupleIterTools3, TupleUtils, - TwoWayMapCollect, UnifiedTupleUtils, UnsoundUtilities, Widen, countmap, even, gcd, gt, - infinite_successors, l, lcm, lt, nail, pa, r, rand, reading, reading::Ext, sort, twice, Ͷ, - Α, Ι, Κ, Λ, Μ, + AndF, BoolTools, DigiCount, Dir, FilterBy, FilterBy3, GreekTools, GridFind, + IntoCombinations, IntoLines, IterͶ, MapWith, NumTupleIterTools, ParseIter, PartitionByKey, + Printable, Skip, SplitU8, Str, TakeLine, TupleIterTools2, TupleIterTools2R, + TupleIterTools3, TupleUtils, TwoWayMapCollect, UnifiedTupleUtils, UnsoundUtilities, Widen, + countmap, even, gcd, gt, infinite_successors, l, lcm, lt, nail, pa, r, rand, reading, + reading::Ext, sort, spiral, twice, Ͷ, Α, Ι, Κ, Λ, Μ, }; #[allow(unused_imports)] pub(crate) use super::{C, bits, dang, leek, mat, shucks}; @@ -1383,7 +1383,7 @@ pub mod reading { s = T::default(); } b => { - s = s * T::ten() + T::from(b - b'0'); + s = s * T::TEN + T::from(b - b'0'); } } } @@ -1391,14 +1391,14 @@ pub mod reading { n + 1 } pub trait Ten { - fn ten() -> Self; + const TEN: Self; + const ONE: Self; } macro_rules! tenz { ($for:ty) => { impl Ten for $for { - fn ten() -> $for { - 10 - } + const TEN: Self = 10; + const ONE: Self = 1; } }; } @@ -1464,7 +1464,7 @@ pub mod reading { if x == until { return n; } - n = n * T::ten() + T::from(x - b'0') + n = n * T::TEN + T::from(x - b'0') } } @@ -1492,7 +1492,7 @@ pub mod reading { if byte == until { return n; } - n = n * T::ten() + T::from(byte - b'0'); + n = n * T::TEN + T::from(byte - b'0'); } } @@ -1504,7 +1504,7 @@ pub mod reading { ) -> T { let mut n = T::default(); for &byte in x { - n = n * T::ten() + T::from(byte - b'0'); + n = n * T::TEN + T::from(byte - b'0'); } n } @@ -1913,18 +1913,22 @@ pub fn ints(x: &'static [u8]) -> impl Iterator<Item = i64> { static RE: LazyLock<Regex> = LazyLock::new(|| Regex::new("-?[0-9]+").unwrap()); RE.find_iter(x.str()).map(|x| x.as_str().λ()) } -#[lower::apply(wrapping)] -pub fn nb(x: usize, y: usize) -> [(usize, usize); 8] { + +pub fn nb< + T: Default + std::ops::Sub<T, Output = T> + std::ops::Add<T, Output = T> + Copy + reading::Ten, +>( + (x, y): (T, T), +) -> [(T, T); 8] { [ - (x - 1, y - 1), - (x, y - 1), - (x + 1, y - 1), - (x - 1, y), + (x - T::ONE, y - T::ONE), + (x, y - T::ONE), + (x + T::ONE, y - T::ONE), + (x - T::ONE, y), // this - (x + 1, y), - (x - 1, y + 1), - (x, y + 1), - (x + 1, y + 1), + (x + T::ONE, y), + (x - T::ONE, y + T::ONE), + (x, y + T::ONE), + (x + T::ONE, y + T::ONE), ] } pub fn twice<T: Copy>(x: T) -> impl Iterator<Item = T> + Clone + ExactSizeIterator { @@ -2030,3 +2034,47 @@ impl<K: Eq + Hash + Clone, V: Clone, I: Iterator<Item = ((K, K), V)>> TwoWayMapC m } } + +/// for spiral such as +/// 9 10 11 12 +/// 8 1 2 13 +/// 7 0 3 14 +/// 6 5 4 15 +pub mod spiral { + // https://www.desmos.com/calculator/qpn25p39v9 + pub fn coordinate_of(n: u64) -> (i64, i64) { + let m = n.isqrt() as i64; + + ( + (-1i64).pow(m as u32 + 1) + * (((n as i64 - m * (m + 1)) // _ + * (((2.0 * (n as f64).sqrt()).floor() as i64 + 1) % 2)) + + (m + 1) / 2), + (-1i64).pow(m as u32) + * ((n as i64 - m * (m + 1)) // _ + * ((2.0 * (n as f64).sqrt()).floor() as i64 % 2) + - (m + 1) / 2), + ) + } + + //https://math.stackexchange.com/a/1860731 + pub fn index_at((x, y): (i64, i64)) -> i64 { + let s = if x.abs() >= y.abs() { x } else { -y }; + + if s >= 0 { + 4 * s * s - x + -y + } else { + 4 * s * s + (-1_i64).pow((s == x) as u32) * (2 * s + x + -y) + } + } +} + +pub trait AndF { + fn and<T>(self, f: impl FnMut(&Self) -> T) -> Self; +} +impl<T> AndF for T { + fn and<U>(self, mut f: impl FnMut(&Self) -> U) -> Self { + f(&self); + self + } +} |