Day 14 (Advent of Code 2022)

This article is part of the Advent of Code 2022 series.

I like how the day 14 puzzle sounds, because I think it'll give me an opportunity to show off yet another way to have Rust embedded in a web page.

But first...

Let me guess: parsing?

You bet your furry ass, parsing.

Parsing

The input looks something like this:

498,4 -> 498,6 -> 496,6
503,4 -> 502,4 -> 502,9 -> 494,9

And each line is essentially... a polyline: we're supposed to draw lines between every point on the path, and that determines rocks on the map.

I don't really think we need nom for this:

Rust code
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Point {
    x: i32,
    y: i32,
}

impl Point {
    fn parse(s: &str) -> Self {
		// yolo error handling, you'll excuse me, we have other things
		// to get to.
        let mut tokens = s.split(',');
        let (x, y) = (tokens.next().unwrap(), tokens.next().unwrap());
        Self {
            x: x.parse().unwrap(),
            y: y.parse().unwrap(),
        }
    }
}

#[derive(Debug)]
struct Polyline {
    points: Vec<Point>,
}

impl Polyline {
    fn parse(s: &str) -> Self {
        Self {
            points: s.split(" -> ").map(Point::parse).collect(),
        }
    }
}

Let's try this out on the sample input:

Rust code
fn main() {
    for line in include_str!("sample-input.txt").lines() {
        let polyline = Polyline::parse(line);
        println!("{polyline:?}");
    }
}
Shell session
$ cargo run
   Compiling day14 v0.1.0 (/home/amos/bearcove/aoc2022/day14)
(cut)
    Finished dev [unoptimized + debuginfo] target(s) in 0.34s
     Running `target/debug/day14`
Polyline { points: [Point { x: 498, y: 4 }, Point { x: 498, y: 6 }, Point { x: 496, y: 6 }] }
Polyline { points: [Point { x: 503, y: 4 }, Point { x: 502, y: 4 }, Point { x: 502, y: 9 }, Point { x: 494, y: 9 }] }

Looks good!

Following polylines

So there's two little complications here. The first is that it gives us polylines, whereas we'd like to work with a grid of pixels, essentially.

That means we need to be able to "draw lines" on the grid, and for that we need to be able to interpolate between different points on the polyline.

Because we don't really ever need to look at "all the points at the same time", I don't want to collect them into a Vec or something. I'd much rather have an iterator.

But iterators are low-key annoying to write, in this case. So we're going to look at a nightly feature: generators.

You know the drill, let's pin to a recent nightly by creating a rust-toolchain.toml file:

TOML markup
[toolchain]
channel = "nightly-2022-12-15"

And then we can do something like this:

Rust code
#![feature(iter_from_generator)]
#![feature(generators)]

impl Polyline {
    fn path_points(&self) -> impl Iterator<Item = Point> + '_ {
        std::iter::from_generator(|| {
            yield Point { x: 1, y: 1 };
            yield Point { x: 2, y: 2 };
        })
    }
}

This isn't the correct logic, but I just wanted y'all to be used to the syntax.

Cool bear's hot tip

This syntax works on nightly-2022-12-15, but might not work with older or newer nightlies. This syntax might end up being changed or retired altogether. Thus is the danger of using nightly features.

And here's the real logic! With the newly stabilized let-else syntax:

Rust code
impl Polyline {
    fn path_points(&self) -> impl Iterator<Item = Point> + '_ {
        std::iter::from_generator(|| {
            let mut points = self.points.iter().copied();
            let Some(mut a) = points.next() else { return };
            yield a;

            loop {
                let Some(b) = points.next() else { return };
                if a.x == b.x {
                    let delta = (b.y - a.y).signum();
                    assert!(delta != 0);
                    loop {
                        a.y += delta;
                        yield a;
                        if a.y == b.y {
                            break;
                        }
                    }
                } else if a.y == b.y {
                    let delta = (b.x - a.x).signum();
                    assert!(delta != 0);
                    loop {
                        a.x += delta;
                        yield a;
                        if a.x == b.x {
                            break;
                        }
                    }
                } else {
                    panic!("Diagonal path");
                }
            }
        })
    }
}

