diff options
| -rw-r--r-- | 2022/rust/Cargo.toml | 2 | ||||
| -rw-r--r-- | 2022/rust/day09/Cargo.toml | 9 | ||||
| -rw-r--r-- | 2022/rust/day09/src/main.rs | 217 |
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(()) +} |