DEV Community

Nicky Meuleman

Posted on • Originally published at nickymeuleman.netlify.app

Advent of Code 2022 Day 12

Day 12: Hill Climbing Algorithm

TL;DR: my solution in Rust

You want to get to a higher spot so your communication device gets better reception.

Today's input is a height map of the surrounding area.
Again, it's a perfect 2D grid of positions.

Each position has an elevation from "a" to "z".
"a" being the lowest and "z" the highest.

You start at the position marked "S".
It has an elevation of "a".

You want to go to the position marked "E".
It has an elevation of "z".

An example input looks like this:

``````Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
``````

During each step, you can move exactly one square up, down, left, or right.

You can only go up one height per step.
So from "a" to "b" is possible.
But going from "a" to "c" is not.

You can go down as many heights as you want. (I guess you are wearing long fall boots from Portal.
So going from "y" to "a" is a perfectly valid move.

Parsing

I decided to extract a couple things from the input:

• The height map, with numbers from 0-25 instead of letters.
• The coordinates for the start (marked "S")
• The coordinates for the end (marked "E")
• The width of the map
• The height of the map

I used a list of lists to store every height.

• Each item in the outer list is a row.
• Each item in a row is a height.

I used a `Coord` struct again to store coordinates.

``````struct Coord {
x: usize,
y: usize,
}
``````

I use the good 'ol double for loop to loop over each letter in the map.

When I encounter an "S".

• I set its height to "a".
• I set the `start` coordinate.

When I encounter an "E".

• I set its height to "z".
• I set the `end` coordinate.

I turn the height letter into a height number by using the ASCII values again. (as in multiple previous days)
That number gets stored in the height map at the corrent row and column index.

``````fn parse() -> (Coord, Coord, Vec<Vec<u8>>, usize, usize) {
let rows = input.lines().count();
let cols = input.lines().next().unwrap().len();
let mut map = vec![vec![0; cols]; rows];
let mut start = Coord { x: 0, y: 0 };
let mut end = Coord { x: 0, y: 0 };

for (row, line) in input.lines().enumerate() {
for (col, c) in line.chars().enumerate() {
let letter = match c {
'S' => {
start.x = col;
start.y = row;
'a'
}
'E' => {
end.x = col;
end.y = row;
'z'
}
'a'..='z' => c,
_ => panic!("Invalid input"),
};

let val = letter as u8 - b'a';
map[row][col] = val;
}
}

(start, end, map, rows, cols)
}
``````

Part 1

The question asks for the fewest steps required to "E" if starting from "S".

Aha, a shortest path problem!
Time to bring out our good friend Dijkstra.

• The start position is `start`.
• The goal position is `end`.
• Per step, the cost increases by 1.

It never makes sense to visit a location twice, you could have stepped in the correct direction the first time.
That's why I also keep track of coordinates the algoritm visited in a set, and only examine new coordinates.

in pseudocode:

``````let mut pq = priority_queue;
let mut visited = set;

while node = pq.pop() {
// if goal is reached, return

// get all next coordinates that fit the rules
for candidate in candidates {
if seen.includes(candidate) {
// do not visit nodes twice
} else {
// insert new node into priority_queue
}
}
}
``````

Helpers

To make it a bit more readable I'll define a few helpers again.
To get all neighbours of a current position given the width and the height of the map:

``````impl Coord {
fn neighbours(&self, rows: usize, cols: usize) -> Vec<Self> {
let mut result = Vec::new();

// up
if self.y > 0 {
result.push(Self {
x: self.x,
y: self.y - 1,
});
}
// down
if self.y < rows - 1 {
result.push(Self {
x: self.x,
y: self.y + 1,
});
}
// left
if self.x > 0 {
result.push(Self {
x: self.x - 1,
y: self.y,
});
}
// right
if self.x < cols - 1 {
result.push(Self {
x: self.x + 1,
y: self.y,
});
}

result
}
}
``````

This doesn't care about the height at a coordinate, only that a coordinate exists on our map!

I also created a `Node` struct that will be the thing we insert into our priority queue.
It has a cost, and a coordinate.

``````struct Node {
cost: u32,
coord: Coord,
}
``````

The priority queue has to be ordered so the thing with the lowest cost gets popped first, so I implement `Ord` to get that behaviour.

``````impl Ord for Node {
fn cmp(&self, other: &Self) -> Ordering {
other.cost.cmp(&self.cost)
}
}

impl PartialOrd for Node {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
``````

Because this comes with a few other requirements (being able to compare `Node`, and because I plan on inserting a node into a set, I derive some traits on `Coord` and `Node`.

They're both small, so I derive `Copy` while I'm at it.

``````#[derive(PartialEq, Eq, Hash, Clone, Copy)]
struct Coord {
x: usize,
y: usize,
}

#[derive(PartialEq, Eq, Clone, Copy)]
struct Node {
cost: u32,
coord: Coord,
}
``````

Before looping over candidates in the algorithm, I calculate all neighbours.
Then, I filter those and only keep the ones that satisfy the rules.

``````let curr_height = map[coord.y][coord.x];
let neighbours = coord.neighbours(rows, cols);
let candidates: Vec<_> = neighbours
.iter()
.filter(|coord| {
let height = map[coord.y][coord.x];
height <= curr_height || height == curr_height + 1
})
.collect();
``````

Filling in the skeleton code gives the answer to part1.
A node at position `end` eventually gets popped off the priority queue.
At that point, we can be certain this node has the lowest cost to reach that coordinate.

Final code

``````pub fn part_1() -> u32 {
let (start, end, map, rows, cols) = parse();
let mut pq = BinaryHeap::new();
let mut visited = HashSet::new();

pq.push(Node {
cost: 0,
coord: start,
});
visited.insert(start);

while let Some(Node { coord, cost }) = pq.pop() {
if coord == end {
return cost;
}

let curr_height = map[coord.y][coord.x];
let neighbours = coord.neighbours(rows, cols);
let candidates: Vec<_> = neighbours
.iter()
.filter(|coord| {
let height = map[coord.y][coord.x];
height <= curr_height || height == curr_height + 1
})
.collect();

for candidate in candidates {
if visited.insert(*candidate) {
pq.push(Node {
cost: cost + 1,
coord: *candidate,
})
}
}
}

panic!("No path found");
}
``````

Part 2

The question asks for the fewest steps required to reach "E" if starting from any "a".

To do this, I flipped the logic from part 1, and adjusted the rules.

The parameters for the Dijkstra algorithm are now:

• The start position is `end`.
• The goal position is any `a`.
• Per step, the cost increases by 1.

The rules from the initial problem also invert!

• You can only go down one height per step.
• You can go up as many heights as you want.

Translated into code, our `return` condition changes, and the spot we `filter` neighbours to apply the rules changes.

Making those changes, and boom, that's part2!

Final code

``````pub fn part_2() -> u32 {
let (start, end, map, rows, cols) = parse();
let mut pq = BinaryHeap::new();
let mut visited = HashSet::new();

pq.push(Node {
cost: 0,
coord: end,
});
visited.insert(start);

while let Some(Node { coord, cost }) = pq.pop() {
let curr_height = map[coord.y][coord.x];

if curr_height == 0 {
return cost;
}

let neighbours = coord.neighbours(rows, cols);
let candidates: Vec<_> = neighbours
.iter()
.filter(|coord| {
let height = map[coord.y][coord.x];
height >= curr_height || height == curr_height - 1
})
.collect();

for candidate in candidates {
if visited.insert(*candidate) {
pq.push(Node {
cost: cost + 1,
coord: *candidate,
})
}
}
}

panic!("No path found");
}
``````

Final code

``````use std::{
cmp::Ordering,
collections::{BinaryHeap, HashSet},
};

#[derive(PartialEq, Eq, Hash, Clone, Copy)]
struct Coord {
x: usize,
y: usize,
}

#[derive(PartialEq, Eq, Clone, Copy)]
struct Node {
cost: u32,
coord: Coord,
}

impl Ord for Node {
fn cmp(&self, other: &Self) -> Ordering {
other.cost.cmp(&self.cost)
}
}

impl PartialOrd for Node {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}

impl Coord {
fn neighbours(&self, rows: usize, cols: usize) -> Vec<Self> {
let mut result = Vec::new();

// up
if self.y > 0 {
result.push(Self {
x: self.x,
y: self.y - 1,
});
}
// down
if self.y < rows - 1 {
result.push(Self {
x: self.x,
y: self.y + 1,
});
}
// left
if self.x > 0 {
result.push(Self {
x: self.x - 1,
y: self.y,
});
}
// right
if self.x < cols - 1 {
result.push(Self {
x: self.x + 1,
y: self.y,
});
}

result
}
}

fn parse() -> (Coord, Coord, Vec<Vec<u8>>, usize, usize) {
let rows = input.lines().count();
let cols = input.lines().next().unwrap().len();
let mut map = vec![vec![0; cols]; rows];
let mut start = Coord { x: 0, y: 0 };
let mut end = Coord { x: 0, y: 0 };

for (row, line) in input.lines().enumerate() {
for (col, c) in line.chars().enumerate() {
let letter = match c {
'S' => {
start.x = col;
start.y = row;
'a'
}
'E' => {
end.x = col;
end.y = row;
'z'
}
'a'..='z' => c,
_ => panic!("Invalid input"),
};

let val = letter as u8 - b'a';
map[row][col] = val;
}
}

(start, end, map, rows, cols)
}

pub fn part_1() -> u32 {
let (start, end, map, rows, cols) = parse();
let mut pq = BinaryHeap::new();
let mut visited = HashSet::new();

pq.push(Node {
cost: 0,
coord: start,
});
visited.insert(start);

while let Some(Node { coord, cost }) = pq.pop() {
if coord == end {
return cost;
}

let curr_height = map[coord.y][coord.x];
let neighbours = coord.neighbours(rows, cols);
let candidates: Vec<_> = neighbours
.iter()
.filter(|coord| {
let height = map[coord.y][coord.x];
height <= curr_height || height == curr_height + 1
})
.collect();

for candidate in candidates {
if visited.insert(*candidate) {
pq.push(Node {
cost: cost + 1,
coord: *candidate,
})
}
}
}

u32::MAX
}

pub fn part_2() -> u32 {
let (start, end, map, rows, cols) = parse();
let mut pq = BinaryHeap::new();
let mut visited = HashSet::new();

pq.push(Node {
cost: 0,
coord: end,
});
visited.insert(start);

while let Some(Node { coord, cost }) = pq.pop() {
let curr_height = map[coord.y][coord.x];

if curr_height == 0 {
return cost;
}

let neighbours = coord.neighbours(rows, cols);
let candidates: Vec<_> = neighbours
.iter()
.filter(|coord| {
let height = map[coord.y][coord.x];
height >= curr_height || height == curr_height - 1
})
.collect();

for candidate in candidates {
if visited.insert(*candidate) {
pq.push(Node {
cost: cost + 1,
coord: *candidate,
})
}
}
}

u32::MAX
}
``````

M Algah Fattah Illahi

Nice solution!
I am curious, how long does it take to run the solution with the actual input?

Nicky Meuleman • Edited

Just tested it, with `Instant::now()` so no rigorous benchmark.

``````Part 1: 370                 (took: 701.5µs)
Part 2: 363                 (took: 480.4µs)
``````

On a core i5 6600K with a bunch of programs open (VSCode, Steam, Chrome, Discord, ...).