summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--2022/rust/Cargo.toml2
-rw-r--r--2022/rust/day09/Cargo.toml9
-rw-r--r--2022/rust/day09/src/main.rs217
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(())
+}