105 lines
2.5 KiB
Rust
105 lines
2.5 KiB
Rust
#![feature(test)]
|
|
|
|
use std::collections::VecDeque;
|
|
|
|
#[derive(Clone, PartialEq, Eq)]
|
|
struct Position {
|
|
x: usize,
|
|
y: usize,
|
|
}
|
|
|
|
impl Position {
|
|
fn neighbors(&self) -> Vec<Position> {
|
|
[(1, 2), (1, 0), (2, 1), (0, 1)]
|
|
.into_iter()
|
|
.filter(|&(dx, dy)| self.x + dx > 0 && self.y + dy > 0)
|
|
.map(|(dx, dy)| Position {
|
|
x: self.x + dx - 1,
|
|
y: self.y + dy - 1,
|
|
})
|
|
.collect()
|
|
}
|
|
}
|
|
|
|
struct Input {
|
|
start: Position,
|
|
end: Position,
|
|
grid: Vec<Vec<u8>>,
|
|
}
|
|
|
|
fn setup(input: &str) -> Input {
|
|
let mut grid = Vec::new();
|
|
let mut start = None;
|
|
let mut end = None;
|
|
for (i, line) in input.trim().lines().enumerate() {
|
|
let mut row = Vec::new();
|
|
for (j, c) in line.bytes().enumerate() {
|
|
let c = match c {
|
|
b'S' => {
|
|
start = Some(Position { x: j, y: i });
|
|
0
|
|
}
|
|
b'E' => {
|
|
end = Some(Position { x: j, y: i });
|
|
25
|
|
}
|
|
_ => c - b'a',
|
|
};
|
|
row.push(c);
|
|
}
|
|
grid.push(row);
|
|
}
|
|
Input {
|
|
start: start.unwrap(),
|
|
end: end.unwrap(),
|
|
grid,
|
|
}
|
|
}
|
|
|
|
fn bfs(
|
|
start: Position,
|
|
grid: &[&[u8]],
|
|
target: impl Fn(&Position) -> bool,
|
|
step: impl Fn(&Position, &Position) -> bool,
|
|
) -> u32 {
|
|
let mut queue = VecDeque::from([(0, start)]);
|
|
let mut visited = vec![vec![false; grid[0].len()]; grid.len()];
|
|
while let Some((d, p)) = queue.pop_front() {
|
|
if target(&p) {
|
|
return d;
|
|
}
|
|
if visited[p.y][p.x] {
|
|
continue;
|
|
}
|
|
visited[p.y][p.x] = true;
|
|
for q in p.neighbors() {
|
|
if grid.get(q.y).and_then(|r| r.get(q.x)).is_some()
|
|
&& step(&p, &q)
|
|
&& !visited[q.y][q.x]
|
|
{
|
|
queue.push_back((d + 1, q));
|
|
}
|
|
}
|
|
}
|
|
panic!()
|
|
}
|
|
|
|
fn part1(Input { start, end, grid }: &Input) -> u32 {
|
|
bfs(
|
|
start.clone(),
|
|
&grid.iter().map(|x| &x[..]).collect::<Vec<_>>()[..],
|
|
|pos| pos == end,
|
|
|from, to| grid[to.y][to.x] <= grid[from.y][from.x] + 1,
|
|
)
|
|
}
|
|
|
|
fn part2(Input { end, grid, .. }: &Input) -> u32 {
|
|
bfs(
|
|
end.clone(),
|
|
&grid.iter().map(|x| &x[..]).collect::<Vec<_>>()[..],
|
|
|pos| grid[pos.y][pos.x] == 0,
|
|
|from, to| grid[from.y][from.x] <= grid[to.y][to.x] + 1,
|
|
)
|
|
}
|
|
|
|
aoc::main!(2022, 12, ex: 1);
|