I'm wondering... could you remove the duplication here by implementing std::ops::Sub and implementing signum() on Point?

Yes... sigh yes we could.

Look, do you want to do it now, or do you want to want to add it tomorrow as "reader feedback"?

You're right, you're right. But I'm gonna pull in a crate, as payback.

Shell session
$ cargo add derive_more
(cut)
Rust code
// 👇 now deriving `Add` and `Sub` through `derive_more`
#[derive(
    Debug, Clone, Copy, PartialEq, Eq, derive_more::Add, derive_more::AddAssign, derive_more::Sub,
)]
struct Point {
    x: i32,
    y: i32,
}

impl Point {
	// that one's not in a trait
    fn signum(self) -> Self {
        Self {
            x: self.x.signum(),
            y: self.y.signum(),
        }
    }
}

And now our

Rust code
impl Polyline {
    fn path_points(&self) -> impl Iterator<Item = Point> + '_ {
        std::iter::from_generator(|| {
            let mut points = self.points.iter().copied();
            let Some(mut a) = points.next() else { return };
            yield a;

            loop {
                let Some(b) = points.next() else { return };
                let delta = (b - a).signum();
                assert!((delta.x == 0) ^ (delta.y == 0));

                loop {
                    a += delta;
                    yield a;
                    if a == b {
                        break;
                    }
                }
            }
        })
    }
}

And voila:

Rust code
fn main() {
    for line in include_str!("sample-input.txt").lines() {
        let polyline = Polyline::parse(line);
        println!("{polyline:?}");
        for p in polyline.path_points() {
            println!("{p:?}");
        }
    }
}
Shell session
$ cargo run
   Compiling day14 v0.1.0 (/home/amos/bearcove/aoc2022/day14)
    Finished dev [unoptimized + debuginfo] target(s) in 0.43s
     Running `target/debug/day14`
Polyline { points: [Point { x: 498, y: 4 }, Point { x: 498, y: 6 }, Point { x: 496, y: 6 }] }
Point { x: 498, y: 4 }
Point { x: 498, y: 5 }
Point { x: 498, y: 6 }
Point { x: 497, y: 6 }
Point { x: 496, y: 6 }
Polyline { points: [Point { x: 503, y: 4 }, Point { x: 502, y: 4 }, Point { x: 502, y: 9 }, Point { x: 494, y: 9 }] }
Point { x: 503, y: 4 }
Point { x: 502, y: 4 }
Point { x: 502, y: 5 }
Point { x: 502, y: 6 }
Point { x: 502, y: 7 }
Point { x: 502, y: 8 }
Point { x: 502, y: 9 }
Point { x: 501, y: 9 }
Point { x: 500, y: 9 }
Point { x: 499, y: 9 }
Point { x: 498, y: 9 }
Point { x: 497, y: 9 }
Point { x: 496, y: 9 }
Point { x: 495, y: 9 }
Point { x: 494, y: 9 }

Are you happy now? Is that solution smartass-approved?

Amos, it's perfect. Just look at it 🥹

Populating the map

As for the second complication, it's that we're not given the size of the grid.

But at the cost of going through every polyline twice, we can solve that:

Rust code
#[derive(Debug, Clone, Copy)]
enum Cell {
    Air,
    Rock,
    Sand,
}

// Note: X+ goes right, Y+ goes down
struct Grid {
    origin: Point,
    width: usize,
    height: usize,
    cells: Vec<Cell>,
}

