DEV Community

Cover image for Advent of Code 2022 - Day 10
Eric Burden
Eric Burden

Posted on • Originally published at ericburden.work on

Advent of Code 2022 - Day 10

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Rust. I’ll post my solutions and code to GitHub as well. After finishing last year (and 2015-2019) in Julia, I needed to spend some time with Rust again! If you haven’t given AoC a try, I encourage you to do so along with me!

Day 10 - Cathode-Ray Tube

Find the problem description HERE.

The Input - Mostly Nothing

Today’s input is a list of instructions, likely to some computer emulator or something. Happily, there are only two types of instructions to concern ourselves with, “noop” and “addx”. Given that there’s a sneaking “noop” hidden inside each and every “addx”, it’s accurate to describe today’s input as mostly instructions to do nothing! This, I can handle!

/// Represents an instruction to our handheld device.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Instruction {
    Noop,
    Addx(i32),
}

/// Module wrapping the parser for the instructions from the input.
mod parser {
    use super::*;
    use anyhow::{anyhow, Result};
    use nom::{
        branch::alt,
        bytes::complete::tag,
        character::complete::i32,
        combinator::{map, value},
        multi::separated_list1,
        sequence::preceded,
        Finish, IResult,
    };

    /// Nom parser for "noop" -> Instruction:Noop
    fn noop(s: &str) -> IResult<&str, Instruction> {
        value(Instruction::Noop, tag("noop"))(s)
    }

    /// Nom parser for "addx 3" -> Instruction::Addx(3)
    fn addx(s: &str) -> IResult<&str, Instruction> {
        map(preceded(tag("addx "), i32), Instruction::Addx)(s)
    }

    /// Nom parser for either instruction variant
    fn instruction(s: &str) -> IResult<&str, Instruction> {
        alt((noop, addx))(s)
    }

    /// Nom parser for all instruction lines -> Vec<Instruction>
    pub fn parse(s: &str) -> Result<Vec<Instruction>> {
        let result = separated_list1(tag("\n"), instruction)(s);
        let (_, instrs) = result.finish().map_err(|e| anyhow!("{e}"))?;
        Ok(instrs)
    }
}

const INPUT: &str = include_str!("../../input/10/input.txt");

/// Parse that input!
fn read() -> Vec<Instruction> {
    parser::parse(INPUT).unwrap()
}

Enter fullscreen mode Exit fullscreen mode

Pretty simple parse today. I mostly even remembered which parser combinators to use. I still get mixed up sometimes between the nom::number::complete::i32 andnom::character::complete::i32 types of parsers. I need to remember that the second module in the path tells me what I’m parsing from, not what I’m parsing_into_.

Part One = Deep Dive

Having successfully splashed down into the river below, our best hope of rejoining the expedition is to fix our communicator. “But wait,” you ask, “didn’t we fix that communicator already?” We did! Then we dove off a rope bridge into a river! There’s more fixing to do. Today, we attempt to run some instructions on the device and perform a signal strength diagnostic check to make sure it’s working correctly.

/// Solve Day 10, Part 1
 fn solve(input: &[Instruction]) -> i32 {
    // Instantiate a new device, run all the instructions on it, then return
    // the total signal strength from that device.
    let mut device = Device::new();
    input.iter().for_each(|instruction| device.execute(instruction));
    device.signal_strength
}

/// Represents our handheld computing device, complete with signal strength
/// accumulator!
struct Device {
    register: i32,
    cycle: usize,
    signal_strength: i32,
}

impl Device {
    fn new() -> Self {
        Device { register: 1, cycle: 1, signal_strength: 0 }
    }

    // Execute a NOOP instruction. We'll leverage these instructions to update the
    // signal strength based on the current cycle count.
    fn execute_noop(&mut self) {
        self.cycle += 1;
        let multiple_of_20 = self.cycle % 20 == 0;
        let odd_multiple = (self.cycle / 20) % 2 == 1;

        // We'll update the signal strength on cycles 20, 60, 100, 140, etc.
        // These are all odd multiples of 20, that is, (20 * 1), (20 * 3), (20 * 5), etc.
        // So, we check that the current cycle count is a multiple of 20 and that the
        // current cycle count divided by 20 is an odd number.
        if multiple_of_20 && odd_multiple {
            self.signal_strength += (self.cycle as i32) * self.register;
        }
    }

    /// Execute an ADDX instruction. We leverage the NOOP instructions here to update
    /// the cycle count and the signal strength, if necessary. It's important that
    /// the register be updated between the NOOP instructions, since the puzzle states
    /// signal strength is checked _during_ the cycle and not after.
    fn execute_addx(&mut self, value: i32) {
        self.execute_noop();
        self.register += value;
        self.execute_noop();
    }

