Refactor out common code

2022/Cargo.toml

@@ -6,10 +6,12 @@ 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"
 nom = "7.1.1"
+strength_reduce = "0.2.4"
 
 [dev-dependencies]
 criterion = "0.4.0"

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/inputs/11.txt

@@ -0,0 +1,55 @@
+Monkey 0:
+  Starting items: 84, 66, 62, 69, 88, 91, 91
+  Operation: new = old * 11
+  Test: divisible by 2
+    If true: throw to monkey 4
+    If false: throw to monkey 7
+
+Monkey 1:
+  Starting items: 98, 50, 76, 99
+  Operation: new = old * old
+  Test: divisible by 7
+    If true: throw to monkey 3
+    If false: throw to monkey 6
+
+Monkey 2:
+  Starting items: 72, 56, 94
+  Operation: new = old + 1
+  Test: divisible by 13
+    If true: throw to monkey 4
+    If false: throw to monkey 0
+
+Monkey 3:
+  Starting items: 55, 88, 90, 77, 60, 67
+  Operation: new = old + 2
+  Test: divisible by 3
+    If true: throw to monkey 6
+    If false: throw to monkey 5
+
+Monkey 4:
+  Starting items: 69, 72, 63, 60, 72, 52, 63, 78
+  Operation: new = old * 13
+  Test: divisible by 19
+    If true: throw to monkey 1
+    If false: throw to monkey 7
+
+Monkey 5:
+  Starting items: 89, 73
+  Operation: new = old + 5
+  Test: divisible by 17
+    If true: throw to monkey 2
+    If false: throw to monkey 0
+
+Monkey 6:
+  Starting items: 78, 68, 98, 88, 66
+  Operation: new = old + 6
+  Test: divisible by 11
+    If true: throw to monkey 2
+    If false: throw to monkey 5
+
+Monkey 7:
+  Starting items: 70
+  Operation: new = old + 7
+  Test: divisible by 5
+    If true: throw to monkey 1
+    If false: throw to monkey 3

2022/inputs/12.txt

