heh
21p2
| -rw-r--r-- | src/main.rs | 63 | ||||
| -rw-r--r-- | src/util.rs | 23 |
2 files changed, 44 insertions, 42 deletions
diff --git a/src/main.rs b/src/main.rs index 31419cb..718b2a7 100644 --- a/src/main.rs +++ b/src/main.rs @@ -36,9 +36,9 @@ extern crate test; pub mod util; use atools::CollectArray; use iter::once; +use util::memoize; pub use util::prelude::*; -const SIZE: usize = 141; #[rustfmt::skip] fn numpad(x: u8) -> (usize, usize) { match x { @@ -57,7 +57,6 @@ fn dpad(x: u8) -> (usize, usize) { _ => unreachable!(), } } - fn pathfind<const N: usize, const M: usize>( input: impl IntoIterator<Item = (u8, (usize, usize))>, grid: [[u8; N]; M], @@ -78,6 +77,7 @@ fn pathfind<const N: usize, const M: usize>( ] .into_iter() .filter(|&((x, y), _)| matches!(grid.get(y).map(|y| y.get(x)), Some(Some(_)))) + .filter(|&((x, y), _)| grid[y][x] != 0) .map(move |(p, dir)| ((p, at, dir), 1)) }, |_| 0, @@ -125,7 +125,6 @@ fn num(code: [u8; 4]) -> Vec<Vec<u8>> { let starts = once(numpad(b'A')).chain(code.iter().copied().map(numpad)); pathfind(code.iter().copied().zip(starts), grid) } - fn pad(code: Vec<u8>) -> Vec<Vec<u8>> { #[rustfmt::skip] let grid = [ @@ -136,42 +135,44 @@ fn pad(code: Vec<u8>) -> Vec<Vec<u8>> { pathfind(code.iter().copied().zip(starts), grid) } -fn my_pad(code: Vec<u8>) -> Vec<Vec<u8>> { - #[rustfmt::skip] - let grid = [ - [0, b'^',b'A'], - [b'<',b'v',b'>'], - ]; - let starts = once(dpad(b'A')).chain(code.iter().copied().map(dpad)); - pathfind(code.iter().copied().zip(starts), grid) +const MAXDEPTH: u8 = 25; +fn solve(thing: Vec<u8>, deep: u8) -> usize { + if deep == MAXDEPTH { + return thing.len(); + } + memoize!(|(thing, deep) in (Vec<u8>, u8)| -> usize { + thing[..thing.len() - 1] + .split(|x| *x == b'A') + .into_iter() + .map(|x| { + let mut x = x.to_vec(); + x.push(b'A'); + pad(x.to_vec()) + .into_iter() + .map(|x| solve(x, deep + 1)) + .min() + .unwrap() + }) + .sum() + }; (thing, deep)) } pub fn run(x: &str) -> impl Display { let i = x.as_bytes(); let codes: [&[u8]; 5] = i.行().carr(); - use rayon::prelude::*; codes - .par_iter() - .map(|&code_| { - let mut complex = usize::MAX; - let numpad_codes = num(code_.try_into().unwrap()); + .into_iter() + .map(|code_| { let numeric: u64 = reading::all(&code_[..3]); - for code in numpad_codes { - for pad in pad(code) { - for pad in my_pad(pad) { - let complexity = pad.len() * numeric as usize; - if complexity < complex { - dbg!(pad.len()); - dbg!(numeric); - } - complex = complex.min(complexity); - } - } - } - dbg!(complex); - complex + let length = num(code_.try_into().unwrap()) + .into_iter() + .map(|x| solve(x, 0)) + .min() + .unwrap() as u64; + println!("{length} * {numeric}"); + length * numeric }) - .sum::<usize>() + .sum::<u64>() } fn main() { diff --git a/src/util.rs b/src/util.rs index 5cd3273..4f9f819 100644 --- a/src/util.rs +++ b/src/util.rs @@ -4,7 +4,7 @@ use rustc_hash::FxHashMap as HashMap; use rustc_hash::FxHashSet as HashSet; use std::{ cmp::Reverse, - collections::{hash_map::Entry, BinaryHeap}, + collections::BinaryHeap, fmt::{Debug, Display, Write}, hash::Hash, mem::swap, @@ -212,7 +212,7 @@ impl UnionFind { } } - fn reset(&mut self) { + pub fn reset(&mut self) { self.s.fill(1); self.p .iter_mut() @@ -247,7 +247,7 @@ impl UnionFind { true } - fn group_size(&self, group: usize) -> usize { + pub fn group_size(&self, group: usize) -> usize { self.s[group] } } @@ -276,18 +276,18 @@ impl<T, E> UnsoundUtilities<T> for Result<T, E> { } } -pub struct LMap<K, V>(HashMap<K, V>, fn(K) -> V) +pub struct LMap<K, V>(HashMap<K, V>, fn(&K) -> V) where - K: Eq + Hash + Copy; -impl<K: Ord + Eq + Debug + Hash + Copy, V: Copy + Debug> LMap<K, V> { - pub fn new(f: fn(K) -> V) -> Self { + K: Eq + Hash + Clone; +impl<K: Ord + Eq + Debug + Hash + Clone, V: Copy + Debug> LMap<K, V> { + pub fn new(f: fn(&K) -> V) -> Self { Self { 0: HashMap::default(), 1: f, } } - pub fn with_cap(f: fn(K) -> V, cap: usize) -> Self { + pub fn with_cap(f: fn(&K) -> V, cap: usize) -> Self { Self { 0: HashMap::with_capacity_and_hasher(cap, rustc_hash::FxBuildHasher::default()), 1: f, @@ -301,8 +301,8 @@ impl<K: Ord + Eq + Debug + Hash + Copy, V: Copy + Debug> LMap<K, V> { // let mut ks = self.0.keys().collect::<Vec<_>>(); // ks.sort(); // println!("{ks:?}"); - let elm = self.1(k); - self.0.insert(k, elm); + let elm = self.1(&k); + self.0.insert(k.clone(), elm); elm } } @@ -312,7 +312,7 @@ macro_rules! memoize { static mut MEMOIZER: std::sync::OnceLock<crate::util::LMap<$in, $out>> = std::sync::OnceLock::new(); unsafe { - MEMOIZER.get_mut_or_init(|| crate::util::LMap::new(|$pat: $in| -> $out { $body })) + MEMOIZER.get_mut_or_init(|| crate::util::LMap::new(|$pat: &$in| -> $out { $body })) } .get($arg) }}; @@ -327,6 +327,7 @@ macro_rules! memoize { .get($arg) }}; } +#[allow(unused_imports)] pub(crate) use memoize; pub fn countg_with_check<N: Debug + PartialEq + Hash + Eq + Copy, I: Iterator<Item = N>>( |