Avatar for fasterthanlime fasterthanlime
Dec 15, 2022 clock icon 8 min #rust · #advent-of-code · #generators

Day 14 (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.

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

Cool bear

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:

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

fn main() {
    for line in include_str!("sample-input.txt").lines() {
        let polyline = Polyline::parse(line);
        println!("{polyline:?}");
    }
}

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

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

And then we can do something like this:

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

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:

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");
                }
            }
        })
    }
}
Cool bear

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

Yes... sigh yes we could.

Cool bear

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.

$ cargo add derive_more
(cut)

// 👇 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

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:

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:?}");
        }
    }
}

$ 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?

Cool bear

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:

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

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:

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

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

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

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

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

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

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

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

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

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

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

        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:

        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?

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

Here's my final render method:

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

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:

A dynamic linker murder mystery

Jul 08, 2020
clock icon 23 min #rust · #linkers · #linux · #postmortem

I write a ton of articles about rust. And in those articles, the main focus is about writing Rust code that compiles. Once it compiles, well, we're basically in the clear! Especially if it compiles to a single executable, that's made up entirely of Rust code.

That works great for short tutorials, or one-off explorations.

Unfortunately, "in the real world", our code often has to share the stage with other code. And Rust is great at that. Compiling Go code to a static library, for example, is relatively finnicky. It insists on being built with GCC (and no other compiler), and linked with GNU ld ().

not
Read more
About Legal Notice Privacy Policy Terms and Conditions