Avatar for fasterthanlime fasterthanlime
Dec 13, 2022 clock icon 8 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:

#[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

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

Comment on /r/fasterthanlime

(JavaScript is required to see this. Or maybe my stuff broke)

Here's another article just for you:

Some mistakes Rust doesn't catch

Feb 07, 2022
clock icon 50 min #rust · #golang · #concurrency

I still get excited about programming languages. But these days, it's not so much because of what they let me do, but rather what they don't let me do.

Ultimately, what you can with a programming language is seldom limited by the language itself: there's nothing you can do in C++ that you can't do in C, given infinite time.

As long as a language is turing-complete and compiles down to assembly, no matter the interface, it's the same machine you're talking to. You're limited by... what your hardware can do, how much memory it has (and how fast it is), what kind of peripherals are plugged into it, and so on.

Read more
About Legal Notice Privacy Policy Terms and Conditions