@@ -0,0 +1,41 @@
+abcccccccaaaaaccccaaaaaaaccccccccccccccccccccccccccccccccccccaaaaa
+abaacccaaaaaaccccccaaaaaaaaaaaaaccccccccccccccccccccccccccccaaaaaa
+abaacccaaaaaaaccccaaaaaaaaaaaaaacccccccccccccaacccccccccccccaaaaaa
+abaacccccaaaaaacaaaaaaaaaaaaaaaacccccccccccccaacccccccccccccacacaa
+abaccccccaaccaacaaaaaaaaaacccaacccccccccccccaaacccccccccccccccccaa
+abcccccccaaaacccaaaaaaaaacccccccccccccaaacccaaacccccccccccccccccaa
+abccccccccaaaccccccccaaaacccccccccccccaaaaacaaaccacacccccccccccccc
+abccccccccaaacaaacccccaaacccccccccccccaaaaaaajjjjjkkkcccccaacccccc
+abcccccaaaaaaaaaacccccaaccccccccccciiiiiijjjjjjjjjkkkcaaaaaacccccc
+abcccccaaaaaaaaacccccccccccccccccciiiiiiijjjjjjjrrkkkkaaaaaaaacccc
+abcccccccaaaaaccccccccccccccccccciiiiiiiijjjjrrrrrppkkkaaaaaaacccc
+abcccaaccaaaaaacccccccccccaacaaciiiiqqqqqrrrrrrrrpppkkkaaaaaaacccc
+abccaaaaaaaaaaaaccccacccccaaaaaciiiqqqqqqrrrrrruuppppkkaaaaacccccc
+abcccaaaaaaacaaaacaaacccccaaaaaahiiqqqqtttrrruuuuupppkkaaaaacccccc
+abcaaaaaaaccccaaaaaaacccccaaaaaahhqqqtttttuuuuuuuuuppkkkccaacccccc
+abcaaaaaaaaccccaaaaaacccccaaaaaahhqqqtttttuuuuxxuuuppkklcccccccccc
+abcaaaaaaaacaaaaaaaaaaacccccaaachhhqqtttxxxuuxxyyuuppllllccccccccc
+abcccaaacaccaaaaaaaaaaaccccccccchhhqqtttxxxxxxxyuupppplllccccccccc
+abaacaacccccaaaaaaaaaaaccccccccchhhqqtttxxxxxxyyvvvpppplllcccccccc
+abaacccccccccaaaaaaacccccccccccchhhpppttxxxxxyyyvvvvpqqqlllccccccc
+SbaaccccccaaaaaaaaaaccccccccccchhhppptttxxxEzzyyyyvvvqqqlllccccccc
+abaaaaccccaaaaaaaaacccccccccccchhhpppsssxxxyyyyyyyyvvvqqqlllcccccc
+abaaaacccccaaaaaaaacccccccccccgggpppsssxxyyyyyyyyyvvvvqqqlllcccccc
+abaaacccaaaacaaaaaaaccccccccccgggpppsswwwwwwyyyvvvvvvqqqllllcccccc
+abaaccccaaaacaaccaaaacccccccccgggppssswwwwwwyyywvvvvqqqqmmmccccccc
+abaaccccaaaacaaccaaaaccaaaccccggpppssssswwswwyywvqqqqqqmmmmccccccc
+abcccccccaaacccccaaacccaaacaccgggpppssssssswwwwwwrqqmmmmmccccccccc
+abcccccccccccccccccccaacaaaaacgggppooosssssrwwwwrrrmmmmmcccccccccc
+abcccccccccccccccccccaaaaaaaacggggoooooooorrrwwwrrnmmmdddccaaccccc
+abaccccccccccccaacccccaaaaaccccggggoooooooorrrrrrrnmmddddcaaaccccc
+abaccccccccaaaaaaccccccaaaaaccccggfffffooooorrrrrnnndddddaaaaccccc
+abaacccccccaaaaaacccccaaaaaacccccffffffffoonrrrrrnnndddaaaaaaacccc
+abaaccccccccaaaaaaaccacaaaacccccccccffffffonnnnnnnndddaaaaaaaacccc
+abccccccccccaaaaaaaaaaaaaaaccccccccccccfffennnnnnnddddccaaaccccccc
+abcccccccccaaaaaaacaaaaaaaaaacccccccccccffeennnnnedddccccaaccccccc
+abcccccccccaaaaaaccaaaaaaaaaaaccccccccccaeeeeeeeeeedcccccccccccccc
+abccccccccccccaaaccaaaaaaaaaaaccccccccccaaaeeeeeeeecccccccccccccaa
+abcccccccaaccccccccaaaaaaaacccccccccccccaaaceeeeecccccccccccccccaa
+abaaccaaaaaaccccccccaaaaaaaacccccccccccccaccccaaacccccccccccaaacaa
+abaaccaaaaacccccaaaaaaaaaaacccccccccccccccccccccacccccccccccaaaaaa
+abaccaaaaaaaaccaaaaaaaaaaaaaacccccccccccccccccccccccccccccccaaaaaa

2022/src/common.rs

@@ -1,5 +1,7 @@
 //! Common helper utilities to all days
 
+use std::cmp::Ordering;
+
 use anyhow::Result;
 use nom::combinator::map;
 use nom::error::ErrorKind;
@@ -116,3 +118,57 @@ where
         (b, a)
     }
 }
+
+/// Some magic to get two mutable references into the same slice
+pub fn get_both<T>(slice: &mut [T], first: usize, second: usize) -> (&mut T, &mut T) {
+    match first.cmp(&second) {
+        Ordering::Greater => {
+            let (begin, end) = slice.split_at_mut(first);
+            (&mut end[0], &mut begin[second])
+        }
+        Ordering::Less => {
+            let (begin, end) = slice.split_at_mut(second);
+            (&mut begin[first], &mut end[0])
+        }
+        Ordering::Equal => panic!("Tried to get the same index twice {first}"),
+    }
+}
+
+#[derive(Default)]
+pub struct IndexSet(Vec<u32>);
+
+impl IndexSet {
+    pub fn with_capacity(capacity: usize) -> Self {
+        Self(Vec::with_capacity(
+            capacity / std::mem::size_of::<u32>() / 8,
+        ))
+    }
+
+    fn ensure_item(&mut self, item: usize) -> &mut u32 {
+        if self.0.len() <= item {
+            self.0.resize(item + 1, 0);
+        }
+
+        &mut self.0[item]
+    }
+
+    #[inline]
+    fn index(index: usize) -> (usize, u8) {
+        const PER_ENTRY: usize = 8 * std::mem::size_of::<u32>();
+
+        (index / PER_ENTRY, (index % PER_ENTRY) as u8)
+    }
+
+    pub fn insert(&mut self, index: usize) -> bool {
+        let (entry, pos) = Self::index(index);
+
+        let item = self.ensure_item(entry);
+
+        if *item & (1 << pos) != 0 {
+            false
+        } else {
+            *item |= 1 << pos;
+            true
+        }
+    }
+}