impl Grid {
    fn parse(input: &str) -> Self {
        let polylines: Vec<_> = input.lines().map(Polyline::parse).collect();

        let (mut min_x, mut min_y, mut max_x, mut max_y) = (i32::MAX, i32::MAX, i32::MIN, i32::MIN);

        // sand falls from `(500,0)`
        let sand_spawn = Point { x: 500, y: 0 };

        for point in polylines
            .iter()
            .flat_map(|p| p.points.iter())
            .chain(std::iter::once(&sand_spawn))
        {
            min_x = min_x.min(point.x);
            min_y = min_y.min(point.y);
            max_x = max_x.max(point.x);
            max_y = max_y.max(point.y);
        }

        dbg!(min_x, max_x);
        dbg!(min_y, max_y);
        let origin = Point { x: min_x, y: min_y };
        let width: usize = (max_x - min_x + 1).try_into().unwrap();
        let height: usize = (max_y - min_y + 1).try_into().unwrap();
        dbg!(origin, width, height);
        let mut grid = Self {
            origin,
            width,
            height,
            cells: vec![Cell::Air; width * height],
        };

        for point in polylines.iter().flat_map(|p| p.path_points()) {
            *grid.cell_mut(point).unwrap() = Cell::Rock;
        }
        grid
    }

    fn cell_index(&self, point: Point) -> Option<usize> {
        let Point { x, y } = point - self.origin;
        // negative coords after offsetting = outside of grid
        let x: usize = x.try_into().ok()?;
        let y: usize = y.try_into().ok()?;

        if x < self.width && y < self.height {
            Some(y * self.width + x)
        } else {
            None
        }
    }

    fn cell(&self, point: Point) -> Option<&Cell> {
        Some(&self.cells[self.cell_index(point)?])
    }

    fn cell_mut(&mut self, point: Point) -> Option<&mut Cell> {
        // borrow checker won't let us do that inline 🙃
        let cell_index = self.cell_index(point)?;
        Some(&mut self.cells[cell_index])
    }
}

Let's add a quick debug impl just to make sure we got it right:

Rust code
impl fmt::Debug for Grid {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for y in 0..self.height {
            for x in 0..self.width {
                let point = Point {
                    x: x as _,
                    y: y as _,
                } + self.origin;
                let cell = self.cell(point).unwrap();
                let c = match cell {
                    Cell::Air => '.',
                    Cell::Rock => '#',
                    Cell::Sand => 'o',
                };
                write!(f, "{c}")?;
            }
            writeln!(f)?;
        }
        Ok(())
    }
}

And we can visually check that our output is the same as the problem statement:

Rust code
fn main() {
    let grid = Grid::parse(include_str!("sample-input.txt"));
    println!("{grid:?}");
}
Shell session
$ cargo run               
   Compiling day14 v0.1.0 (/home/amos/bearcove/aoc2022/day14)
(cut: some warnings)
    Finished dev [unoptimized + debuginfo] target(s) in 0.49s
     Running `target/debug/day14`
[src/main.rs:106] min_x = 494
[src/main.rs:106] max_x = 503
[src/main.rs:107] min_y = 0
[src/main.rs:107] max_y = 9
[src/main.rs:111] origin = Point {
    x: 494,
    y: 0,
}
[src/main.rs:111] width = 10
[src/main.rs:111] height = 10
..........
..........
..........
..........
....#...##
....#...#.
..###...#.
........#.
........#.
#########.

Drawing the map

I've been having so much fun with wasm, it would be a shame to stop now!

As we did in day 12, let's split our code across two files, so we have a bin+lib crate.

Everything except the main function goes in src/lib.rs, and src/main.rs becomes:

Rust code
// in `src/main.rs`

use day14::Grid;

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

Note that we have to make several things in the lib pub, so we can use them from the bin.

Then we can add a few dependencies:

Rust code
$ cargo add wasm-bindgen@0.2
# cut

$ cargo add js-sys
# cut

$ cargo add web-sys -F CanvasRenderingContext2d,Document,Element,HtmlCanvasElement,Window
# cut

