Day 10 (Advent of Code 2022)

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

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

Shell session
$ cargo add nom@7
(cut)

...to parse the input into nicely-organized Rust data structures:

Rust code
// 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!

Rust code
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!

Rust code
fn main() {
    let mut ms = MachineState::new();
    loop {
        println!("{:?}", ms);
        if !ms.step() {
            break;
        }
    }
}
Shell session
$ 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:

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

Rust code
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:

Rust code
const DISPLAY_MASK: u64 = 0b1111111111111111111111111111111111111111;

And then a function to get the value of the sprite:

Rust code
fn sprite_value(pos: u32) -> u64 {
    (0b11100000000000000000000000000000000000000 >> pos) & DISPLAY_MASK
}

We can even write some tests!

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

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

Shell session
$ 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!

Shell session
$ cargo add --dev pretty_assertions
(cut)
Rust code
#[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:

Test failing: there's an extra 1 on the 'left' output, which is highlighted in bold, along with the corresponding 0 on the 'right' output

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:

Rust code
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:

Rust code
struct MachineState {
    instructions: VecDeque<Instruction>,
    current: Option<(Instruction, u32)>,
    cycle: u32,
    x: i32,
    // 👇
    display_lines: Vec<u64>,
}

And print them:

Rust code
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:

Rust code
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:

Rust code
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:

Shell session
$ cargo run --release --quiet
(cut)
cycle=240 x=17 current=None (0 instructions left)
##..##..##..##..##..##..##..##..##..##..
###...###...###...###...###...###...###.
####....####....####....####....####....
#####.....#####.....#####.....#####.....
######......######......######......####
#######.......#######.......#######.....
........................................

Although... it doesn't work in debug mode!

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

Rust code
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:

Rust code
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:

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

Shell session
$ cargo add wasm-bindgen@0.2
(cut)

In Cargo.toml, we also want to set crate-type:

TOML markup
[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:

Rust code
// 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):

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

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

HTML
<!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:

Rust code
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:

JavaScript code
<!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.)

This article is part 10 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?