    /// Dispatch for instruction execution. Calls the appropriate execute method
    /// depending on the instruction provided.
    fn execute(&mut self, instr: &Instruction) {
        match instr {
            Instruction::Noop => self.execute_noop(),
            Instruction::Addx(v) => self.execute_addx(*v),
        }
    }
}

Enter fullscreen mode Exit fullscreen mode

Turns out those “noop” instructions did more than we thought! Plus, we managed to sneak two “noop” instructions into each “addx”. How cool are we?

Part Two - Pretty Pixel Perfect

Now that we’ve tuned up the device and confirmed that it can run the instructions, it’s time to check that display. Obviously, the actual display is a ruin of sad electronics, but we can at least detect which pixels the CPU tries to light up and read the display output directly. Lets do that.

use std::fmt::{Display, Formatter, Result as FmtResult};

/// Solve Day 10, Part 2
fn solve(input: &[Instruction]) -> String {
    // Boot up a new model of device and run all the instructions on it.
    let mut device = Device::new();
    input.iter().for_each(|instruction| device.execute(instruction));

    // Collect the prettified pixel display into a string and return it
    PrettyPixels(device.pixels).to_string()
}

/// Represents a new-fangled computer with a display. We'll keep track of pixels
/// lit in a boolean array and worry about displaying them later.
struct Device {
    register: i32,
    cycle: usize,
    pixels: [bool; 240],
}

impl Device {
    fn new() -> Self {
        Device { register: 1, cycle: 0, pixels: [false; 240] }
    }

    // Execute a NOOP instruction. We'll leverage these instructions to update the
    // pixels based on the current sprite position.
    fn execute_noop(&mut self) {
        // Calculate the three-wide position of the sprite.
        let sprite_range = (self.register - 1)..=(self.register + 1);

        // The current line position is the cycle wrapped to 40-width lines. So, on
        // cycle 40, we've wrapped around to the first pixel of the second line.
        let line_pos = (self.cycle % 40) as i32;

        // If the current line position is within the sprite, set the corresponding
        // pixel in our array of pixels to `true`.
        if sprite_range.contains(&line_pos) {
            self.pixels[self.cycle] = true;
        }

        self.cycle += 1;
    }

    /// Execute an ADDX instruction. Once again, we leverage the NOOP instructions here
    /// to update the cycle count and the pixels. This time, we need to update the 
    /// register _after_ both NOOPs, since pixel drawing happens at the _beginning_
    /// of each cycle.
    fn execute_addx(&mut self, value: i32) {
        self.execute_noop();
        self.execute_noop();
        self.register += value;
    }

    /// Dispatch for instruction execution. Calls the appropriate execute method
    /// depending on the instruction provided.
    fn execute(&mut self, instr: &Instruction) {
        match instr {
            Instruction::Noop => self.execute_noop(),
            Instruction::Addx(v) => self.execute_addx(*v),
        }
    }
}

/// This is how we worry about displaying pixels. Using the newtype syntax, we can
/// implement a standard library trait on a (wrapped) standard library data structure.
/// In this case, we want to implement `Display` for our array of pixels so we can
/// convert it to a string that can show us the answer to part two.
struct PrettyPixels([bool; 240]);

impl Display for PrettyPixels {
    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
        for (idx, pixel) in self.0.iter().enumerate() {
            // Wrap the pixel lines to a width of 40 characters
            if (idx % 40 == 0) && idx > 0 { writeln!(f)?; }

            // If the pixel is lit, print a '#', other wise print a space
            let glyph = if *pixel { "#" } else { " " };
            write!(f, "{glyph}")?;
        }

        write!(f, "") // Finish the print results
    }
}

Enter fullscreen mode Exit fullscreen mode

Do you know what I really like about puzzles like this one? There’s no possible way to look at your output and not know with 100% accuracy whether or not it’s correct. The odds of actually displaying characters that aren’t the right answer is preposterously low. So, if you see characters instead of randomly placed pixels, you’re good!

Wrap Up

No real curveballs today, other than mixing up the timing on those instructions. The fact that the signal strength was detected during the cycle, while the pixels were drawn at the beginning of each cycle meant that the approach between parts one and two needed to change in subtle ways that could easily lead to bugs. Thankfully, I definitely hit all those bugs, but they were pretty obvious thanks to the garbled display output. I also appreciated the format of the example output, which made it pretty easy to tell if you were lighting up pixels correctly. The fact that Eric Wastl took the time to create a set of instructions that produced a nice diagnostic output is most appreciated!

Top comments (0)