Just like the windows crate, web-sys exports almost nothing by default, because the API surface area is so large: we have to opt into whatever we want to use.

Then, we need to adjust the lib.crate-type property to prepare and build for wasm:

TOML markup
# in `Cargo.toml`

[lib]
crate-type = ["lib", "cdylib"]

# (other sections omitted)

Again, the "lib" part is so it can be used from a Rust binary (our src/main.rs), and the "cdylib" part is for WebAssembly. It's not really C, and it's not really a dynamic library, but toolchains do be like that sometimes.

We'll need to expose some functions to wasm:

Rust code
// in `src/lib.rs`

use wasm_bindgen::{prelude::*, JsCast};

#[wasm_bindgen]
pub struct Grid {
    // cut: fields
}

#[wasm_bindgen]
impl Grid {
    #[wasm_bindgen(constructor)]
    #[allow(clippy::new_without_default)]
    pub fn new() -> Self {
        Self::parse(include_str!("input.txt"))
    }

    #[wasm_bindgen]
    pub fn render(&self, canvas_id: &str) {
        let document = web_sys::window().unwrap().document().unwrap();
        let canvas = document.get_element_by_id(canvas_id).unwrap();
        let canvas: web_sys::HtmlCanvasElement = canvas
            .dyn_into::<web_sys::HtmlCanvasElement>()
            .map_err(|_| ())
            .unwrap();

        canvas.set_width(self.width as _);
        canvas.set_height(self.height as _);

        let context = canvas
            .get_context("2d")
            .unwrap()
            .unwrap()
            .dyn_into::<web_sys::CanvasRenderingContext2d>()
            .unwrap();

        for y in 0..self.height {
            for x in 0..self.width {
                let point = Point {
                    x: x as _,
                    y: y as _,
                } + self.origin;
                let cell = self.cell(point).unwrap();
                let color = match cell {
                    Cell::Air => "#4db4e3",
                    Cell::Rock => "#33302d",
                    Cell::Sand => "#827f58",
                };
                context.set_fill_style(&JsValue::from_str(color));
                context.fill_rect(x as _, y as _, 1.0, 1.0);
            }
        }
    }
}

And then, with a barebones index.html:

HTML
<!DOCTYPE html>
<html>

<head>
	<head>
	</head>
	<style>
		html,
		body {
			width: 100%;
			margin: 0;
			padding: 0;
			background: transparent;
			font-family: "Open Sans", sans-serif;
		}

		canvas {
			image-rendering: crisp-edges;
			width: 100%;
			max-width: 400px;
			height: auto;
		}
	</style>
</head>

<body>
	<canvas id="map"></canvas>

	<script type="module">
		import init, { Grid } from "./pkg/day14.js";

		async function main() {
			// wait for wasm to be actually loaded
			await init();

			let grid = new Grid();
			grid.render("map");
		};
		main();
	</script>
</body>

</html>

It's a little silly to draw 1px-wide rectangles, but here we are.

And through the magic of wasm-pack --target web, we can show it in the browser!

What my puzzle input looks like

With the code shown above, here's what my puzzle input looks like:

And now it's time to start simulating stuff!

We'll need a new field in Grid for the current grain of sand, and a step method.

Rust code
// in `src/lib.rs`

const SPAWN_POINT: Point = Point { x: 500, y: 0 };

// Note: X+ goes right, Y+ goes down
#[wasm_bindgen]
pub struct Grid {
    // omitted: existing fields.
    settled: usize,
    current_grain: Point,
    // note: in `parse`, this gets initialized to SPAWN_POINT
}

#[wasm_bindgen]
impl Grid {
    // omitted: other methods

    #[wasm_bindgen]
    pub fn num_settled(&self) -> usize {
        self.settled
    }

