Thanks to my sponsors: Tom Forbes, Tiziano Santoro, Yufan Lou, Daniel Wagner-Hall, Alex Doroshenko, Chris Walker, Adam Gutglick, Josh Triplett, Herman J. Radtke III, Ramen, SeniorMars, Christian Bourjau, Eugene Bulkin, old.woman.josiah, Evan Relf, Tyler Schmidtke, playest, Ula, Matt Jackson, Romain Ruetschi and 230 more
8 min
Day 10 (Advent of Code 2022)
👋 This page was last updated ~2 years ago. Just so you know.
Onwards! To the day 10 puzzle.
I don't see a way to make part 1 especially fun — so let's just get to it.
Parsing
As usual, let's reach for the nom crate...
$ cargo add nom@7
(cut)
...to parse the input into nicely-organized Rust data structures:
// in `src/main.rs`
use nom::{
branch::alt,
bytes::complete::tag,
combinator::{map, value},
sequence::preceded,
IResult,
};
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
enum Instruction {
Noop,
Addx(i32),
}
impl Instruction {
fn parse(i: &str) -> IResult<&str, Self> {
let noop = tag("noop");
let addx = preceded(tag("addx "), nom::character::complete::i32);
alt((value(Self::Noop, noop), map(addx, Self::Addx)))(i)
}
fn cycles(self) -> u32 {
match self {
Self::Noop => 1,
Self::Addx(_) => 2,
}
}
}
And then, we can start simulating!
struct MachineState {
instructions: VecDeque<Instruction>,
current: Option<(Instruction, u32)>,
cycle: u32,
x: i32,
}
impl fmt::Debug for MachineState {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(
f,
"cycle={} x={} current={:?} ({} instructions left)",
self.cycle,
self.x,
self.current,
self.instructions.len()
)
}
}
impl MachineState {
fn new() -> Self {
let mut res = Self {
instructions: include_str!("sample-input1.txt")
.lines()
.map(|l| all_consuming(Instruction::parse)(l).finish().unwrap().1)
.collect(),
current: None,
cycle: 1,
x: 1,
};
res.decode();
res
}
fn decode(&mut self) {
self.current = self.instructions.pop_front().map(|ins| (ins, ins.cycles()));
}
fn step(&mut self) -> bool {
if self.current.is_none() {
return false;
}
let (ins, cycles_left) = self.current.as_mut().unwrap();
*cycles_left -= 1;
if *cycles_left == 0 {
match ins {
Instruction::Noop => {}
Instruction::Addx(x) => self.x += *x,
}
self.decode();
}
self.cycle += 1;
true
}
}
I'm not sure this is correct, as I think the problem statement, although it tries its best, leaves some room for some off-by-one errors. Let's try it!
fn main() {
let mut ms = MachineState::new();
loop {
println!("{:?}", ms);
if !ms.step() {
break;
}
}
}
$ cargo run --quiet
cycle=1 x=1 current=Some((Noop, 1)) (2 instructions left)
cycle=2 x=1 current=Some((Addx(3), 2)) (1 instructions left)
cycle=3 x=1 current=Some((Addx(3), 1)) (1 instructions left)
cycle=4 x=4 current=Some((Addx(-5), 2)) (0 instructions left)
cycle=5 x=4 current=Some((Addx(-5), 1)) (0 instructions left)
cycle=6 x=-1 current=None (0 instructions left)
That seems to match the example given in the problem statement. Let's try with the bigger input:
$ cargo run --quiet
cycle=1 x=1 current=Some((Addx(15), 2)) (145 instructions left)
cycle=2 x=1 current=Some((Addx(15), 1)) (145 instructions left)
cycle=3 x=16 current=Some((Addx(-11), 2)) (144 instructions left)
cycle=4 x=16 current=Some((Addx(-11), 1)) (144 instructions left)
cycle=5 x=5 current=Some((Addx(6), 2)) (143 instructions left)
cycle=6 x=5 current=Some((Addx(6), 1)) (143 instructions left)
cycle=7 x=11 current=Some((Addx(-3), 2)) (142 instructions left)
cycle=8 x=11 current=Some((Addx(-3), 1)) (142 instructions left)
cycle=9 x=8 current=Some((Addx(5), 2)) (141 instructions left)
cycle=10 x=8 current=Some((Addx(5), 1)) (141 instructions left)
cycle=11 x=13 current=Some((Addx(-1), 2)) (140 instructions left)
cycle=12 x=13 current=Some((Addx(-1), 1)) (140 instructions left)
cycle=13 x=12 current=Some((Addx(-8), 2)) (139 instructions left)
cycle=14 x=12 current=Some((Addx(-8), 1)) (139 instructions left)
cycle=15 x=4 current=Some((Addx(13), 2)) (138 instructions left)
cycle=16 x=4 current=Some((Addx(13), 1)) (138 instructions left)
cycle=17 x=17 current=Some((Addx(4), 2)) (137 instructions left)
cycle=18 x=17 current=Some((Addx(4), 1)) (137 instructions left)
cycle=19 x=21 current=Some((Noop, 1)) (136 instructions left)
cycle=20 x=21 current=Some((Addx(-1), 2)) (135 instructions left)
(cut)
cycle=60 x=19 current=Some((Addx(-3), 2)) (113 instructions left)
(cut)
cycle=100 x=18 current=Some((Noop, 1)) (86 instructions left)
(cut)
cycle=140 x=21 current=Some((Addx(1), 2)) (60 instructions left)
(cut)
cycle=180 x=16 current=Some((Addx(-9), 2)) (36 instructions left)
(cut)
cycle=220 x=18 current=Some((Addx(1), 1)) (13 instructions left)
(cut)
cycle=241 x=17 current=None (0 instructions left)
Okay, the problem and I seem to agree. Adding some code to find the "signal strength" (cycle multiplied by the value of register X) at the 6 times the problem asks us to check should get us to part 2:
fn main() {
let mut ms = MachineState::new();
let counted = [20, 60, 100, 140, 180, 220]
.into_iter()
.collect::<HashSet<u32>>();
let mut total = 0;
loop {
println!("{:?}", ms);
// definitely not the most efficient way to do this, but they can't
// all be winners
if counted.contains(&ms.cycle) {
total += ms.cycle as i32 * ms.x;
}
if !ms.step() {
break;
}
}
println!("total: {total}");
}
And indeed it does!
Part 2
Part 2 is a lot more fun! It turns out register X indicates the center of a three-pixel wide sprite on a 40-wide line.
(% represents off-screen pixels)
%##......................................
^
X = 0
###.....................................
^
X = 1
...###..................................
^
X = 4
.....................................###
^
X = 38
......................................##%
^
X = 39
.......................................#%%
^
X = 40
Well, now's as good a time as any to do some bitwise operations. Normally we'd have to be fluent in converting from hexadecimal and binary, but Rust lets us use binary literals directly, so, we can make a mask for the screen:
const DISPLAY_MASK: u64 = 0b1111111111111111111111111111111111111111;
And then a function to get the value of the sprite:
fn sprite_value(pos: u32) -> u64 {
(0b11100000000000000000000000000000000000000 >> pos) & DISPLAY_MASK
}
We can even write some tests!
#[test]
fn test_sprite_value() {
assert_eq!(
format!("{:040b}", sprite_value(0)),
"1100000000000000000000000000000000000000"
);
assert_eq!(
format!("{:040b}", sprite_value(1)),
"1110000000000000000000000000000000000000"
);
assert_eq!(
format!("{:040b}", sprite_value(38)),
"0000000000000000000000000000000000000111"
);
assert_eq!(
format!("{:040b}", sprite_value(39)),
"0000000000000000000000000000000000000011"
);
assert_eq!(
format!("{:040b}", sprite_value(40)),
"0000000000000000000000000000000000000001"
);
}
Wait, why do we bother using format! here?
Ah that's in case the tests fail - it's easier to tell visually what's going on this way.
Without it, we'd be looking at this:
$ cargo nextest run
(cut)
--- STDERR: day10::bin/day10 test_sprite_value ---
thread 'test_sprite_value' panicked at 'assertion failed: `(left == right)`
left: `833223655424`,
right: `824633720832`', src/main.rs:63:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
And with formatting, we're looking at this:
$ cargo nextest run
(cut)
--- STDERR: day10::bin/day10 test_sprite_value ---
thread 'test_sprite_value' panicked at 'assertion failed: `(left == right)`
left: `"1100001000000000000000000000000000000000"`,
right: `"1100000000000000000000000000000000000000"`', src/main.rs:63:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
In fact, it's even better if we use pretty_assertions!
$ cargo add --dev pretty_assertions
(cut)
#[test]
fn test_sprite_value() {
use pretty_assertions::assert_eq;
assert_eq!(
format!("{:040b}", sprite_value(0)),
"1100000000000000000000000000000000000000"
);
// etc.
}
And then we get pretty colors and bold text and stuff:
Because lines wrap at 40 pixels, it seems convenient to go back on a decision I made earlier and make the cycle 0-based, and we can get the mask for the current cycle like so:
fn cycle_mask(cycle: u32) -> u64 {
(0b1000000000000000000000000000000000000000 >> (cycle % 40)) & DISPLAY_MASK
}
And now we can simulate the display! We need to keep track of display lines:
struct MachineState {
instructions: VecDeque<Instruction>,
current: Option<(Instruction, u32)>,
cycle: u32,
x: i32,
// 👇
display_lines: Vec<u64>,
}
And print them:
impl fmt::Debug for MachineState {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
writeln!(
f,
"cycle={} x={} current={:?} ({} instructions left)",
self.cycle,
self.x,
self.current,
self.instructions.len()
)?;
for line in &self.display_lines {
for i in 0..40 {
let c = if line & cycle_mask(i) > 0 { '#' } else { '.' };
write!(f, "{c}")?;
}
writeln!(f)?;
}
Ok(())
}
}
As for the simulation itself, if we separate "drawing" and "simulating the CPU", it becomes:
impl MachineState {
fn new() -> Self {
let mut res = Self {
instructions: include_str!("sample-input2.txt")
.lines()
.map(|l| all_consuming(Instruction::parse)(l).finish().unwrap().1)
.collect(),
current: None,
cycle: 0,
x: 1,
display_lines: vec![],
};
res.decode();
res
}
fn decode(&mut self) {
self.current = self.instructions.pop_front().map(|ins| (ins, ins.cycles()));
}
fn draw(&mut self) {
let crt_line = (self.cycle / 40) as usize;
if crt_line + 1 > self.display_lines.len() {
self.display_lines.push(0);
}
let crt_line = self.display_lines.get_mut(crt_line).unwrap();
let cycle_mask = cycle_mask(self.cycle);
let sprite = sprite_value(self.x as _);
*crt_line |= cycle_mask & sprite;
}
fn step(&mut self) -> bool {
if self.current.is_none() {
return false;
}
let (ins, cycles_left) = self.current.as_mut().unwrap();
*cycles_left -= 1;
if *cycles_left == 0 {
match ins {
Instruction::Noop => {}
Instruction::Addx(x) => self.x += *x,
}
self.decode();
}
self.cycle += 1;
true
}
}
As for main: no need to compute the "signal strength", we can just draw,
print, and step:
fn main() {
let mut ms = MachineState::new();
loop {
ms.draw();
println!("{:?}", ms);
if !ms.step() {
break;
}
}
}
Running with the (larger) sample input gives the expected results:
$ cargo run --release --quiet
(cut)
cycle=240 x=17 current=None (0 instructions left)
##..##..##..##..##..##..##..##..##..##..
###...###...###...###...###...###...###.
####....####....####....####....####....
#####.....#####.....#####.....#####.....
######......######......######......####
#######.......#######.......#######.....
........................................
Although... it doesn't work in debug mode!
$ cargo run --quiet
(cut)
cycle=208 x=20 current=Some((Addx(-21), 1)) (19 instructions left)
##..##..##..##..##..##..##..##..##..##..
###...###...###...###...###...###...###.
####....####....####....####....####....
#####.....#####.....#####.....#####.....
######......######......######......####
#######.................................
thread 'main' panicked at 'attempt to shift right with overflow', src/main.rs:64:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
That's right! Rust protects us against integer overflow. In this case, we don't mind, the bits can just fall off: we don't want them to wrap around.
Our sprite_value function becomes:
fn sprite_value(pos: u32) -> u64 {
// (Some things were moved around to avoid unfortunate rustfmt formatting)
let (shifted, _) = 0b11100000000000000000000000000000000000000_u64.overflowing_shr(pos);
shifted & DISPLAY_MASK
}
And now it works in debug builds as well. Once again, Rust forces you to disambiguate the behavior you want, which is annoying at first, but ultimately beneficial, in my opinion.
Squashing a bug
In my initial solution, I had a bug and I think it's a cautionary tale about unit tests. My output looked like this:
###..
...#.
...#. (cut)
.##..
..#..
...#.
In text format, this is a bit squished, but it was sufficiently recognizable as
the letter R, and it allowed me to get past the puzzle on the advent of code
website.
However, it is incorrect: most of the leftmost pixels are missing. This is due
to a bug in sprite_value. The bug is that the value of register X can be
negative!
The function should really look something like:
fn sprite_value(pos: i32) -> u64 {
let model = 0b11100000000000000000000000000000000000000_u64;
let shifted;
if pos < 0 {
(shifted, _) = model.overflowing_shl((-pos).try_into().unwrap());
} else {
(shifted, _) = model.overflowing_shr(pos.try_into().unwrap());
}
shifted & DISPLAY_MASK
}
And we should add a missing test case:
#[test]
fn test_sprite_value() {
use pretty_assertions::assert_eq;
assert_eq!(
format!("{:040b}", sprite_value(-1)),
"1000000000000000000000000000000000000000"
);
// cut: other test cases
}
More WASM?
I'm curious: can we embed this solution in this article? We've already done so with egui / eframe and trunk in the Day 9 challenge, but... I'm thinking something maybe a bit lighter.
Let's see if we can get something working:
$ cargo add wasm-bindgen@0.2
(cut)
In Cargo.toml, we also want to set crate-type:
[package]
name = "day10"
version = "0.1.0"
edition = "2021"
# 👇 here !
[lib]
crate-type = ["cdylib"]
[dependencies]
nom = "7.1.1"
wasm-bindgen = "0.2"
[dev-dependencies]
pretty_assertions = "1.3.0"
And because we now have a lib crate, not a binary crate (we could've done three
crates: one lib, one wasm-lib, and one native-executable, I just chose not to),
we must rename src/main.rs to src/lib.rs, remove the main function and
add something exported with wasm-bindgen:
// in `src/lib.rs` (renamed from `main.rs`)
// note: `fn main` is gone
// cut: everything else
use wasm_bindgen::prelude::*;
#[wasm_bindgen]
pub fn greet(name: &str) -> String {
format!("Hello, {name}")
}
Then let's grab wasm-pack: I just followed the instructions on their
website.
Then let's try to build our crate (with --target web, I don't want to play
with webpack today):
$ wasm-pack build --target web
(cut)
[INFO]: :-) Your wasm pkg is ready to publish at /home/amos/bearcove/aoc2022/day10/pkg.
In pkg, we have a bunch of files:
$ ll pkg
total 40K
-rw-rw-r-- 1 amos amos 1.3K Dec 11 17:46 day10.d.ts
-rw-rw-r-- 1 amos amos 4.9K Dec 11 17:46 day10.js
-rw-rw-r-- 1 amos amos 18K Dec 11 17:46 day10_bg.wasm
-rw-rw-r-- 1 amos amos 405 Dec 11 17:46 day10_bg.wasm.d.ts
-rw-rw-r-- 1 amos amos 188 Dec 11 17:46 package.json
Interestingly, the .js is almost a third of the size of the .wasm here!
(I'm sure they both compress well).
We can try using it from an index.html file, like so:
<!DOCTYPE html>
<html>
<head>
<script type="module">
import init, { greet } from "./pkg/day10.js";
(async function run() {
await init();
let s = greet("Cool Bear");
document.getElementById("output").innerText = s;
})();
</script>
</head>
<body>
<div id="output"></div>
</body>
</html>
And we see:
Hello, Cool Bear
As the output! Almost like magic!
We need to export a couple more things, let's see:
use wasm_bindgen::prelude::*;
#[wasm_bindgen]
pub struct Machine {
state: MachineState,
}
#[wasm_bindgen]
impl Machine {
#[wasm_bindgen(constructor)]
#[allow(clippy::new_without_default)]
pub fn new() -> Self {
Self {
state: MachineState::new(),
}
}
#[wasm_bindgen]
pub fn get_x(&self) -> i32 {
self.state.x
}
#[wasm_bindgen]
pub fn get_cycle(&self) -> u32 {
self.state.cycle
}
#[wasm_bindgen]
pub fn get_pixel(&self, x: u32, y: u32) -> bool {
let crt_line = match self.state.display_lines.get(y as usize) {
Some(l) => l,
None => return false,
};
let cycle_mask = cycle_mask(x);
*crt_line & cycle_mask > 0
}
#[wasm_bindgen]
pub fn draw(&mut self) {
self.state.draw();
}
#[wasm_bindgen]
pub fn step(&mut self) -> bool {
self.state.step()
}
}
With a bit of creativity, our index.html becomes:
<!DOCTYPE html>
<html>
<head>
<style>
html,
body {
margin: 0;
padding: 0;
background: #333;
color: #D1D4D1;
font-family: sans-serif;
}
body {
display: flex;
flex-direction: column;
align-items: center;
justify-content: center;
padding: 1em;
}
button {
font-size: 1.4rem;
padding: 0.4em 1.4em;
margin-bottom: 1em;
}
#output {
white-space: pre;
}
#output .matrix {
font-family: monospace;
letter-spacing: .4em;
color: #6C0;
}
#output i {
color: #aaa;
}
</style>
</head>
<body>
<button disabled id="play">▶ Play</button>
<div id="output">Click Play button to begin!</div>
<script type="module">
import init, { Machine } from "./pkg/day10.js";
async function main() {
// DOM is already loaded, the `<script>` tag is at the bottom of the page
let button = document.getElementById("play");
// wait for wasm to be actually loaded
await init();
button.disabled = false;
let play = () => {
button.disabled = true;
let m = new Machine();
let step = () => {
m.draw();
let s = `cycle=${m.get_cycle()}, x=${m.get_x()}\n\n<div class="matrix">`;
for (let y = 0; y < 6; y++) {
for (let x = 0; x < 40; x++) {
let c = m.get_pixel(x, y) ? "#" : "<i>.</i>";
s += c;
}
s += "\n";
}
s += "</div>";
document.getElementById("output").innerHTML = s;
if (m.step()) {
requestAnimationFrame(step);
} else {
button.disabled = false;
}
};
requestAnimationFrame(step);
};
button.onclick = () => { play(); };
};
main();
</script>
</body>
</html>
Don't get me wrong - it's still ugly as sin. We could do much better with multiple layers, some animations, maybe use a canvas? There's a lot to do here. But if it was perfect, what would be left for y'all to do?
Update: I have made it less ugly below, since I had some bugs to fix anyway.
Anyway, enjoy!
Part 2 solution, in your browser
(The solution should show above.)
Here's another article just for you:
Request coalescing in async Rust
51 min
As the popular saying goes, there are only two hard problems in computer science: caching, off-by-one errors, and getting a Rust job that isn't cryptocurrency-related.
Today, we'll discuss caching! Or rather, we'll discuss... "request coalescing", or "request deduplication", or "single-flighting" - there's many names for that concept, which we'll get into fairly soon.