Faster hash set

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)
+    File::open(input_path)?.read_to_end(&mut buffer)?;
-        .expect("Failed to open input file")
-        .read_to_end(&mut buffer)
-        .expect("Failed to read input file");
 
-    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));
-        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));
             });
+
+            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/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> {
+use crate::common::parse_input;
-    anyhow::bail!("not implemented")
+
+#[derive(Copy, Clone)]
+enum Direction {
+    Up,
+    Left,
+    Right,
+    Down,
 }
 
-pub fn part2(_input: &[u8]) -> Result<String> {
+impl Direction {
-    anyhow::bail!("not implemented")
+    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<'a>(input: &'a [u8]) -> IResult<&'a [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/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