2022/src/day05.rs

@@ -1,5 +1,3 @@
-use std::cmp::Ordering;
-
 use anyhow::Result;
 use nom::branch::alt;
 use nom::bytes::complete::tag;
@@ -8,6 +6,7 @@ use nom::bytes::complete::take_until;
 use nom::character::complete::newline;
 use nom::combinator::map;
 use nom::combinator::opt;
+use nom::combinator::value;
 use nom::multi::fold_many1;
 use nom::multi::many1;
 use nom::sequence::delimited;
@@ -17,6 +16,7 @@ use nom::sequence::tuple;
 use nom::IResult;
 
 use crate::common::enumerate;
+use crate::common::get_both;
 use crate::common::parse_input;
 
 type Move = (usize, usize, usize);
@@ -32,7 +32,7 @@ fn parse_row<'a>(input: &'a [u8], stacks: &mut OwnedStacks) -> IResult<&'a [u8],
                     Some(v[0])
                 }),
                 // Or an empty stack into a None
-                map(tag("   "), |_| None),
+                value(None, tag("   ")),
             )),
             opt(tag(" ")),
         )),
@@ -91,21 +91,6 @@ fn parse_task(input: &[u8]) -> IResult<&[u8], (OwnedStacks, Vec<Move>)> {
     Ok((input, (stacks, moves)))
 }
 
