Add day09, 2022

3 files changed, 227 insertions, 1 deletions

diff --git a/2022/rust/Cargo.toml b/2022/rust/Cargo.toml
index 12f5982..f43b72b 100644
--- a/2022/rust/Cargo.toml
+++ b/2022/rust/Cargo.toml
@@ -8,7 +8,7 @@ members = [
      "day06",
      "day07",
      "day08",
-#     "day09",
+     "day09",
 #     "day10",
 #     "day11",
 #     "day12",
diff --git a/2022/rust/day09/Cargo.toml b/2022/rust/day09/Cargo.toml
new file mode 100644
index 0000000..20cc628
--- /dev/null
+++ b/2022/rust/day09/Cargo.toml
@@ -0,0 +1,9 @@
+[package]
+name = "day09"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
+aoc = { path = "../../../common/rust/aoc" }
+anyhow = "1.0"
+regex = "1.7.0"
diff --git a/2022/rust/day09/src/main.rs b/2022/rust/day09/src/main.rs
new file mode 100644
index 0000000..f2731e5
--- /dev/null
+++ b/2022/rust/day09/src/main.rs
@@ -0,0 +1,217 @@
+#![allow(non_snake_case)]
+use {
+    anyhow::{
+        anyhow,
+        Context,
+        Result,
+    },
+    regex::Regex,
+    std::{
+        env::args,
+        fs::File,
+        io::{
+            BufRead,
+            BufReader,
+        },
+        path::Path,
+    },
+};
+
+#[derive(Debug)]
+enum Direction {
+    Up,
+    Down,
+    Left,
+    Right,
+}
+
+type Move = (Direction, usize);
+
+#[derive(Clone, Copy, PartialEq)]
+struct Position {
+    x: isize,
+    y: isize,
+}
+
+struct Rope {
+    length: usize,
+    knots: Vec<Position>,
+}
+
+impl Rope {
+    fn new(length: usize) -> Self {
+        let knots = (0..length).into_iter().map(|_| Position { x: 0, y: 0 }).collect();
+        Self {
+            length,
+            knots,
+        }
+    }
+
+    #[allow(dead_code)]
+    fn head(&self) -> Position {
+        self.knots[0]
+    }
+
+    fn tail(&self) -> Position {
+        self.knots[self.length - 1]
+    }
+
+    fn lead(&mut self, direction: &Direction) {
+        match direction {
+            Direction::Down  => self.knots[0].y += 1,
+            Direction::Up    => self.knots[0].y -= 1,
+            Direction::Right => self.knots[0].x += 1,
+            Direction::Left  => self.knots[0].x -= 1,
+        }
+    }
+
+    fn follow(&mut self, index: usize) {
+        let Δx = self.knots[index - 1].x - self.knots[index].x;
+        let Δy = self.knots[index - 1].y - self.knots[index].y;
+        let Δx_abs = isize::abs(Δx);
+        let Δy_abs = isize::abs(Δy);
+        
+        if Δx == 0 && Δy == 0 {
+            // Already touching. Stay as is.
+        } else if Δx == 0 {
+            if Δy_abs <= 1 {
+                // Already touching. Stay as is.
+            } else if Δy_abs == 2 {
+                self.knots[index].y += Δy.signum();
+            } else {
+                unreachable!();
+            }
+        } else if Δy == 0 {
+            if Δx_abs <= 1 {
+                // Already touching. Stay as is.
+            } else if Δx_abs == 2 {
+                self.knots[index].x += Δx.signum();
+            } else {
+                unreachable!();
+            }
+        } else if Δx_abs == 1 && Δy_abs == 1 {
+            // Already touching. Stay as is.
+        } else if Δx_abs >= 1 && Δy_abs >= 1 {
+            self.knots[index].x += Δx.signum();
+            self.knots[index].y += Δy.signum();
+        } else {
+            unreachable!();
+        }
+    }
+
+    fn step(&mut self, direction: &Direction) {
+        self.lead(direction);
+        for knot in 1..self.length {
+            self.follow(knot);
+        }
+    }
+}
+
+fn read_input<T: AsRef<Path>>(filename: T) -> Result<Vec<Move>> {
+    let reader = BufReader::new(File::open(filename)?);
+    let re = Regex::new(r#"(?P<direction>[UDRL]) (?P<steps>[0-9]+)"#)?;
+
+    reader.lines().map(
+        |v| {
+            let s = v?;
+            let caps = re.captures(&s).ok_or_else(|| anyhow!("Regex match failed: {s}"))?;
+            let steps = caps.name("steps").ok_or_else(|| anyhow!("Missing steps: {s}"))?.as_str()
+                .parse()?;
+            let direction = match caps.name("direction")
+                .ok_or_else(|| anyhow!("Missing direction: {s}"))?.as_str()
+            {
+                "U" => Direction::Up,
+                "D" => Direction::Down,
+                "L" => Direction::Left,
+                "R" => Direction::Right,
+                _   => return Err(anyhow!("Failed to parse direction from: {s}")),
+            };
+            Ok((direction, steps))
+        }
+    ).collect()
+}
+
+#[allow(dead_code)]
+fn plot(rope: &Rope, visited: &[Position]) {
+    let min_x =
+        [rope.head(), rope.tail()].iter().chain(visited.iter()).map(|pos| pos.x).min().unwrap();
+    let max_x =
+        [rope.head(), rope.tail()].iter().chain(visited.iter()).map(|pos| pos.x).max().unwrap();
+    let min_y =
+        [rope.head(), rope.tail()].iter().chain(visited.iter()).map(|pos| pos.y).min().unwrap();
+    let max_y =
+        [rope.head(), rope.tail()].iter().chain(visited.iter()).map(|pos| pos.y).max().unwrap();
+
+    println!("x: {min_x}..{max_x}, y: {min_y}..{max_y}");
+    for y in min_y..=max_y {
+        for x in min_x..=max_x {
+            let pos = Position { x, y };
+
+            if pos == rope.head() {
+                print!("H");
+            } else if pos == rope.tail() {
+                print!("T");
+            } else if pos == (Position { x: 0, y: 0 }) {
+                print!("s");
+            } else if visited.contains(&pos) {
+                print!("#");
+            } else {
+                print!(".");
+            }
+        }
+        println!();
+    }
+    println!();
+}
+
+fn part1(input: &[Move]) -> Result<usize> {
+    let mut rope = Rope::new(2);
+    let mut visited = vec![rope.tail()];
+
+    for (direction, steps) in input {
+        for _ in 0..*steps {
+            rope.step(direction);
+            let tail = rope.tail();
+            if !visited.contains(&tail) {
+                visited.push(tail);
+            }
+            // plot(&rope, &visited);
+        }
+    }
+
+    Ok(visited.len())
+}
+
+fn part2(input: &[Move]) -> Result<usize> {
+    let mut rope = Rope::new(10);
+    let mut visited = vec![rope.tail()];
+
+    for (direction, steps) in input {
+        for _ in 0..*steps {
+            rope.step(direction);
+            let tail = rope.tail();
+            if !visited.contains(&tail) {
+                visited.push(tail);
+            }
+            // plot(&rope, &visited);
+        }
+    }
+
+    Ok(visited.len())
+}
+
+fn main() -> Result<()> {
+    let ( do_part_1, do_part_2 ) = aoc::do_parts();
+
+    let filename = args().nth(1).ok_or_else(|| anyhow!("Missing input filename"))?;
+    let input = read_input(filename).context("Could not read input")?;
+    if do_part_1 {
+        let solution = part1(&input).context("No solution for part 1")?;
+        println!("Part1, solution found to be: {}", solution);
+    }
+    if do_part_2 {
+        let solution = part2(&input).context("No solution for part 2")?;
+        println!("Part2, solution found to be: {}", solution);
+    }
+    Ok(())
+}