    #[wasm_bindgen]
    pub fn step(&mut self) {
        let straight_down = self.current_grain + Point { x: 0, y: 1 };
        let down_left = self.current_grain + Point { x: -1, y: 1 };
        let down_right = self.current_grain + Point { x: 1, y: 1 };
        let options = [straight_down, down_left, down_right];

        // Can we move?
        if let Some(pos) = options
            .into_iter()
            .find(|pos| matches!(self.cell(*pos), Some(Cell::Air)))
        {
            self.current_grain = pos;
            return;
        }

        // If not, are we moving off-screen?
        if let Some(pos) = options.into_iter().find(|pos| self.cell(*pos).is_none()) {
            // yes, we're done
            return;
        }

        // If not, then we've settled
        self.settled += 1;
        *self.cell_mut(self.current_grain).unwrap() = Cell::Sand;
        self.current_grain = SPAWN_POINT;
    }
}

And if we add a few controls... we get this!

Part 1 solution

Note: the simulation is paused in the beginning, and it's using my input.

You'll have to select a speed higher than 0 to get it started!

As fun as this simulation is, we can do better. Because grains of sands move down by one or settle on every step, we can emit grains of sands more often, simulating all of them at once.

We can have:

Rust code
struct Grid {
    // instead of `current_grain`
    grains: Vec<Point>,
    // omitted: other fields
}

And, using nightly's drain_filter feature, because I can:

Rust code
#![feature(drain_filter)]

#[wasm_bindgen]
impl Grid {
    // omitted: other methods

    #[wasm_bindgen]
    pub fn step(&mut self) {
        // this is _relatively_ cheap. an empty vec doesn't actually make any
        // heap allocations iirc, and we're re-using the storage of `grains`
        // every turn
        let mut grains = std::mem::take(&mut self.grains);
        let _ = grains
            .drain_filter(|grain| {
                let straight_down = *grain + Point { x: 0, y: 1 };
                let down_left = *grain + Point { x: -1, y: 1 };
                let down_right = *grain + Point { x: 1, y: 1 };
                let options = [straight_down, down_left, down_right];

                // Can we move?
                if let Some(pos) = options
                    .into_iter()
                    .find(|pos| matches!(self.cell(*pos), Some(Cell::Air)))
                {
                    *grain = pos;
                    return false; // keep it
                }

                // If not, are we moving off-screen?
                if options.into_iter().any(|pos| self.cell(pos).is_none()) {
                    return true; // remove it
                }

                // If not, then we've settled
                self.settled += 1;
                *self.cell_mut(*grain).unwrap() = Cell::Sand;
                true // remove it
            })
            .count();
        self.grains = grains;
        self.grains.push(SPAWN_POINT);
    }
}

The drawing code also needs to be adjusted.

Part 1 alternative solution

And here's the part 1 solution again, but this time, one grain is spawned every frame:

Part 2

Part 2 is like part 1, but now we have a floor, that's 2 units below the bottom-most bit of rock. And now we have to stop, not when sand starts falling down "into the abyss", but when a grain of sand settles at the top.

And that's when you realize why the spawn position is at (500, 0).

The floor is supposed to be infinite, but the input isn't, so, using the time-travel powers of editing this article, I'm going to decide on a reasonable size for the floor:

Rust code
        let floor_y = max_y + 2;
        min_x = 300;
        max_x = 700;
        max_y = floor_y;
        polylines.push(Polyline {
            points: vec![
                Point { x: min_x, y: floor_y },
                Point {
                    x: max_x,
                    y: floor_y,
                },
            ],
        });

(You can do it programmatically, but since those dimensions dictate how large our canvas is, I chose something smaller than the theoretical maximum).

And we can add the end condition at the beginning of step:

Rust code
        if matches!(self.cell(Point { x: 500, y: 0 }).unwrap(), Cell::Sand) {
            // don't step, we're done
            return;
        }

And you know what the problem becomes then?

Drawing the screen becomes really slow. But as I said earlier, drawing 1px-wide rectangles is a little silly. Not just because they're 1-pixel rectangles, but also because we're doing a lot of WASM-to-JS calls.

