Thanks to my sponsors: Shane Lillie, David Barsky, Michael Mrozek, jatescher, Xirvik Servers, Marcin Kołodziej, Senyo Simpson, Yuriy Taraday, James Brown, Jean Manguy, Richard Pringle, Rufus Cable, Daniel Papp, Guy Waldman, Daniel Strittmatter, Jonathan Adams, Steven McGuire, Steven Pham, Marco Carmosino, Katie Janzen and 235 more
Day 12 (Advent of Code 2022)
Alright! The day 12 puzzle involves path finding, and it seems like a good time to lean more heavily on the WASM embeds I've set up for the previous parts.
Let's start by setting up the types we'll want!
Types and parsing
Our input is a heightmap, like so:
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
Where 'a'..='z'
is a square with a given elevation (from lowest to highest),
S
is the start, and E
is the end.
With that in mind, we can make a Cell
type like this:
#[derive(Clone, Copy)]
enum Cell {
// Start position
Start,
// End position
End,
// Square with given elevation
Square(u8),
}
The very next thing I want is a Grid<T>
type, and we'll tackle the parsing
there:
struct Grid {
width: usize,
height: usize,
data: Vec<Cell>,
}
impl Grid {
fn parse(input: &str) -> Self {
let first_line = input.lines().next().unwrap();
let width = first_line.len();
let height = input.lines().count();
let mut data = vec![];
for c in input.chars() {
let cell = match c {
'S' => Cell::Start,
'E' => Cell::End,
'a'..='z' => Cell::Square(c as u8 - b'a'),
'\r' | '\n' => continue,
_ => panic!("invalid character: {c}"),
};
data.push(cell);
}
Self {
width,
height,
data,
}
}
}
Like we did for day 8, let's make a GridCoord
type:
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
struct GridCoord {
x: usize,
y: usize,
}
impl From<(usize, usize)> for GridCoord {
fn from((x, y): (usize, usize)) -> Self {
Self { x, y }
}
}
Then some getters for Grid
:
impl Grid {
fn in_bounds(&self, coord: GridCoord) -> bool {
coord.x < self.width && coord.y < self.height
}
fn cell(&self, coord: GridCoord) -> Option<&Cell> {
if !self.in_bounds(coord) {
return None;
}
Some(&self.data[coord.y * self.width + coord.x])
}
fn cell_mut(&mut self, coord: GridCoord) -> Option<&mut Cell> {
if !self.in_bounds(coord) {
return None;
}
Some(&mut self.data[coord.y * self.width + coord.x])
}
}
Then a little Debug
impl just to make sure we parsed things correctly:
impl fmt::Debug for Grid {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
writeln!(f, "{}x{} grid:", self.width, self.height)?;
for y in 0..self.height {
for x in 0..self.width {
let cell = self.cell((x, y).into()).unwrap();
let c = match cell {
Cell::Start => 'S',
Cell::End => 'E',
Cell::Square(elevation) => (b'a' + elevation) as char,
};
write!(f, "{c}")?;
}
writeln!(f)?;
}
Ok(())
}
}
And then our main
function can start out its life as:
fn main() {
let grid = Grid::parse(include_str!("sample-input.txt"));
println!("{grid:?}");
}
And it seems okay:
$ cargo run --quiet
8x5 grid:
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
Visualizing the grid
Now that we do have the grid, I want to see it in a browser. This doesn't really help with solving the puzzle, it's just my way of having fun with it.
Just like in day 10, we're going to turn our application into a
"cdylib" library so we can build it to WebAssembly using wasm-pack
.
First:
$ cargo add wasm-bindgen@0.2
(cut)
We can now add wasm_bindgen
annotations on... Grid
for example!
use wasm_bindgen::prelude::*;
#[wasm_bindgen]
// 👇 note: we need it to be pub now
pub struct Grid {
// cut
}
#[wasm_bindgen]
impl Grid {
#[wasm_bindgen(constructor)]
pub fn parse(input: &str) -> Self {
// cut
}
}
And then, and this is the new bit, let's add a function that returns the grid as an SVG document. We'll use a crate to make the generation slightly nicer:
$ cargo add svg@0.13
(cut)
use svg::Document;
#[wasm_bindgen]
impl Grid {
#[wasm_bindgen]
pub fn to_svg(&self) -> String {
const SIDE: usize = 64;
let mut document =
Document::new().set("viewBox", (0, 0, self.width * SIDE, self.height * SIDE));
for y in 0..self.height {
for x in 0..self.width {
let cell = self.cell((x, y).into()).unwrap();
let (title, r, g, b) = match cell {
Cell::Start => ("start".to_string(), 216, 27, 96),
Cell::End => ("end".to_string(), 30, 136, 229),
Cell::Square(elevation) => {
let title = format!("elevation {elevation}");
let elevation = *elevation as f32 / 25.0;
let f = (elevation * 255.0) as u8;
(title, f, f, f)
}
};
let rect = svg::node::element::Rectangle::new()
.set("x", x * SIDE)
.set("y", y * SIDE)
.set("width", SIDE)
.set("height", SIDE)
.set("fill", format!("rgb({r}, {g}, {b})"))
.set("stroke", "white")
.set("stroke-width", "2px")
.add(svg::node::element::Title::new().add(svg::node::Text::new(title)));
document = document.add(rect);
}
}
document.to_string()
}
}
Last time we used WASM we converted the whole project over to a library. This
time let's have it be a bin+lib
.
We can rename our src/main.rs
file to src/lib.rs
, and create another
src/main.rs
, moving over just the main
function, importing Grid
as needed:
// in `src/main.rs`
use day12::Grid;
fn main() {
let grid = Grid::parse(include_str!("sample-input.txt"));
println!("{grid:?}");
}
We can now add cdylib
as a library type in Cargo.toml
, for the wasm build:
# in `Cargo.toml`
[package]
name = "day12"
version = "0.1.0"
edition = "2021"
# 👇 new section!
[lib]
crate-type = ["lib", "cdylib"]
[dependencies]
svg = "0.13"
wasm-bindgen = "0.2.83"
And, well, build it! Although - I'm going to be "deploying" this a bunch, as in, copying the build artifacts to my blog a bunch of times. That seems like it could be a job for the just task runner:
# in `Justfile`
# just manual: https://github.com/casey/just#readme
_default:
just --list
deploy name:
#!/bin/bash -eux
DEST="/home/amos/bearcove/fasterthanli.me/content/series/advent-of-code-2022/part-12/assets/{{name}}"
echo "Will deploy to $DEST"
if [ -d $DEST ]; then
echo "Destination already exists, removing with confirmation"
rm -rfI $DEST
fi
rm -rf pkg
wasm-pack build --target web
mkdir -p $DEST/pkg
cp index.html $DEST/
cp pkg/*.{js,wasm} $DEST/pkg
And now we need an index.html
: we can keep it simple.
<!DOCTYPE html>
<html>
<head>
<style>
html,
body {
margin: 0;
padding: 0;
background: transparent;
}
svg {
width: 100%;
height: auto;
}
</style>
</head>
<body>
<div id="content"></div>
<script type="module">
import init, { Grid } from "./pkg/day12.js";
async function main() {
// DOM is already loaded, the `<script>` tag is at the bottom of the page
let content = document.getElementById("content");
// wait for wasm to be actually loaded
await init();
let input = `Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi`;
let grid = new Grid(input);
content.innerHTML = grid.to_svg();
};
main();
</script>
</body>
</html>
And here's the result!
This looks like a static image, but it's not: you can hover the squares, and you should see the exact values. It's not a very interesting visualization yet, let's raise the stakes as we try and so some path-finding.
Finding walkable neighbors
First, let's make a helper function that determines the neighbors we can move to: the problem statement says we can move to a cell at most one higher. It also tells us the start cell has the lowest elevation, and the end cell has the highest elevation.
impl Cell {
fn elevation(self) -> u8 {
match self {
Cell::Start => 0,
Cell::End => 25,
Cell::Square(e) => e,
}
}
}
Because I'm in love with the unstable feature that lets us have
checked_add_signed
, let's once again reach for a nightly:
# in `rust-toolchain.toml`
[toolchain]
channel = "nightly-2022-12-09"
impl Grid {
fn walkable_neighbors(&self, coord: GridCoord) -> impl Iterator<Item = GridCoord> + '_ {
let curr_elev = self.cell(coord).unwrap().elevation();
let deltas: [(isize, isize); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];
deltas.into_iter().filter_map(move |(dx, dy)| {
Some(GridCoord {
x: coord.x.checked_add_signed(dx)?,
y: coord.y.checked_add_signed(dy)?,
})
.filter(|&coord| self.in_bounds(coord))
.filter(|&coord| {
let other_elev = self.cell(coord).unwrap().elevation();
other_elev <= curr_elev + 1
})
})
}
}
With that, we can show possible paths on the whole map!
// in `to_svg`, after drawing the grid (I've dimmed the cells a little so
// it's easier to see the arrows).
let defs = svg::node::element::Definitions::new().add(
svg::node::element::Marker::new()
.set("id", "arrowhead")
.set("markerWidth", 10)
.set("markerHeight", 7)
.set("refX", 10)
.set("refY", 3.5)
.set("orient", "auto")
.add(
svg::node::element::Polygon::new()
.set("points", "0 0, 10 3.5, 0 7")
// `stroke-context` is supposed to work but I couldn't
// get it to work.
.set("fill", "#ffc107"),
),
);
document = document.add(defs);
for y in 0..self.height {
for x in 0..self.width {
let coord: GridCoord = (x, y).into();
for ncoord in self.walkable_neighbors(coord) {
let side = SIDE as f64;
let (x, y) = (x as f64, y as f64);
let dx = ncoord.x as f64 - x;
let dy = ncoord.y as f64 - y;
let line = svg::node::element::Line::new()
.set("x1", (x + 0.5 + dx * 0.05) * side)
.set("y1", (y + 0.5 + dy * 0.05) * side)
.set("x2", (x + 0.5 + dx * 0.45) * side)
.set("y2", (y + 0.5 + dy * 0.45) * side)
.set("stroke", "#ffc107")
.set("stroke-width", "1px")
.set("marker-end", "url(#arrowhead)");
document = document.add(line);
}
}
}
And this is what we get:
And now, well, we just have to get to it.
Walking the graph
There's a plethora of path-finding algorithms out there — let's go with something relatively simple and intuitive. We'll do something "breadth-first": we start with a set of cells, and find out all the neighbors of all those cells, excluding the ones we've already visited (since there's a shorter or equivalent path to them).
Eventually, we'll either have the end cell in our set, or we'll run out of cells to explore. Either way the algorithm is over.
So, let's add a couple fields to Grid
:
struct CellRecord {
prev: Option<GridCoord>,
}
#[wasm_bindgen]
pub struct Grid {
width: usize,
height: usize,
data: Vec<Cell>,
visited: HashMap<GridCoord, CellRecord>,
current: HashSet<GridCoord>,
num_steps: usize,
}
In the constructor, everything's set to Default
btw:
Self {
width,
height,
data,
current: Default::default(),
visited: Default::default(),
num_steps: 0,
}
We end up initializing all this in the step
method itself:
impl Grid {
#[wasm_bindgen]
pub fn step(&mut self) {
if self.current.is_empty() {
// find start coordinate
let mut start_coord: Option<GridCoord> = None;
for y in 0..self.height {
for x in 0..self.width {
let coord: GridCoord = (x, y).into();
if let Cell::Start = self.cell(coord).unwrap() {
start_coord = Some(coord);
break;
}
}
}
let start_coord = start_coord.unwrap();
self.current.insert(start_coord);
self.visited.insert(start_coord, CellRecord { prev: None });
return;
}
let current = std::mem::take(&mut self.current);
let mut next = HashSet::new();
let mut visited = std::mem::take(&mut self.visited);
for curr in current {
for ncoord in self.walkable_neighbors(curr) {
if visited.contains_key(&ncoord) {
// don't visit it again!
continue;
}
visited.insert(ncoord, CellRecord { prev: Some(curr) });
next.insert(ncoord);
}
}
self.current = next;
self.visited = visited;
self.num_steps += 1;
}
}
For the sake of UI, we can add more getters:
#[wasm_bindgen]
pub fn num_visited(&self) -> usize {
self.visited.len()
}
#[wasm_bindgen]
pub fn num_cells(&self) -> usize {
self.width * self.height
}
#[wasm_bindgen]
pub fn num_steps(&self) -> usize {
self.num_steps
}
I messed with the styling a bit, but mostly the markup on the page now looks like:
<div id="controls">
<button id="reset">♻ Reset</button>
<button id="step">➡ Step</button>
<div id="status"></div>
<div id="bar"></div>
</div>
<div id="content"></div>
And the code to drive it is something like:
async function main() {
// DOM is already loaded, the `<script>` tag is at the bottom of the page
let content = document.getElementById("content");
let status = document.getElementById("status");
let bar = document.getElementById("bar");
let reset_button = document.getElementById("reset");
let step_button = document.getElementById("step");
// wait for wasm to be actually loaded
await init();
let state = {};
let render = () => {
let { grid } = state;
content.innerHTML = grid.to_svg();
let percent = (grid.num_visited() / grid.num_cells() * 100);
status.innerText = `${grid.num_steps()} steps, ${grid.num_visited()}/${grid.num_cells()} visited (${percent.toFixed(1)}%)`;
bar.style.right = `${100 - percent}%`;
};
let reset = () => {
let input = `Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi`;
state.grid = new Grid(input);
render();
}
reset_button.onclick = reset;
step_button.onclick = () => {
state.grid.step();
render();
};
reset();
};
main();
It's all messy, we're mixing snake_case
and camelCase
because JavaScript and
Rust are fighting it out, but it's all good! Who cares! It's all throwaway code,
we're just having nice and, uh, slightly dirty fun.
The new drawing code.. could be anything, let your imagination wonder! I went with something relatively straightforward:
#[wasm_bindgen]
impl Grid {
#[wasm_bindgen]
pub fn to_svg(&self) -> String {
const SIDE: usize = 64;
let side = SIDE as f64;
let mut document =
Document::new().set("viewBox", (0, 0, self.width * SIDE, self.height * SIDE));
for y in 0..self.height {
for x in 0..self.width {
let cell = self.cell((x, y).into()).unwrap();
let (title, r, g, b) = match cell {
Cell::Start => ("start".to_string(), 216, 27, 96),
Cell::End => ("end".to_string(), 30, 136, 229),
Cell::Square(elevation) => {
let title = format!("elevation {elevation}");
let elevation = *elevation as f32 / 25.0;
let f = (elevation * 180.0) as u8;
(title, f, f, f)
}
};
let rect = svg::node::element::Rectangle::new()
.set("x", x * SIDE)
.set("y", y * SIDE)
.set("width", SIDE)
.set("height", SIDE)
.set("fill", format!("rgb({r}, {g}, {b})"))
.set("stroke", "white")
.set("stroke-width", "2px")
.add(svg::node::element::Title::new().add(svg::node::Text::new(title)));
document = document.add(rect);
}
}
let defs = svg::node::element::Definitions::new().add(
svg::node::element::Marker::new()
.set("id", "arrowhead")
.set("markerWidth", 10)
.set("markerHeight", 7)
.set("refX", 7)
.set("refY", 3.5)
.set("orient", "auto")
.add(
svg::node::element::Polygon::new()
.set("points", "0 0, 10 3.5, 0 7")
// `stroke-context` is supposed to work but I couldn't
// get it to work.
.set("fill", "#ffc107"),
),
);
document = document.add(defs);
for coord in self.visited.keys() {
let circle = svg::node::element::Circle::new()
.set("cx", (coord.x as f64 + 0.5) * side)
.set("cy", (coord.y as f64 + 0.5) * side)
.set("r", side * 0.1)
.set("fill", "#fff");
document = document.add(circle);
}
for coord in self.current.iter() {
let circle = svg::node::element::Circle::new()
.set("cx", (coord.x as f64 + 0.5) * side)
.set("cy", (coord.y as f64 + 0.5) * side)
.set("r", side * 0.1)
.set("fill", "#ffc107");
document = document.add(circle);
let record = self.visited.get(coord).unwrap();
let mut curr = record;
let mut coord = *coord;
while let Some(prev) = curr.prev.as_ref() {
curr = self.visited.get(prev).unwrap();
let (x, y) = (prev.x as f64, prev.y as f64);
let dx = coord.x as f64 - x;
let dy = coord.y as f64 - y;
let line = svg::node::element::Line::new()
.set("x1", (x + 0.5 + dx * 0.2) * side)
.set("y1", (y + 0.5 + dy * 0.2) * side)
.set("x2", (x + 0.5 + dx * 0.8) * side)
.set("y2", (y + 0.5 + dy * 0.8) * side)
.set("stroke", "#ffc107")
.set("stroke-width", "1.5px")
.set("marker-end", "url(#arrowhead)");
document = document.add(line);
coord = *prev;
}
}
document.to_string()
}
}
Part 1 solution, in your browser
I've iterated on this solution for a bit! First I added a file picker so it can be used with a "real" puzzle input (here's my input if you're not participating in AoC 12).
Then I had to adjust the rendering a little, because the real input is much much larger than the sample one. I made everything bigger, removed the arrowheads, and eventually, for performance, I split the background (heightmap) and foreground (paths) to relieve pressure on the poor browser's garbage collector.
Anyway, enjoy!
(Again, this is much more fun to watch with a real puzzle input, you should try with yours, or try downloading mine linked above, and dragging into that file input).
Part 2 solution, in your browser
The trick to part 2 is to realize that, no, you don't have to search all the paths from the lowest elevation to the end, you can just reverse the direction of the search.
You have to start from the end, change the test to "jump down at most 1 in height", and stop when you reach elevation zero.
The changes are left as an exercise to the reader, but you can play with the solution here:
Cool bear's hot tip
Because we're doing a BFS (breadth-first search), it's no costlier to keep exactly the same movement/neighbor rules, but have the starting set simply be all cells with the lowest elevation. Thanks to salameme on GitHub for the tip.
Here's another article just for you:
Image decay as a service
Since I write a lot of articles about Rust, I tend to get a lot
of questions about specific crates: "Amos, what do you think of oauth2-simd
?
Is it better than openid-sse4
? I think the latter has a lot of boilerplate."
And most of the time, I'm not sure what to responds. There's a lot of crates out there. I could probably review one crate a day until I retire!