heh
hmm
| -rw-r--r-- | src/main.rs | 93 | ||||
| -rw-r--r-- | src/util.rs | 39 |
2 files changed, 82 insertions, 50 deletions
diff --git a/src/main.rs b/src/main.rs index 22e07cc..2d8ed86 100644 --- a/src/main.rs +++ b/src/main.rs @@ -18,54 +18,59 @@ extern crate test; pub mod util; pub use util::prelude::*; -// const MUST: i16 = 3; -// const NEEDS: i16 = 0; -const MUST: i16 = 10; -const NEEDS: i16 = 4; +// const MUST: u8 = 3; +// const NEEDS: u8 = 0; +const MUST: u8 = 10; +const NEEDS: u8 = 4; -pub fn run(i: &str) -> impl Display { - let v = i.行().collect_vec(); - let g = util::LMap::new(|(x, y, δx, δy, gone): (i16, i16, i16, i16, i16)| { - Some( - [ - Dir::W + (x, y), - Dir::E + (x, y), - Dir::N + (x, y), - Dir::S + (x, y), - ] - .iter() - .filter_map(|&(nx, ny)| { - let ngon; - let nδx = nx - x; - let nδy = ny - y; - if nδx == δx && nδy == δy { - if gone == MUST { - return None; - } - ngon = gone + 1; - } else if (nδx == -δx && nδx != 0) || (nδy == -δy && nδy != 0) { - return None; - } else { - if gone < NEEDS { - return None; - } - ngon = 1; - } - (nx >= 0 && nx < v[0].len() as i16 && ny >= 0 && ny < v.len() as i16).then(|| { - ( - (nx, ny, nδx, nδy, ngon), - (v[ny as usize][nx as usize] - b'0') as u32, - ) - }) - }) - .collect_vec(), - ) - }); - util::dijkstra(g, (0i16, 0i16, 0i16, 0i16, NEEDS), |(x, y, _, _, g)| { - x == v[0].len() as i16 - 1 && y == v.len() as i16 - 1 && g >= NEEDS +fn neighbor( + (x, y, δx, δy, gone): (u8, u8, i8, i8, u8), + v: &[[u8; 142]; 141], +) -> impl Iterator<Item = ((u8, u8, i8, i8, u8), u16)> + '_ { + [ + Dir::W + (x, y), + Dir::E + (x, y), + Dir::N + (x, y), + Dir::S + (x, y), + ] + .into_iter() + .flatten() + .filter(|&(x, _)| x < 141) + .filter(|&(_, y)| y < 141) + .filter_map(move |(nx, ny)| { + let go; + let nδx = (nx as i16 - x as i16) as i8; + let nδy = (ny as i16 - y as i16) as i8; + if nδx == δx && nδy == δy { + if gone == MUST { + return None; + } + go = gone + 1; + } else if (nδx == -δx && nδx != 0) || (nδy == -δy && nδy != 0) { + return None; + } else { + if gone < NEEDS { + return None; + } + go = 1; + } + + Some(( + (nx, ny, nδx, nδy, go), + (C! { v[ny as usize][nx as usize] } - b'0') as u16, + )) }) } +pub fn run(i: &str) -> impl Display { + let v = unsafe { &*(i.as_bytes().as_ptr() as *const [[u8; 142]; 141]) }; + util::dijkstra( + |n| neighbor(n, v), + (0u8, 0u8, 0i8, 0i8, NEEDS), + |(x, y, _, _, g)| x == 140 && y == 140 && g >= NEEDS, + ) +} + fn main() { let i = include_str!("inp.txt").trim(); println!("{}", run(i)); diff --git a/src/util.rs b/src/util.rs index 790fc4e..e4b1f1b 100644 --- a/src/util.rs +++ b/src/util.rs @@ -198,11 +198,37 @@ where } } -pub fn dijkstra<N: Debug + Eq + Hash + Copy + Ord>( - mut graph: LMap<N, Vec<(N, u32)>, impl Fn(N) -> Option<Vec<(N, u32)>>>, +pub fn dijkstra_h<N: Debug + Eq + Hash + Copy + Ord, I: Iterator<Item = (N, u16)>>( + graph: impl Fn(N) -> I, start: N, end: impl Fn(N) -> bool, -) -> u32 { + h: impl Fn(N) -> u16, +) -> u16 { + let mut q = BinaryHeap::new(); + let mut s = HashSet::new(); + q.push(Reverse((h(start), 0, start))); + while let Some(Reverse((_, c, n))) = q.pop() { + if end(n) { + return c; + } + if !s.insert(n) { + continue; + } + for (n, d) in graph(n) { + if s.contains(&n) { + continue; + } + q.push(Reverse((h(n) + c + d, c + d, n))); + } + } + dang!() +} + +pub fn dijkstra<N: Debug + Eq + Hash + Copy + Ord, I: Iterator<Item = (N, u16)>>( + graph: impl Fn(N) -> I, + start: N, + end: impl Fn(N) -> bool, +) -> u16 { let mut q = BinaryHeap::new(); let mut s = HashSet::new(); q.push(Reverse((0, start))); @@ -213,15 +239,16 @@ pub fn dijkstra<N: Debug + Eq + Hash + Copy + Ord>( if !s.insert(n) { continue; } - for (n, d) in graph.get(n).α() { - if s.contains(n) { + for (n, d) in graph(n) { + if s.contains(&n) { continue; } - q.push(Reverse((c + *d, *n))); + q.push(Reverse((c + d, n))); } } dang!() } + impl std::ops::Add<(i16, i16)> for Dir { type Output = (i16, i16); fn add(self, (x, y): (i16, i16)) -> Self::Output { |