Actually test part two, why not

2022/Cargo.toml

@@ -6,6 +6,7 @@ edition = "2021"
 # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
 
 [dependencies]
+ahash = "0.8.2"
 anyhow = "1.0.66"
 clap = { version = "4.0.19", features = ["derive"] }
 itertools = "0.10.5"

2022/benches/days.rs

@@ -10,34 +10,31 @@ use criterion::Criterion;
 /// Number of days we have an implementation to benchmark
 const DAYS_IMPLEMENTED: u8 = 25;
 
-fn read_input(day: u8) -> Vec<u8> {
+fn read_input(day: u8) -> std::io::Result<Vec<u8>> {
     let input_path = format!("inputs/{:02}.txt", day);
 
     let mut buffer = Vec::new();
-    File::open(input_path)
-        .expect("Failed to open input file")
-        .read_to_end(&mut buffer)
-        .expect("Failed to read input file");
+    File::open(input_path)?.read_to_end(&mut buffer)?;
 
-    buffer
+    Ok(buffer)
 }
 
 pub fn benchmark_days(c: &mut Criterion) {
     for day in 1..=DAYS_IMPLEMENTED {
-        let input = read_input(day);
+        if let Ok(input) = read_input(day) {
+            let part1 = get_implementation(day, false).unwrap();
 
-        let part1 = get_implementation(day, false).unwrap();
-
-        c.bench_with_input(BenchmarkId::new("part1", day), &input, |b, i| {
-            b.iter(|| part1(i));
-        });
-
-        if day < 25 {
-            let part2 = get_implementation(day, true).unwrap();
-
-            c.bench_with_input(BenchmarkId::new("part2", day), &input, |b, i| {
-                b.iter(|| part2(i));
+            c.bench_with_input(BenchmarkId::new("part1", day), &input, |b, i| {
+                b.iter(|| part1(i));
             });
+
+            if day < 25 {
+                let part2 = get_implementation(day, true).unwrap();
+
+                c.bench_with_input(BenchmarkId::new("part2", day), &input, |b, i| {
+                    b.iter(|| part2(i));
+                });
+            }
         }
     }
 }

2022/inputs/10.txt

@@ -0,0 +1,140 @@
+noop
+addx 5
+noop
+noop
+noop
+addx 1
+addx 2
+addx 5
+addx 2
+addx 5
+noop
+noop
+noop
+noop
+noop
+addx -12
+addx 18
+addx -1
+noop
+addx 3
+addx 5
+addx -5
+addx 7
+noop
+addx -36
+addx 18
+addx -16
+noop
+noop
+noop
+addx 5
+addx 2
+addx 5
+addx 2
+addx 13
+addx -6
+addx -4
+addx 5
+addx 2
+addx 4
+addx -3
+addx 2
+noop
+addx 3
+addx 2
+addx 5
+addx -40
+addx 25
+addx -22
+addx 25
+addx -21
+addx 5
+addx 3
+noop
+addx 2
+addx 19
+addx -10
+addx -4
+noop
+addx -4
+addx 7
+noop
+addx 3
+addx 2
+addx 5
+addx 2
+addx -26
+addx 27
+addx -36
+noop
+noop
+noop
+noop
+addx 4
+addx 6
+noop
+addx 12
+addx -11
+addx 2
+noop
+noop
+noop
+addx 5
+addx 5
+addx 2
+noop
+noop
+addx 1
+addx 2
+addx 5
+addx 2
+addx 1
+noop
+noop
+addx -38
+noop
+addx 9
+addx -4
+noop
+noop
+addx 7
+addx 10
+addx -9
+addx 2
+noop
+addx -9
+addx 14
+addx 5
+addx 2
+addx -24
+addx 25
+addx 2
+addx 5
+addx 2
+addx -30
+addx 31
+addx -38
+addx 7
+noop
+noop
+noop
+addx 1
+addx 21
+addx -16
+addx 8
+addx -4
+addx 2
+addx 3
+noop
+noop
+addx 5
+addx -2
+addx 5
+addx 3
+addx -1
+addx -1
+addx 4
+addx 5
+addx -38
+noop

2022/src/day08.rs

@@ -1,5 +1,3 @@
-use std::cmp::Ordering;
-
 use anyhow::Context;
 use anyhow::Result;
 
@@ -65,39 +63,19 @@ pub fn part1(input: &[u8]) -> Result<String> {
 fn scenery<'a>(
     values: impl IntoIterator<Item = &'a u8>,
     visible: impl IntoIterator<Item = &'a mut usize>,
-    tree_stack: &mut Vec<(usize, u8)>,
 ) {
-    tree_stack.clear();
+    let mut last_seen = [0; 10];
 
     for (i, (&val, score)) in values.into_iter().zip(visible).enumerate() {
-        scenery_helper(i, tree_stack, val, score);
-    }
-}
+        let val = val - b'0';
+        let visible = i - last_seen[val as usize];
 
-fn scenery_helper(i: usize, tree_stack: &mut Vec<(usize, u8)>, val: u8, score: &mut usize) {
-    if i > 0 {
-        let mut first = 0;
-
-        while let Some((pos, other)) = tree_stack.pop() {
-            match other.cmp(&val) {
-                Ordering::Less => (),
-                Ordering::Equal => {
-                    first = pos;
-                    break;
-                }
-                Ordering::Greater => {
-                    tree_stack.push((pos, other));
-                    first = pos;
-                    break;
-                }
-            }
+        if i > 0 {
+            *score *= visible;
+            last_seen[..=(val as usize)].fill(i);
+        } else {
+            *score = 0;
         }
-
-        tree_stack.push((i, val));
-
-        *score *= i - first;
-    } else {
-        *score = 0;
     }
 }
 
@@ -110,18 +88,15 @@ pub fn part2(input: &[u8]) -> Result<String> {
 
     let mut score = vec![1; width * height];
 
-    let mut tree_stack = Vec::with_capacity(10);
-
     // Horizontal striping
     for (y, row) in input.chunks_exact(width + 1).enumerate() {
         // First, left to right
-        scenery(&row[..width], &mut score[(y * width)..], &mut tree_stack);
+        scenery(&row[..width], &mut score[(y * width)..]);
 
         // Then right to left
         scenery(
             row[..width].iter().rev(),
             score[(y * width)..(y * width + width)].iter_mut().rev(),
-            &mut tree_stack,
         );
     }
 
@@ -131,14 +106,12 @@ pub fn part2(input: &[u8]) -> Result<String> {
         scenery(
             input[x..].iter().step_by(width + 1),
             score[x..].iter_mut().step_by(width),
-            &mut tree_stack,
         );
 
         // Bottom to top
         scenery(
             input[x..].iter().step_by(width + 1).rev(),
             score[x..].iter_mut().step_by(width).rev(),
-            &mut tree_stack,
         )
     }
 

2022/src/day09.rs

@@ -1,9 +1,161 @@
+use std::ops::Add;
+use std::ops::Index;
+use std::ops::IndexMut;
+use std::ops::Sub;
+
+use ahash::AHashSet;
 use anyhow::Result;
+use nom::bytes::complete::tag;
+use nom::bytes::complete::take;
+use nom::character::complete::newline;
+use nom::combinator::map_res;
+use nom::multi::many0;
+use nom::sequence::separated_pair;
+use nom::sequence::terminated;
+use nom::IResult;
 
-pub fn part1(_input: &[u8]) -> Result<String> {
-    anyhow::bail!("not implemented")
+use crate::common::parse_input;
+
+#[derive(Copy, Clone)]
+enum Direction {
+    Up,
+    Left,
+    Right,
+    Down,
 }
 
-pub fn part2(_input: &[u8]) -> Result<String> {
-    anyhow::bail!("not implemented")
+impl Direction {
+    fn vec_for(self) -> Vec2 {
+        Vec2(match self {
+            Direction::Up => [0, -1],
+            Direction::Left => [1, 0],
+            Direction::Right => [-1, 0],
+            Direction::Down => [0, 1],
+        })
+    }
+}
+
+impl TryFrom<u8> for Direction {
+    type Error = anyhow::Error;
+
+    fn try_from(value: u8) -> Result<Self, Self::Error> {
+        match value {
+            b'U' => Ok(Direction::Up),
+            b'L' => Ok(Direction::Left),
+            b'R' => Ok(Direction::Right),
+            b'D' => Ok(Direction::Down),
+            b => anyhow::bail!("Invalid direction '{b}'"),
+        }
+    }
+}
+
+fn parse_moves(input: &[u8]) -> IResult<&[u8], Vec<(Direction, u32)>> {
+    many0(terminated(
+        separated_pair(
+            map_res(take(1usize), |bs: &[u8]| Direction::try_from(bs[0])),
+            tag(" "),
+            nom::character::complete::u32,
+        ),
+        newline,
+    ))(input)
+}
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+struct Vec2(pub [i32; 2]);
+
+impl Add<Self> for Vec2 {
+    type Output = Self;
+
+    fn add(self, rhs: Self) -> Self::Output {
+        Self([self[0] + rhs[0], self[1] + rhs[1]])
+    }
+}
+
+impl Sub<Self> for Vec2 {
+    type Output = Self;
+
+    fn sub(self, rhs: Self) -> Self::Output {
+        Self([self[0] - rhs[0], self[1] - rhs[1]])
+    }
+}
+
+impl Index<usize> for Vec2 {
+    type Output = i32;
+
+    #[inline]
+    fn index(&self, index: usize) -> &Self::Output {
+        &self.0[index]
+    }
+}
+
+impl IndexMut<usize> for Vec2 {
+    #[inline]
+    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
+        &mut self.0[index]
+    }
+}
+
+fn part_generic<const N: usize>(input: &[u8]) -> Result<String> {
+    let moves = parse_input(input, parse_moves)?;
+
+    let mut head_pos = Vec2([0, 0]);
+    let mut tails = [head_pos; N];
+
+    let mut visited = AHashSet::new();
+    visited.insert(head_pos);
+
+    for (direction, steps) in moves {
+        let step = direction.vec_for();
+
+        for _ in 0..steps {
+            head_pos = head_pos + step;
+
+            let mut ref_pos = head_pos;
+
+            for tail_pos in &mut tails {
+                let delta = ref_pos - *tail_pos;
+
+                if delta[0].abs() <= 1 && delta[1].abs() <= 1 {
+                    break;
+                }
+
+                let step = Vec2([delta[0].signum(), delta[1].signum()]);
+
+                *tail_pos = *tail_pos + step;
+
+                ref_pos = *tail_pos;
+            }
+
+            visited.insert(*tails.last().unwrap());
+        }
+    }
+
+    Ok(visited.len().to_string())
+}
+
+pub fn part1(input: &[u8]) -> Result<String> {
+    part_generic::<1>(input)
+}
+
+pub fn part2(input: &[u8]) -> Result<String> {
+    part_generic::<9>(input)
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    const SAMPLE: &[u8] = include_bytes!("samples/09.txt");
+    const SAMPLE_LARGE: &[u8] = include_bytes!("samples/09.large.txt");
+
+    #[test]
+    fn sample_part1() {
+        assert_eq!(part1(SAMPLE).unwrap(), "13");
+    }
+
+    #[test]
+    fn sample_part2() {
+        assert_eq!(part2(SAMPLE).unwrap(), "1");
+        assert_eq!(part2(SAMPLE_LARGE).unwrap(), "36");
+    }
 }

2022/src/day10.rs

@@ -1,9 +1,130 @@
 use anyhow::Result;
+use nom::branch::alt;
+use nom::bytes::complete::tag;
+use nom::character::complete::newline;
+use nom::combinator::iterator;
+use nom::combinator::map;
+use nom::sequence::preceded;
+use nom::sequence::terminated;
+use nom::IResult;
 
-pub fn part1(_input: &[u8]) -> Result<String> {
-    anyhow::bail!("not implemented")
+#[derive(Copy, Clone)]
+enum Instruction {
+    AddX(i32),
+    Noop,
 }
 
-pub fn part2(_input: &[u8]) -> Result<String> {
-    anyhow::bail!("not implemented")
+impl Instruction {
+    #[inline]
+    pub fn cycles(self) -> i32 {
+        match self {
+            Instruction::AddX(_) => 2,
+            Instruction::Noop => 1,
+        }
+    }
+
+    #[inline]
+    pub fn execute(self, x: &mut i32, cycle: &mut i32) {
+        *cycle += self.cycles();
+
+        if let Instruction::AddX(v) = self {
+            *x += v;
+        }
+    }
+}
+
+fn parse_instruction(input: &[u8]) -> IResult<&[u8], Instruction> {
+    terminated(
+        alt((
+            map(tag("noop"), |_| Instruction::Noop),
+            map(preceded(tag("addx "), nom::character::complete::i32), |v| {
+                Instruction::AddX(v)
+            }),
+        )),
+        newline,
+    )(input)
+}
+
+pub fn part1(input: &[u8]) -> Result<String> {
+    let mut x = 1;
+    // Count from one like a scrub
+    let mut cycle = 1;
+
+    let mut input_it = iterator(input, parse_instruction);
+
+    let mut total = 0;
+
+    for instruction in &mut input_it {
+        let old_cycle = cycle;
+        let old_x = x;
+
+        instruction.execute(&mut x, &mut cycle);
+
+        if old_cycle % 40 < 20 && cycle % 40 >= 20 {
+            let to_report = if cycle % 40 == 20 { x } else { old_x };
+
+            let checkpoint = cycle / 20 * 20;
+            total += to_report * checkpoint;
+        }
+
+        if cycle >= 220 {
+            return Ok(total.to_string());
+        }
+    }
+
+    anyhow::bail!("out of instructions")
+}
+
+pub fn part2(input: &[u8]) -> Result<String> {
+    let mut x = 1;
+    let mut input_it = iterator(input, parse_instruction);
+    let mut input_it = (&mut input_it).peekable();
+
+    let mut output = String::with_capacity(6 * (40 + 1));
+
+    let mut cpu_cycle = 0;
+
+    for crt_cycle in 1..=240 {
+        if let Some(instruction) = input_it.next_if(|i| cpu_cycle + i.cycles() < crt_cycle) {
+            instruction.execute(&mut x, &mut cpu_cycle);
+        }
+
+        let beam_pos = (crt_cycle + 39) % 40;
+
+        if (beam_pos - x).abs() <= 1 {
+            output.push('#');
+        } else {
+            output.push(' ');
+        }
+
+        if crt_cycle % 40 == 0 {
+            output.push('\n');
+        }
+    }
+
+    Ok(output)
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    const SAMPLE: &[u8] = include_bytes!("samples/10.txt");
+
+    #[test]
+    fn sample_part1() {
+        assert_eq!(part1(SAMPLE).unwrap(), "13140");
+    }
+
+    #[test]
+    fn sample_part2() {
+        let answer = "##  ##  ##  ##  ##  ##  ##  ##  ##  ##  
+###   ###   ###   ###   ###   ###   ### 
+####    ####    ####    ####    ####    
+#####     #####     #####     #####     
+######      ######      ######      ####
+#######       #######       #######     \n";
+
+        assert_eq!(part2(SAMPLE).unwrap(), answer);
+    }
 }

2022/src/samples/09.large.txt

@@ -0,0 +1,8 @@
+R 5
+U 8
+L 8
+D 3
+R 17
+D 10
+L 25
+U 20

2022/src/samples/09.txt

@@ -0,0 +1,8 @@
+R 4
+U 4
+L 3
+D 1
+R 4
+D 1
+L 5
+R 2

2022/src/samples/10.txt

@@ -0,0 +1,146 @@
+addx 15
+addx -11
+addx 6
+addx -3
+addx 5
+addx -1
+addx -8
+addx 13
+addx 4
+noop
+addx -1
+addx 5
+addx -1
+addx 5
+addx -1
+addx 5
+addx -1
+addx 5
+addx -1
+addx -35
+addx 1
+addx 24
+addx -19
+addx 1
+addx 16
+addx -11
+noop
+noop
+addx 21
+addx -15
+noop
+noop
+addx -3
+addx 9
+addx 1
+addx -3
+addx 8
+addx 1
+addx 5
+noop
+noop
+noop
+noop
+noop
+addx -36
+noop
+addx 1
+addx 7
+noop
+noop
+noop
+addx 2
+addx 6
+noop
+noop
+noop
+noop
+noop
+addx 1
+noop
+noop
+addx 7
+addx 1
+noop
+addx -13
+addx 13
+addx 7
+noop
+addx 1
+addx -33
+noop
+noop
+noop
+addx 2
+noop
+noop
+noop
+addx 8
+noop
+addx -1
+addx 2
+addx 1
+noop
+addx 17
+addx -9
+addx 1
+addx 1
+addx -3
+addx 11
+noop
+noop
+addx 1
+noop
+addx 1
+noop
+noop
+addx -13
+addx -19
+addx 1
+addx 3
+addx 26
+addx -30
+addx 12
+addx -1
+addx 3
+addx 1
+noop
+noop
+noop
+addx -9
+addx 18
+addx 1
+addx 2
+noop
+noop
+addx 9
+noop
+noop
+noop
+addx -1
+addx 2
+addx -37
+addx 1
+addx 3
+noop
+addx 15
+addx -21
+addx 22
+addx -6
+addx 1
+noop
+addx 2
+addx 1
+noop
+addx -10
+noop
+noop
+addx 20
+addx 1
+addx 2
+addx 2
+addx -6
+addx -11
+noop
+noop
+noop