To reach the elves a heightmap of the surrounding area is scanned on the handheld device.
The goal is to reach the highest position (E) on the map from the starting point (S).
Each square on the grid has an elevation level, where a move from one square to a neighboring square
is only allowed when either the target level is lower or at max one level higher.
Movement is restricted to one of the four neighboring squares, left, right, above or below from the current one.
Levels are given in a range of a (lowest) and z (highest).
The start square is on the lowest level a, while the end square has the highest level z.
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
Assuming the grid starts at 0,0 in the upper left corner, the start square S has level a.
To reach the end square E there are number of possible ways to go, but eventually the path
spirals around until E is hit.
v..v<<<<
>v.vv<<^
.>vv>E^^
..v>>>^^
..>>>>>^
The example above marks the way to find the end square in 31 steps.
Part 1
The goal is to find the shortest possible path from S to E in the given map of elevation levels.
This challenge is a good place to introduce a new crate. There are a few excellent crates available to handle graph problems, e.g. finding the shortest path in a graph, by applying different algorithms. Of course it's also possible to implement one of the existing algorithms on our own.
To start things the given input is parsed into a Grid struct that contains all squares, the Pos struct from
earlier challenges are the coordinates into the Grid.
#[derive(Debug, Hash, PartialEq, Eq, Copy, Clone, PartialOrd)]
struct Pos {
x: i32,
y: i32,
}
impl Pos {
pub const fn new(x: i32, y: i32) -> Self {
Self { x, y }
}
}
struct Grid {
start: Pos,
end: Pos,
squares: Vec<char>,
width: usize,
height: usize,
}
impl Grid {
pub fn new() -> Self {
Self {
squares: Vec::new(),
start: Pos::new(0, 0),
end: Pos::new(0, 0),
width: 0,
height: 0,
}
}
pub fn add_line(mut self, row: impl Iterator<Item = char>) -> Self {
let mut row = row.collect::<Vec<_>>();
self.width = row.len();
if let Some(index) = row.iter().position(|&c| c == 'S') {
self.start = Pos::new(index as i32, self.height as i32);
row[index] = 'a';
};
if let Some(index) = row.iter().position(|&c| c == 'E') {
self.end = Pos::new(index as i32, self.height as i32);
row[index] = 'z';
}
self.squares.append(&mut row);
self.height += 1;
self
}
}
fn part1(grid: &Grid) -> u32 {
todo!()
}
fn parse(input: &str) -> Grid {
input
.lines()
.map(str::trim)
.filter(|line| !line.is_empty())
.fold(Grid::new(), |grid, line| grid.add_line(line.chars()))
}
fn main() {
let grid = parse(include_str!("input.txt"));
println!("Part 1: {}", part1(&grid));
}
#[cfg(test)]
mod tests {
use super::*;
const INPUT: &str = r#"
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
"#;
#[test]
fn check_part1() {
assert_eq!(31, part1(&parse(INPUT)));
}
}
The parse function builds the Grid struct by adding line by line, it forwards an iterator of char to the
Grid#add_line method, which appends each row & determines the start and end position inside the grid.
The start (S) & end (E) squares are replaced with their associated levels a & z.
The fields width & height are the dimensions of the Grid, they are used later to index
into the 1-dimensional Vec of squares.
The single test currently fails as the part1 function is not implemented yet.
Time to pick an appropriate crate to handle the pathfinding for us instead of implementing it ourselves. One option is the petgraph
crate that is a graph data structure library to build different types of graph. It also supports a set of different path algorithms.
Instead of using petgraph we add the pathfinding crate to the dependencies in the Cargo.toml. Or alternatively install the crate via
cargo add pathfinding
This library supports a number of different directed graph algorithms which are quite easy to initialize. There are different
algorithms to pick from, let's try dijkstra
using the Dijkstra's Search Algorithm that finds the shortest path between
two nodes in a weighted graph.
The function signature of pathfinding::directed::dijkstra::dijkstra looks like:
pub fn dijkstra<N, C, FN, IN, FS>(
start: &N,
successors: FN,
success: FS
) -> Option<(Vec<N>, C)>
where
//..
{
// ..
}
The function takes a number of trait types to define what can be passed into the function. For further details please check the documentation. The parameters for the function are, a start node, a lambda or function to determine all successors for a given node (for the traversal) and the end node as third parameter.
From the input the start and end squares are known. What is missing is the function to determine all successor nodes which determine
the nodes that are directly accessible from a given node. The successor function expects weights as well, but as there are no weights
we pass in the value of 1. The function returns Option<(Vec<N>, C)> where N in our case will be Pos, while C is a u32.
Using a weight of 1 results in the nice property that the total weight is the length of the found path.
The parts that are missing is to determine what the neighboring squares that can be moved to are. We know it's possible to move
from one square to another when the target square has a lower elevation level, but it's only allowed to move one elevation level up, e.g. from a to b, but not from b to d. Initially I made a mistake to check when given two levels if it's possible to move from one to the other.
After some trial & a number of useful tests I came up with the following helper function.
fn can_move(l: char, r: char) -> bool {
let (l, r) = (l as i32, r as i32);
(l - r).abs() <= 1 || l > r
}
which is the heart of it all. The function returns true if it's possible to move from elevation l to r.
A few more helper methods are necessary to prepare the algorithm, one is to get all neighbor squares from a given square, the other is to get the elevation level for a position.
impl Grid {
const DIRECTIONS: [Pos; 4] = [
Pos::new(1, 0), // right
Pos::new(0, 1), // down
Pos::new(-1, 0), // left
Pos::new(0, -1), // up
];
fn neighbors(&self, pos: Pos) -> Vec<Pos> {
Self::DIRECTIONS
.iter()
.map(|dir| pos + *dir)
.filter(|neighbor| self.get(neighbor).is_some())
.collect_vec()
}
fn get(&self, &Pos { x, y }: &Pos) -> Option<char> {
if 0 <= x && x < self.width as i32 && 0 <= y && y < self.height as i32 {
Some(self.squares[(y * self.width as i32 + x) as usize])
} else {
None
}
}
}
The neighbors method only returns neighboring squares that exist on the grid.
Now there is everything set up to implement the path finding algorithm using dijkstra.
impl Grid {
pub fn find_shortest_path(&self, start: &Pos) -> Option<u32> {
let result = dijkstra::dijkstra(
start,
|&pos| {
let height = self.get(&pos).expect("Failed to get height");
self.neighbors(pos)
.iter()
.filter(|neighbor| can_move(height, self.get(neighbor).unwrap()))
.map(|neighbor| (*neighbor, 1))
.collect_vec()
},
|&p| p == self.end,
);
result.map(|(_path, length)| length)
}
}
fn part1(grid: &Grid) -> u32 {
grid.find_shortest_path(&grid.start).unwrap()
}
The first parameter to the dijkstra function is the start position. The second parameter is a closure that
gets the height of the current position, then determines which neighboring squares can be reached from it by checking
the elevation levels. The last parameter is the end position.
The test should pass and running the program should output the first solution.
Part 2
Instead of using the current start position the elves surely would like to know which is the most scenic hiking trail
The best scenic route is a path from one of the squares with elevation level a to the end position. The trail
should still be direct, taking the fewest steps required to reach the end. The goal is to find the best starting position
on a square with elevation level a that results overall in the shortest path.
Instead of checking the current path, the list of all squares is determined first that have an elevation level a. Then
for each start position the shortest path is determined, finally the shortest number of steps overall is then returned as
the second solution. The given example input results in a scenic path of length 29.
impl Grid {
pub fn find_scenic_path(&self) -> Vec<u32> {
todo!()
}
}
fn part2(grid: &Grid) -> u32 {
let result = grid.find_scenic_path();
*result.iter().min().expect("Failed to get length")
}
fn main() {
let grid = parse(include_str!("input.txt"));
println!("Part 1: {}", part1(&grid));
println!("Part 2: {}", part2(&grid));
}
#[cfg(test)]
mod tests {
// ..
#[test]
fn check_part2() {
assert_eq!(29, part2(&parse(INPUT)));
}
}
Last thing to implement is method Grid#find_scenic_path that returns a list of lengths for all shortest paths.
impl Grid {
pub fn find_scenic_path(&self) -> Vec<u32> {
let scenic_spots = (0..self.width as i32)
.cartesian_product(0..self.height as i32)
.filter(|(x, y)| self.squares[(y * self.width as i32 + x) as usize] == 'a')
.collect::<Vec<_>>();
scenic_spots
.iter()
.filter_map(|&(x, y)| self.find_shortest_path(&Pos::new(x, y)))
.collect()
}
}
The method find_scenic_path uses Itertools#cartesian_product to generate of all grid coordinates. The variable scenic_spots consists of all squares with elevation level a.
These are the starting points for which the shortest paths will be determined.
The second part iterates over all these starting positions and determines their shortest path, reusing find_shortest_path method.
We are not necessarily interested in the paths itself, only in their lengths.
Once returned function part2 finds the min value of this list, which is the overall shortest path & therefore the best scenic route.
All tests should pass now, running the program again should also give the second solution. Voila.