Home
Log in
Avatar for fasterthanlime fasterthanlime
Dec 13, 2022 clock icon 19 min #rust · #advent-of-code · #wasm · #interactive

Day 12 (Advent of Code 2022)

From the series Advent of Code 2022
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

👋 This page was last updated ~2 years ago. Just so you know.

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:

Rust code
#[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:

Rust code
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:

Rust code
#[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:

Rust code
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:

Rust code
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:

Rust code
fn main() {
    let grid = Grid::parse(include_str!("sample-input.txt"));
    println!("{grid:?}");
}

And it seems okay:

Shell session
$ 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:

Shell session
$ cargo add wasm-bindgen@0.2
(cut)

We can now add wasm_bindgen annotations on... Grid for example!

Rust code
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:

Shell session
$ cargo add svg@0.13
(cut)
Rust code
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:

Rust code
// 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:

TOML markup
# 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.

HTML
<!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.

Rust code
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:

TOML markup
# in `rust-toolchain.toml`
[toolchain]
channel = "nightly-2022-12-09"
Rust code
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!

Rust code
        // 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:

Rust code
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:

Rust code
        Self {
            width,
            height,
            data,
            current: Default::default(),
            visited: Default::default(),
            num_steps: 0,
        }

We end up initializing all this in the step method itself:

Rust code
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:

Rust code
    #[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:

HTML
	<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:

JavaScript code
		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:

Rust code
#[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.

You're reading the Advent of Code 2022 series.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Reddit logo Comment on /r/fasterthanlime

If you liked what you saw, please support my work!

Github logo Donate on GitHub Patreon logo Donate on Patreon

Here's another article just for you:

The bottom emoji breaks rust-analyzer
Feb 13, 2023
clock icon 1 hour 10 min #rust · #emacs

Some bugs are merely fun. Others are simply delicious!

Today's pick is the latter.

Reproducing the issue, part 1

(It may be tempting to skip that section, but reproducing an issue is an important part of figuring it out, so.)

I've never used Emacs before, so let's install it. I do most of my computing on an era-appropriate Ubuntu, today it's Ubuntu 22.10, so I just need to:

Read more