-/// Some magic to get two mutable references into the same slice
-fn get_both(stacks: &mut [Vec<u8>], from: usize, to: usize) -> (&mut Vec<u8>, &mut Vec<u8>) {
-    match from.cmp(&to) {
-        Ordering::Greater => {
-            let (begin, end) = stacks.split_at_mut(from);
-            (&mut end[0], &mut begin[to])
-        }
-        Ordering::Less => {
-            let (begin, end) = stacks.split_at_mut(to);
-            (&mut begin[from], &mut end[0])
-        }
-        Ordering::Equal => panic!("Tried to stack from and to {from}"),
-    }
-}
-
 fn compute_answer(stacks: &mut [Vec<u8>]) -> Result<String> {
     let mut result = String::with_capacity(stacks.len());
 

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,131 @@
 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::combinator::value;
+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((
+            value(Instruction::Noop, tag("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/day11.rs

@@ -1,9 +1,189 @@
 use anyhow::Result;
+use nom::branch::alt;
+use nom::bytes::complete::tag;
+use nom::bytes::complete::take;
+use nom::character::complete::digit1;
+use nom::character::complete::newline;
+use nom::combinator::map;
+use nom::combinator::map_res;
+use nom::combinator::value;
+use nom::multi::separated_list0;
+use nom::multi::separated_list1;
+use nom::sequence::delimited;
+use nom::sequence::preceded;
+use nom::sequence::separated_pair;
+use nom::sequence::tuple;
+use nom::IResult;
+use strength_reduce::StrengthReducedU64;
 
-pub fn part1(_input: &[u8]) -> Result<String> {
-    anyhow::bail!("not implemented")
+use crate::common::parse_input;
+
+#[derive(Debug, Copy, Clone)]
+enum Operation {
+    Mul(u64),
+    Add(u64),
+    Square,
 }
 
-pub fn part2(_input: &[u8]) -> Result<String> {
-    anyhow::bail!("not implemented")
+impl Operation {
+    fn transform(self, worry: u64) -> u64 {
+        match self {
+            Operation::Mul(val) => worry * val,
+            Operation::Add(val) => worry + val,
+            Operation::Square => worry * worry,
+        }
+    }
+}
+
+#[derive(Debug)]
+struct Monkey {
+    items: Vec<u64>,
+    operation: Operation,
+    test_mod: StrengthReducedU64,
+    targets: [usize; 2],
+    inspected: usize,
+}
+
+impl Monkey {
+    fn handle_items(&mut self, drains: &mut [Vec<u64>; 2]) {
+        self.inspected += self.items.len();
+
+        for item in self.items.drain(..) {
+            let mut new_val = self.operation.transform(item);
+            // Miraculously get less worried
+            new_val /= 3;
+
+            drains[(new_val % self.test_mod == 0) as usize].push(new_val);
+        }
+    }
+
+    fn handle_items2(&mut self, drains: &mut [Vec<u64>], mod_base: StrengthReducedU64) {
+        self.inspected += self.items.len();
+
+        for item in self.items.drain(..) {
+            let mut new_val = self.operation.transform(item);
+            // Modular arithmetic is a good way to get less worried
+            new_val = new_val % mod_base;
+
+            drains[(new_val % self.test_mod == 0) as usize].push(new_val);
+        }
+    }
+}
+
+fn parse_operation(input: &[u8]) -> IResult<&[u8], Operation> {
+    preceded(
+        tag("new = old "),
+        alt((
+            map_res(
+                separated_pair(take(1usize), tag(" "), nom::character::complete::u64),
+                |(op, val): (&[u8], u64)| match op[0] {
+                    b'*' => Ok(Operation::Mul(val)),
+                    b'+' => Ok(Operation::Add(val)),
+                    _ => Err(anyhow::anyhow!("Invalid operation {op:?}")),
+                },
+            ),
+            value(Operation::Square, tag("* old")),
+        )),
+    )(input)
+}
+
+fn parse_monkey(input: &[u8]) -> IResult<&[u8], Monkey> {
+    use nom::character::complete::u64;
+
+    map(
+        preceded(
+            // Skip the useless header line
+            tuple((tag("Monkey "), digit1, tag(":\n"))),
+            // Parse the actual interesting bits of the monkey
+            tuple((
+                // Parse the starting items
+                delimited(
+                    tag("  Starting items: "),
+                    separated_list1(tag(", "), u64),
+                    newline,
+                ),
+                // Parse operation
+                delimited(tag("  Operation: "), parse_operation, newline),
+                // Parse the test
+                delimited(tag("  Test: divisible by "), u64, newline),
+                // Parse both cases
+                delimited(tag("    If true: throw to monkey "), u64, newline),
+                delimited(tag("    If false: throw to monkey "), u64, newline),
+            )),
+        ),
+        |(items, operation, test_mod, if_true, if_false)| Monkey {
+            items,
+            operation,
+            test_mod: StrengthReducedU64::new(test_mod),
+            targets: [if_false as usize, if_true as usize],
+            inspected: 0,
+        },
+    )(input)
+}
+
+fn parse_monkeys(input: &[u8]) -> IResult<&[u8], Vec<Monkey>> {
+    separated_list0(newline, parse_monkey)(input)
+}
+
+fn format_result(mut monkeys: Vec<Monkey>) -> Result<String> {
+    monkeys.sort_by(|a, b| b.inspected.cmp(&a.inspected));
+
+    let result: usize = monkeys[0].inspected * monkeys[1].inspected;
+
+    Ok(result.to_string())
+}
+
+pub fn part1(input: &[u8]) -> Result<String> {
+    let mut monkeys = parse_input(input, parse_monkeys)?;
+    let mut drains = [Vec::new(), Vec::new()];
+
+    for _ in 0..20 {
+        for i in 0..monkeys.len() {
+            monkeys[i].handle_items(&mut drains);
+
+            for (j, drain) in drains.iter_mut().enumerate() {
+                let target = monkeys[i].targets[j];
+                monkeys[target].items.append(drain);
+            }
+        }
+    }
+
+    format_result(monkeys)
+}
+
+pub fn part2(input: &[u8]) -> Result<String> {
+    let mut monkeys = parse_input(input, parse_monkeys)?;
+    let mut drains = [Vec::new(), Vec::new()];
+
+    let mod_base = StrengthReducedU64::new(monkeys.iter().map(|m| m.test_mod.get()).product());
+
+    for _ in 0..10000 {
+        for i in 0..monkeys.len() {
+            monkeys[i].handle_items2(&mut drains, mod_base);
+
+            for (j, drain) in drains.iter_mut().enumerate() {
+                let target = monkeys[i].targets[j];
+                monkeys[target].items.append(drain);
+            }
+        }
+    }
+
+    format_result(monkeys)
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    const SAMPLE: &[u8] = include_bytes!("samples/11.txt");
+
+    #[test]
+    fn sample_part1() {
+        assert_eq!(part1(SAMPLE).unwrap(), "10605");
+    }
+
+    #[test]
+    fn sample_part2() {
+        assert_eq!(part2(SAMPLE).unwrap(), "2713310158");
+    }
 }

2022/src/day12.rs

@@ -1,9 +1,98 @@
+use std::collections::VecDeque;
+
+use anyhow::Context;
 use anyhow::Result;
 
-pub fn part1(_input: &[u8]) -> Result<String> {
-    anyhow::bail!("not implemented")
+use crate::common::IndexSet;
+
+fn can_travel(from: u8, to: u8) -> bool {
+    match (from, to) {
+        (b'S', b'a'..=b'b') => true,
+        (b'y'..=b'z', b'E') => true,
+        (b'a'..=b'z', b'a'..=b'z') => to <= from || to - from == 1,
+        _ => false,
+    }
 }
 
-pub fn part2(_input: &[u8]) -> Result<String> {
-    anyhow::bail!("not implemented")
+fn parts_common(
+    input: &[u8],
+    starting_symbol: u8,
+    is_end: impl Fn(u8) -> bool,
+    accessible: impl Fn(u8, u8) -> bool,
+) -> Result<String> {
+    let width = input
+        .iter()
+        .position(|&c| c == b'\n')
+        .context("No newlines in input")?
+        + 1;
+
+    let starting_pos = input
+        .iter()
+        .position(|&c| c == starting_symbol)
+        .context("Could not find starting position")?;
+
+    let mut visited = IndexSet::with_capacity(input.len());
+
+    let mut todo = VecDeque::new();
+    todo.push_back((0, starting_pos));
+
+    while let Some((dist, pos)) = todo.pop_front() {
+        if is_end(input[pos]) {
+            return Ok(dist.to_string());
+        }
+
+        let mut add_todo = |new: usize| {
+            if accessible(input[pos], input[new]) && visited.insert(new) {
+                todo.push_back((dist + 1, new));
+            }
+        };
+
+        if pos % width != 0 {
+            add_todo(pos - 1);
+        }
+
+        if pos % width != width - 1 {
+            add_todo(pos + 1)
+        }
+
+        if pos >= width {
+            add_todo(pos - width);
+        }
+
+        if pos + width < input.len() {
+            add_todo(pos + width);
+        }
+    }
+
+    anyhow::bail!("Did not find a valid route")
+}
+
+pub fn part1(input: &[u8]) -> Result<String> {
+    parts_common(input, b'S', |b| b == b'E', can_travel)
+}
+
+pub fn part2(input: &[u8]) -> Result<String> {
+    parts_common(
+        input,
+        b'E',
+        |b| b == b'a' || b == b'S',
+        |a, b| can_travel(b, a),
+    )
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    const SAMPLE: &[u8] = include_bytes!("samples/12.txt");
+
+    #[test]
+    fn sample_part1() {
+        assert_eq!(part1(SAMPLE).unwrap(), "31")
+    }
+
+    #[test]
+    fn sample_part2() {
+        assert_eq!(part2(SAMPLE).unwrap(), "29")
+    }
 }

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

2022/src/samples/11.txt

@@ -0,0 +1,27 @@
+Monkey 0:
+  Starting items: 79, 98
+  Operation: new = old * 19
+  Test: divisible by 23
+    If true: throw to monkey 2
+    If false: throw to monkey 3
+
+Monkey 1:
+  Starting items: 54, 65, 75, 74
+  Operation: new = old + 6
+  Test: divisible by 19
+    If true: throw to monkey 2
+    If false: throw to monkey 0
+
+Monkey 2:
+  Starting items: 79, 60, 97
+  Operation: new = old * old
+  Test: divisible by 13
+    If true: throw to monkey 1
+    If false: throw to monkey 3
+
+Monkey 3:
+  Starting items: 74
+  Operation: new = old + 3
+  Test: divisible by 17
+    If true: throw to monkey 0
+    If false: throw to monkey 1

2022/src/samples/12.txt

@@ -0,0 +1,5 @@
+Sabqponm
+abcryxxl
+accszExk
+acctuvwj
+abdefghi