What if instead, we built the image from scratch in Rust?

Rust code
# features are additive, luckily
$ cargo add web-sys -F ImageData

Here's my final render method:

Rust code
#[wasm_bindgen]
impl Grid {
    // omitted: other methods

    #[wasm_bindgen]
    #[allow(clippy::identity_op)]
    pub fn render(&self, canvas_id: &str) {
        let document = web_sys::window().unwrap().document().unwrap();
        let canvas = document.get_element_by_id(canvas_id).unwrap();
        let canvas: web_sys::HtmlCanvasElement = canvas
            .dyn_into::<web_sys::HtmlCanvasElement>()
            .map_err(|_| ())
            .unwrap();

        canvas.set_width(self.width as _);
        canvas.set_height(self.height as _);

        let context = canvas
            .get_context("2d")
            .unwrap()
            .unwrap()
            .dyn_into::<web_sys::CanvasRenderingContext2d>()
            .unwrap();

        let mut pixels = vec![0u8; 4 * self.width * self.height];
        #[allow(clippy::identity_op)]
        for y in 0..self.height {
            for x in 0..self.width {
                let base_index = 4 * (y * self.width + x);
                pixels[base_index + 0] = 255;
                pixels[base_index + 1] = 20;
                pixels[base_index + 2] = 20;
                pixels[base_index + 3] = 255;
            }
        }

        // let air_color = JsValue::from_str("#4db4e3");
        let air_color: [u8; 3] = [77, 180, 227];

        // let rock_color = JsValue::from_str("#33302d");
        let rock_color: [u8; 3] = [51, 48, 45];

        // let sand_color = JsValue::from_str("#827f58");
        let sand_color: [u8; 3] = [130, 127, 88];

        // let current_color = JsValue::from_str("#f5ce31");
        let current_color: [u8; 3] = [245, 206, 49];

        for y in 0..self.height {
            for x in 0..self.width {
                let point = Point {
                    x: x as _,
                    y: y as _,
                } + self.origin;
                let cell = self.cell(point).unwrap();
                let color = match cell {
                    Cell::Air => &air_color,
                    Cell::Rock => &rock_color,
                    Cell::Sand => &sand_color,
                };

                let base_index = 4 * (y * self.width + x);
                pixels[base_index + 0] = color[0];
                pixels[base_index + 1] = color[1];
                pixels[base_index + 2] = color[2];
            }
        }

        for grain in self.grains.iter().copied() {
            // then draw current grain of sand
            let Point { x, y } = grain - self.origin;

            let color = &current_color;
            let base_index = 4 * (y as usize * self.width + x as usize);
            pixels[base_index + 0] = color[0];
            pixels[base_index + 1] = color[1];
            pixels[base_index + 2] = color[2];
        }

        let imagedata =
            ImageData::new_with_u8_clamped_array(Clamped(&pixels[..]), self.width as _).unwrap();
        context.put_image_data(&imagedata, 0.0, 0.0).unwrap();
    }
}

You can do much better than that: everything except self.grains is "append-only", so we could keep a separate buffer just with that, and copy it to a second buffer where we'd add the grains on top.

Regardless, it's pretty smooth for me!

Part 2 solution

Here it is: x8 is a nice speed for this one.

And yes, it does give the right answer for my input! No file inputs or reset buttons this time, if you want to play with it more you'll just have to make your own! Remember, these articles are thinly-veiled excuses to teach you more Rust.

This article is part 14 of the Advent of Code 2022 series.

Read the next part

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

Github logo Donate on GitHub Patreon logo Donate on Patreon

Latest video View all

video cover image
C++ vs Rust: which is faster?

I ported some Advent of Code solutions from C/C++ to Rust, and used the opportunity to compare performance. When I couldn't explain why they performed differently, I had no choice but to disassemble both and look at what the codegen was like!

Watch now
Looking for the homepage?
Another article: Recursive iterators in Rust