heh
optimize d8p2
| -rw-r--r-- | .gitignore | 3 | ||||
| -rw-r--r-- | src/main.rs | 51 | ||||
| -rw-r--r-- | src/util.rs | 47 |
3 files changed, 79 insertions, 22 deletions
@@ -1,2 +1,5 @@ /target Cargo.lock +before +prepare.sh +prepared.rs diff --git a/src/main.rs b/src/main.rs index 2a4fda5..d755ae1 100644 --- a/src/main.rs +++ b/src/main.rs @@ -2,24 +2,41 @@ #![feature(array_windows, test, slice_as_chunks, array_chunks)] extern crate test; mod util; -pub use explicit_cast::prelude::*; pub use util::prelude::*; -fn solve(i: &str) -> impl Display { +#[inline(always)] +fn k(s: &str) -> u16 { + unsafe { *s.as_ptr().cast::<[u8; 3]>() } + .iter() + .enumerate() + .map(|(i, &b)| ((b - b'A') as u16) << (i * 5)) + .sum() +} + +fn start(x: u16) -> bool { + (x >> (2 * 5) & 0b11111) == 0u16 +} + +fn end(x: u16) -> bool { + (x >> (2 * 5) & 0b11111) == (b'Z' - b'A') as u16 +} + +pub fn run(i: &str) -> impl Display { let mut lines = i.lines(); let line = lines.by_ref().Δ().as_bytes(); let map = lines .skip(1) .map(|x| { x.μ('=') - .mr(|x| x.trim()[1..x.len() - 2].μ(',').ml(str::trim).mr(str::trim)) + .mr(|x| x.trim()[1..x.len() - 2].μ(',').mb(str::trim).mb(k)) .ml(str::trim) + .ml(k) }) .collect::<HashMap<_, _>>(); let mut positions = map .keys() .map(|&x| x) - .filter(|x| x.ends_with('A')) + .filter(|&x| start(x)) .collect::<Box<[_]>>(); let mut steps = 1u64; let mut findings = HashMap::new(); @@ -29,41 +46,37 @@ fn solve(i: &str) -> impl Display { break; } for p in &mut *positions { - let at = map[*p]; + let at = map[p]; *p = match instruction { b'L' => at.0, b'R' => at.1, _ => dang!(), }; - if p.ends_with('Z') { - if let Some(&c) = findings.get(*p) { - if !cycle.contains_key(*p) { - println!("cycle {} ({steps})", steps - c); - cycle.insert(*p, steps - c); + if end(*p) { + if let Some(&c) = findings.get(p) { + match cycle.entry(*p) { + Entry::Occupied(_) => {} + Entry::Vacant(x) => { + x.insert(steps - c); + } } } else { - println!("register {p} ({steps})"); findings.insert(*p, steps); } } } steps += 1; } - print!("lcm("); - for cycle in cycle.values() { - print!("{cycle},") - } - println!(")"); - 0 + lcm(cycle.values().copied()) } fn main() { let i = include_str!("inp.txt").trim(); - println!("{}", solve(i)); + println!("{}", run(i)); } #[bench] fn bench(b: &mut test::Bencher) { let i = boxd(include_str!("inp.txt").trim()); - b.iter(|| solve(i)); + b.iter(|| run(i)); } diff --git a/src/util.rs b/src/util.rs index 5320a8d..b633247 100644 --- a/src/util.rs +++ b/src/util.rs @@ -1,15 +1,16 @@ #![allow(non_snake_case)] -use std::str::FromStr; +use std::{mem::swap, str::FromStr}; pub mod prelude { pub use super::{ - GreekTools, IterͶ, NumTupleIterTools, TupleIterTools, TupleUtils, Ͷ, Α, Κ, Λ, Μ, + gcd, lcm, GreekTools, IterͶ, NumTupleIterTools, TupleIterTools, TupleUtils, + UnifiedTupleUtils, Ͷ, Α, Κ, Λ, Μ, }; pub use itertools::izip; pub use itertools::Itertools; pub use std::{ cmp::Ordering::*, - collections::{HashMap, HashSet, VecDeque}, + collections::{hash_map::Entry, HashMap, HashSet, VecDeque}, fmt::{Debug, Display}, hint::black_box as boxd, iter, @@ -26,6 +27,36 @@ macro_rules! dang { } pub(crate) use dang; +pub fn lcm(n: impl IntoIterator<Item = u64>) -> u64 { + let mut x = n.into_iter(); + let mut lcm = x.by_ref().next().expect("cannot compute LCM of 0 numbers"); + let mut gcd; + for x in x { + gcd = crate::util::gcd(x, lcm); + lcm = (lcm * x) / gcd; + } + lcm +} + +pub fn gcd(mut a: u64, mut b: u64) -> u64 { + if a == 0 || b == 0 { + return a | b; + } + let shift = (a | b).trailing_zeros(); + a >>= shift; + loop { + b >>= b.trailing_zeros(); + if a > b { + swap(&mut a, &mut b); + } + b -= a; + if b == 0 { + break; + } + } + return a << shift; +} + pub trait Λ { fn λ<T: FromStr>(&self) -> T where @@ -207,6 +238,16 @@ pub trait TupleUtils<T, U> { fn rev(self) -> (U, T); } +pub trait UnifiedTupleUtils<T> { + fn mb<U>(self, f: impl FnMut(T) -> U) -> (U, U); +} + +impl<T> UnifiedTupleUtils<T> for (T, T) { + fn mb<U>(self, mut f: impl FnMut(T) -> U) -> (U, U) { + (f(self.0), f(self.1)) + } +} + impl<T, U> TupleUtils<T, U> for (T, U) { fn map<V, W>(self, f: impl FnOnce((T, U)) -> (V, W)) -> (V, W) { f(self) |