bendns' repos / aoc
heh
Diffstat (limited to 'src/main.rs')
-rw-r--r--src/main.rs170
1 files changed, 130 insertions, 40 deletions
diff --git a/src/main.rs b/src/main.rs
index 177700a..31419cb 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -34,54 +34,144 @@
)]
extern crate test;
pub mod util;
+use atools::CollectArray;
+use iter::once;
pub use util::prelude::*;
const SIZE: usize = 141;
-pub fn run(x: &str) -> impl Display {
- let i = x.as_bytes();
- let g = unsafe { i.as_chunks_unchecked::<{ SIZE + 1 }>() };
- let start = memchr::memchr(b'S', i).ψ();
- let (y, x) = (start / (SIZE + 1), start % (SIZE + 1));
- let mut cost = [[0; SIZE]; SIZE];
- let base = pathfinding::directed::bfs::bfs(
- &(x, y),
- |&p| {
- [Dir::N + p, Dir::E + p, Dir::S + p, Dir::W + p]
+#[rustfmt::skip]
+fn numpad(x: u8) -> (usize, usize) {
+ match x {
+ b'7' => (0, 0), b'8' => (1, 0), b'9' => (2, 0),
+ b'4' => (0, 1), b'5' => (1, 1), b'6' => (2, 1),
+ b'1' => (0, 2), b'2' => (1, 2), b'3' => (2, 2),
+ b'0' => (1, 3), b'A' => (2, 3),
+ _ => unreachable!(),
+ }
+}
+#[rustfmt::skip]
+fn dpad(x: u8) -> (usize, usize) {
+ match x {
+ b'^' => (1, 0), b'A' => (2, 0),
+ b'<' => (0, 1), b'v' => (1, 1), b'>' => (2, 1),
+ _ => unreachable!(),
+ }
+}
+
+fn pathfind<const N: usize, const M: usize>(
+ input: impl IntoIterator<Item = (u8, (usize, usize))>,
+ grid: [[u8; N]; M],
+) -> Vec<Vec<u8>> {
+ let mut ways = HashSet::<Vec<u8>>::default();
+ for ((code, start), first) in input
+ .into_iter()
+ .zip(std::iter::once(true).chain(std::iter::repeat(false)))
+ {
+ let current = pathfinding::directed::astar::astar_bag(
+ &(start, code, b'.'),
+ |&(p, at, _)| {
+ [
+ (Dir::N + p, b'^'),
+ (Dir::E + p, b'>'),
+ (Dir::S + p, b'v'),
+ (Dir::W + p, b'<'),
+ ]
.into_iter()
- .filter(|&(x, y)| g[y][x] != b'#')
- },
- |&(x, y)| g[y][x] == b'E',
- )
- .unwrap();
- let n = base.len() as u32;
- for (&(x, y), i) in base.iter().ι::<u32>() {
- cost[y][x] = i;
+ .filter(|&((x, y), _)| matches!(grid.get(y).map(|y| y.get(x)), Some(Some(_))))
+ .map(move |(p, dir)| ((p, at, dir), 1))
+ },
+ |_| 0,
+ |&((x, y), at, _)| grid.get(y).map(|y| y.get(x)) == Some(Some(&at)),
+ )
+ .ψ()
+ .0
+ .into_iter()
+ .map(|x| {
+ x.into_iter()
+ .skip(1)
+ .map(|x| x.2)
+ .chain(once(b'A'))
+ .collect_vec()
+ })
+ .collect_vec();
+
+ if first {
+ ways.extend(current);
+ } else {
+ ways = ways
+ .into_iter()
+ .flat_map(|x| {
+ current.iter().map(move |way| {
+ let mut x = x.clone();
+ x.extend(way);
+ x
+ })
+ })
+ .collect();
+ }
}
- let dst = n - 1;
- // use rayon::prelude::*;
- base.into_iter()
- .filter(|&(x, y)| g[y][x] != b'#')
- // .par_bridge()
- .filter_map(|(x, y)| {
- for (y_offset, x_offset) in include!("../offsets") {
- let (x2, y2) = (
- (x as i32 + x_offset) as usize,
- (y as i32 + y_offset) as usize,
- );
- if x2 < SIZE
- && y2 < SIZE
- && ((cost[y][x] + n - cost[y2][x2] - 1
- + x_offset.abs() as u32
- + y_offset.abs() as u32)
- + 100)
- <= dst
- {
- return Some(());
+
+ ways.into_iter().collect_vec()
+}
+
+fn num(code: [u8; 4]) -> Vec<Vec<u8>> {
+ #[rustfmt::skip]
+ let grid = [
+ [b'7',b'8',b'9'],
+ [b'4',b'5',b'6'],
+ [b'1',b'2',b'3'],
+ [0 , b'0',b'A'],
+ ];
+ 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 = [
+ [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)
+}
+
+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)
+}
+
+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());
+ 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);
+ }
}
}
- None
+ dbg!(complex);
+ complex
})
- .count()
+ .sum::<usize>()
}
fn main() {