I used Rust for day 16.
Parsing
We have a grid to parse. For this we create a struct to represent each row, col coordinate and an enum to represent the value at each point on the grid. We split into lines and then into chars, while using the enumerate iterator method to get the index at each step for the row and column coordinates, and finally collect into a hashmap.
fn parse_input(input: String) -> HashMap<Point, GridValue> {
input
.trim()
.lines()
.enumerate()
.flat_map(|(row, line)| {
line.chars().enumerate().map(move |(col, ch)| {
(Point::new(row as i32, col as i32), GridValue::from_char(ch))
})
})
.collect()
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct Point {
row: i32,
col: i32,
}
impl Point {
fn new(row: i32, col: i32) -> Self {
Point { row, col }
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
enum GridValue {
Start,
End,
Blank,
Wall,
}
impl GridValue {
fn from_char(ch: char) -> Self {
match ch {
'#' => Self::Wall,
'S' => Self::Start,
'E' => Self::End,
'.' => Self::Blank,
other @ _ => panic!("Invalid character {}", other),
}
}
}Part One
Our grid is a maze with a scoring system when travelling through it. There is a start point and an end point marked on the maze. We need to find out the lowest score for going from the start point to the end point. The scoring system is somewhat interesting, with a cost of 1 point to go forward one unit in the current direction and a cost of 1000 points to turn in place 90 degrees. We start out facing in the east direction.
This is a textbook example of using Dijkstra’s algorithm. We have a graph (in the form of a grid) and need to find the shortest path through it. An excellent explanation with interactive visualizations of Dijkstra’s algorithm can be found at this page.
We create an enum to represent the 4 cardinal directions and add a method on our Point struct to get the next point given a direction. We also add a method on the Direction enum to get the directions we can turn to given our current direction.
impl Point {
fn next(self, direction: Direction) -> Self {
match direction {
Direction::North => Point {
row: self.row - 1,
col: self.col,
},
Direction::South => Point {
row: self.row + 1,
col: self.col,
},
Direction::East => Point {
row: self.row,
col: self.col + 1,
},
Direction::West => Point {
row: self.row,
col: self.col - 1,
},
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
enum Direction {
North,
South,
East,
West,
}
impl Direction {
fn turns(self) -> [Self; 2] {
match self {
Direction::North | Direction::South => [Direction::East, Direction::West],
Direction::East | Direction::West => [Direction::South, Direction::North],
}
}
}
impl Default for Direction {
fn default() -> Self {
Direction::East
}
}There are two issues with directly using a (cost, data) tuple for the state to put in our Dijkstra’s priority queue. The first is that Rust’s BinaryHeap is a max-heap by default but we need a min-heap for our priority queue. The second is that our data would have to implement the Ord trait which doesn’t really make sense for points and is inconvenient to do. To deal with these, a PqState struct is created which impls Ord based on the reverse order of its cost field. The rest of the solution is a basic Dijkstra’s algorithm implementation. The nodes of the graph are (point, direction) tuples and each node has three neighbors: the next point with the same direction and the same point with two different directions that we can turn to.
fn part1(parsed: &HashMap<Point, GridValue>) -> u32 {
let start_point = parsed
.iter()
.find(|(_point, val)| val == &&GridValue::Start)
.expect("No start position in input")
.0
.clone();
let end_point = parsed
.iter()
.find(|(_point, val)| val == &&GridValue::End)
.expect("No end position in input")
.0
.clone();
let mut current_points = BinaryHeap::new();
let mut visited = HashSet::new();
current_points.push(PqState {
cost: 0,
inner: (start_point, Direction::default()),
});
while let Some(PqState {
cost: current_cost,
inner: (current_point, current_direction),
}) = current_points.pop()
{
if current_point == end_point {
return current_cost;
}
visited.insert((current_point, current_direction));
let next_point = current_point.next(current_direction);
if let Some(&next_value) = parsed.get(&next_point) {
if next_value != GridValue::Wall && !visited.contains(&(next_point, current_direction))
{
current_points.push(PqState {
cost: current_cost + 1,
inner: (next_point, current_direction),
});
}
}
for next_direction in current_direction.turns().iter().copied() {
if !visited.contains(&(current_point, next_direction)) {
current_points.push(PqState {
cost: current_cost + 1000,
inner: (current_point, next_direction),
});
}
}
}
0
}
#[derive(Debug, Clone)]
struct PqState<T> {
cost: u32,
inner: T,
}
impl<T> Ord for PqState<T> {
fn cmp(&self, other: &Self) -> cmp::Ordering {
self.cost.cmp(&other.cost).reverse()
}
}
impl<T> PartialOrd for PqState<T> {
fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
Some(self.cmp(other))
}
}
impl<T> PartialEq for PqState<T> {
fn eq(&self, other: &Self) -> bool {
return self.cost == other.cost;
}
}
impl<T> Eq for PqState<T> {}Part Two
Now we need to find the number of points that lie on the lowest-score paths from the start point to the end point. Since there can be multiple paths with the same lowest-score, we now need to continue searching even after finding the end point once. We also care about the path between the start and the end instead of just the cost of the path now. All this requires a few small changes to our code.
First, we store the path leading to a point in our priority queue instead of just the point. Second, when we reach the end point, instead of returning the path cost, we update a BTreeMap with the points along the path. This map is keyed on the cost to reach the end. Finally, to get the answer, we get the length of the set of points corresponding to the the lowest cost of reaching the end.
fn part2(parsed: &HashMap<Point, GridValue>) -> usize {
let start_point = parsed
.iter()
.find(|(_point, val)| val == &&GridValue::Start)
.expect("No start position in input")
.0
.clone();
let end_point = parsed
.iter()
.find(|(_point, val)| val == &&GridValue::End)
.expect("No end position in input")
.0
.clone();
let mut current_points = BinaryHeap::new();
let mut visited = HashSet::new();
current_points.push(PqState {
cost: 0,
inner: (vec![start_point], Direction::default()),
});
let mut spots: BTreeMap<u32, HashSet<Point>> = BTreeMap::new();
while let Some(PqState {
cost: current_cost,
inner: (current_path, current_direction),
}) = current_points.pop()
{
let current_point = current_path.last().copied().unwrap();
if current_point == end_point {
spots.entry(current_cost).or_default().extend(current_path);
continue;
}
visited.insert((current_point, current_direction));
let next_point = current_point.next(current_direction);
if let Some(&next_value) = parsed.get(&next_point) {
if next_value != GridValue::Wall && !visited.contains(&(next_point, current_direction))
{
let mut next_path = current_path.clone();
next_path.push(next_point);
current_points.push(PqState {
cost: current_cost + 1,
inner: (next_path, current_direction),
});
}
}
for next_direction in current_direction.turns().iter().copied() {
if !visited.contains(&(current_point, next_direction)) {
current_points.push(PqState {
cost: current_cost + 1000,
inner: (current_path.clone(), next_direction),
});
}
}
}
spots.pop_first().unwrap().1.len()
}