The elves disappear, the communication system on the handheld device has a big crack in its screen. Today's challenge is to find a replacement for the screen based on cathode-ray technology. The device also has a simple CPU. Both screen and CPU work at a constant rate (cycles).
The CPU has a single register X which starts at 1. The CPU only supports two instructions,
addx Vto increase the value in registerXby valueV, the instructions takes two cycles to completenoopis a no op instruction & takes one cycle to complete
It is advised to check register X throughout execution of the list of given instructions,
in particular the signal strength at certain cycles, e.g. 20, 60, 100, 140, 180, 220.
Part 1
The goal is to find the signal strengths at the given intervals. The separate factors are calculated by
value in register X multiplied with the interval cycle, e.g. 20 * 21 = 420. All these factors
are then summed up to a final result.
Today we are using nom to parse the instructions from the input file.
The format of the instructions is as follows:
noop
addx 3
addx -5
The addx instruction can also take negative numbers.
The nom crate is a parser combinator framework, it analyzes the input string and can be used to map it to useful types.
use nom::{
branch::alt, bytes::complete::tag, character::complete::newline, combinator::map,
multi::separated_list1, sequence::preceded, IResult,
};
#[derive(Debug)]
enum Instruction {
Noop,
Add(i32),
}
impl Instruction {
pub fn cycles(&self) -> u32 {
match self {
Instruction::Noop => 1,
Instruction::Add(_) => 2,
}
}
pub fn parse(input: &str) -> IResult<&str, Self> {
alt((
map(tag("noop"), |_| Instruction::Noop),
map(preceded(tag("addx "), nom::character::complete::i32), |n| {
Instruction::Add(n)
}),
))(input)
}
}
fn parse(input: &str) -> Vec<Instruction> {
let (_, instructions) = separated_list1(newline, Instruction::parse)(input).unwrap();
instructions
}
The nom combinators usually have a similar function signature with:
fn parse(input: &str) -> IResult<&str, A> {
combinators(...)(input)
}
where the return type is a tuple of (&str, A). The &str type is the remainder of the input string to parse, while A is a type that is mapped into, in the case above it is the Instruction enum.
Function alt tests multiple combinators until one of its branches matches the pattern. Function tag recognizes a specific input pattern (e.g. noop) & map takes the parsed string to map it into a different type. The documentation is a good place to learn which combinators exist and how they can be used.
The example input is the same size as the real given input, therefore it's also loaded via the include_str! macro inside the test module.
fn part1(instructions: &[Instruction]) -> usize {
todo!()
}
#[cfg(test)]
mod tests {
use crate::*;
const INPUT: &str = include_str!("test.txt");
#[test]
fn check_part1() {
assert_eq!(13140, part1(&parse(INPUT)));
}
}
Currently the test will fail. Time to emulate the new video system.
#[derive(Debug)]
struct VideoSystem {
start_interval: u32,
interval: u32,
}
impl VideoSystem {
pub fn new(start_interval: u32, interval: u32) -> Self {
Self {
start_interval,
interval,
}
}
}
The VideoSystem struct has two fields, start_interval to denote the starting cycle, interval is to know when to take signals from the register. All intervals are 40 cycles long, while the first measurement is taken at cycle 20.
impl VideoSystem {
// 👇 new function to run all instructions
pub fn run(&self, instructions: &[Instruction]) -> Vec<(i32, i32)> {
todo!()
}
}
fn part1(instructions: &[Instruction]) -> u64 {
let video_system = VideoSystem::new(20, 40);
let strengths = video_system.run(instructions);
strengths
.iter()
.map(|(cycle, value)| *cycle * *value)
.sum::<u64>()
}
The part1 function is fairly straightforward, it sets up the VideoSystem and runs all instructions. The return type of run is a tuple
of interval cycle & signal strength at that cycle.
Now comes the interesting part, to execute all instructions and take the signal strengths at specific cycles.
pub fn run(&self, instructions: &[Instruction]) -> Vec<(i32, i32)> {
let mut signal_strengths = Vec::new();
let mut cycle_count = 0;
let mut interval = self.start_interval;
let mut x = 1;
for instruction in instructions {
for _ in 0..instruction.cycles() {
cycle_count += 1;
interval += 1;
if interval >= self.interval {
interval = 0;
signal_strengths.push((cycle_count, x));
}
}
if let Instruction::Add(value) = instruction {
x += *value;
}
}
signal_strengths
}
A short break down of this method, signal_strengths is the list of taken signal strengths at certain cycles.
The interval variable is initialized to the start interval, e.g. 20. Once it passes the number of cycles for one interval
it is reset to 0 & the current signal strength in register x is stored.
The addx instruction updates the register. The inner for loop waits for the number of cycles the instruction takes.
With this in place the test should pass now, running the program should also output the first solution.
fn main() {
let instructions = parse(include_str!("input.txt"));
println!("Part 1: {}", part1(&instructions));
}
Part 2
The second part gets more interesting and also explains what the instructions are used for.
The screen size is 40 characters wide and 6 characters high.
The video system uses the instructions to update the CRT display, where register X controls the horizontal position of a sprite.
Every interval wraps the cursor around to the next line.
By carefully timing instructions and CRT drawing the output is an ASCII art display of eight capital letters.
A pixel is rendered at a position when the sprite, consisting of ###, is positioned such that one of its three pixels is the pixel currently
being drawn. Then the screen renders a lit pixel (#), otherwise leaves the pixel dark (.). The sprite is controlled
by the X register and moves accordingly. The beam is similar to a cathode ray that moves horizontally.
impl VideoSystem {
pub fn display(&self, instructions: &[Instruction]) -> String {
let mut output = String::new();
let mut beam = self.start_interval as i32;
let mut sprite = 1;
for instruction in instructions {
for _ in 0..instruction.cycles() {
beam += 1;
// When the sprite is covering the beam position render the pixel
if sprite <= beam && beam < sprite + 3 {
output.push('#');
} else {
output.push('.');
}
if beam >= self.interval as i32 {
beam = 0;
output.push('\n');
}
}
if let Instruction::Add(value) = instruction {
sprite += *value;
}
}
output
}
}
fn part2(instructions: &[Instruction]) -> String {
let video_system = VideoSystem::new(0, 40);
video_system.display(&instructions)
}
fn main() -> anyhow::Result<()> {
let instructions = parse(include_str!("input.txt"));
println!("Part 1: {}", part1(&instructions));
println!("Part 2:\n{}", part2(&instructions));
}
#[cfg(test)]
mod tests {
#[test]
fn check_part2() {
let expected = "##..##..##..##..##..##..##..##..##..##..\n\
###...###...###...###...###...###...###.\n\
####....####....####....####....####....\n\
#####.....#####.....#####.....#####.....\n\
######......######......######......####\n\
#######.......#######.......#######.....\n";
let instructions = parse(INPUT);
assert_eq!(expected, part2(&instructions));
}
}
The VideoSystem#display method works similar to the run, but instead updates the horizontal beam. The output string
then mimicks the content of the CRT display, consisting of # & . in a 40 x 6 grid.
The generated output for the given input in ASCII is
####..##..###...##....##.####...##.####.
...#.#..#.#..#.#..#....#.#.......#....#.
..#..#....###..#..#....#.###.....#...#..
.#...#....#..#.####....#.#.......#..#...
#....#..#.#..#.#..#.#..#.#....#..#.#....
####..##..###..#..#..##..#.....##..####.
To make it easier to read the letters the . character can also be replaced with a whitespace. The solution is ZCBAJFJZ.