21 min
Day 14 (Advent of Code 2022)
👋 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...
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.
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");
}
}
})
}
}
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.
$ 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?
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 = ¤t_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.
Thanks to my sponsors: Theodore Rose, Kamran Khan, Tyler Schmidtke, Jake Demarest-Mays, Michael Mrozek, Jon Gjengset, Yufan Lou, callym, Cole Kurkowski, Chris Biscardi, you got maiL, bbutkovic, Jean Manguy, Marcus Brito, WeblWabl, Geoff Cant, Torben Clasen, belzael, Integer 32, LLC, SeniorMars and 227 more
If you liked what you saw, please support my work!
Donate on GitHub
Donate on Patreon
Here's another article just for you:
12 min
In my previous article, I said I needed to stop thinking of Rust generics as Java generics, because in Rust, generic types are erased.
Someone gently pointed out that they are also erased in Java, the difference was elsewhere. And so, let's learn the difference together.
Java generics
I learned Java first (a long, long time ago), and their approach to generics made sense to me at the time.