diff options
Diffstat (limited to 'day09a/src/main.rs')
| -rw-r--r-- | day09a/src/main.rs | 417 |
1 files changed, 417 insertions, 0 deletions
diff --git a/day09a/src/main.rs b/day09a/src/main.rs new file mode 100644 index 0000000..efe843c --- /dev/null +++ b/day09a/src/main.rs @@ -0,0 +1,417 @@ +/// --- Day 9: Rope Bridge --- +/// +/// This rope bridge creaks as you walk along it. You aren't sure how old it is, or whether it can +/// even support your weight. +/// +/// It seems to support the Elves just fine, though. The bridge spans a gorge which was carved out +/// by the massive river far below you. +/// +/// You step carefully; as you do, the ropes stretch and twist. You decide to distract yourself by +/// modeling rope physics; maybe you can even figure out where not to step. +/// +/// Consider a rope with a knot at each end; these knots mark the head and the tail of the rope. If +/// the head moves far enough away from the tail, the tail is pulled toward the head. +/// +/// Due to nebulous reasoning involving Planck lengths, you should be able to model the positions +/// of the knots on a two-dimensional grid. Then, by following a hypothetical series of motions +/// (your puzzle input) for the head, you can determine how the tail will move. +/// +/// Due to the aforementioned Planck lengths, the rope must be quite short; in fact, the head (H) +/// and tail (T) must always be touching (diagonally adjacent and even overlapping both count as +/// touching): +/// +/// ``` +/// .... +/// .TH. +/// .... +/// +/// .... +/// .H.. +/// ..T. +/// .... +/// +/// ... +/// .H. (H covers T) +/// ... +/// ``` +/// +/// If the head is ever two steps directly up, down, left, or right from the tail, the tail must +/// also move one step in that direction so it remains close enough: +/// +/// ``` +/// ..... ..... ..... +/// .TH.. -> .T.H. -> ..TH. +/// ..... ..... ..... +/// +/// ... ... ... +/// .T. .T. ... +/// .H. -> ... -> .T. +/// ... .H. .H. +/// ... ... ... +/// ``` +/// +/// Otherwise, if the head and tail aren't touching and aren't in the same row or column, the tail +/// always moves one step diagonally to keep up: +/// +/// ``` +/// ..... ..... ..... +/// ..... ..H.. ..H.. +/// ..H.. -> ..... -> ..T.. +/// .T... .T... ..... +/// ..... ..... ..... +/// +/// ..... ..... ..... +/// ..... ..... ..... +/// ..H.. -> ...H. -> ..TH. +/// .T... .T... ..... +/// ..... ..... ..... +/// ``` +/// +/// You just need to work out where the tail goes as the head follows a series of motions. Assume +/// the head and the tail both start at the same position, overlapping. +/// +/// For example: +/// +/// ``` +/// R 4 +/// U 4 +/// L 3 +/// D 1 +/// R 4 +/// D 1 +/// L 5 +/// R 2 +/// ``` +/// +/// This series of motions moves the head right four steps, then up four steps, then left three +/// steps, then down one step, and so on. After each step, you'll need to update the position of +/// the tail if the step means the head is no longer adjacent to the tail. Visually, these motions +/// occur as follows (s marks the starting position as a reference point): +/// +/// ``` +/// == Initial State == +/// +/// ...... +/// ...... +/// ...... +/// ...... +/// H..... (H covers T, s) +/// +/// == R 4 == +/// +/// ...... +/// ...... +/// ...... +/// ...... +/// TH.... (T covers s) +/// +/// ...... +/// ...... +/// ...... +/// ...... +/// sTH... +/// +/// ...... +/// ...... +/// ...... +/// ...... +/// s.TH.. +/// +/// ...... +/// ...... +/// ...... +/// ...... +/// s..TH. +/// +/// == U 4 == +/// +/// ...... +/// ...... +/// ...... +/// ....H. +/// s..T.. +/// +/// ...... +/// ...... +/// ....H. +/// ....T. +/// s..... +/// +/// ...... +/// ....H. +/// ....T. +/// ...... +/// s..... +/// +/// ....H. +/// ....T. +/// ...... +/// ...... +/// s..... +/// +/// == L 3 == +/// +/// ...H.. +/// ....T. +/// ...... +/// ...... +/// s..... +/// +/// ..HT.. +/// ...... +/// ...... +/// ...... +/// s..... +/// +/// .HT... +/// ...... +/// ...... +/// ...... +/// s..... +/// +/// == D 1 == +/// +/// ..T... +/// .H.... +/// ...... +/// ...... +/// s..... +/// +/// == R 4 == +/// +/// ..T... +/// ..H... +/// ...... +/// ...... +/// s..... +/// +/// ..T... +/// ...H.. +/// ...... +/// ...... +/// s..... +/// +/// ...... +/// ...TH. +/// ...... +/// ...... +/// s..... +/// +/// ...... +/// ....TH +/// ...... +/// ...... +/// s..... +/// +/// == D 1 == +/// +/// ...... +/// ....T. +/// .....H +/// ...... +/// s..... +/// +/// == L 5 == +/// +/// ...... +/// ....T. +/// ....H. +/// ...... +/// s..... +/// +/// ...... +/// ....T. +/// ...H.. +/// ...... +/// s..... +/// +/// ...... +/// ...... +/// ..HT.. +/// ...... +/// s..... +/// +/// ...... +/// ...... +/// .HT... +/// ...... +/// s..... +/// +/// ...... +/// ...... +/// HT.... +/// ...... +/// s..... +/// +/// == R 2 == +/// +/// ...... +/// ...... +/// .H.... (H covers T) +/// ...... +/// s..... +/// +/// ...... +/// ...... +/// .TH... +/// ...... +/// s..... +/// ``` +/// +/// After simulating the rope, you can count up all of the positions the tail visited at least +/// once. In this diagram, s again marks the starting position (which the tail also visited) and # +/// marks other positions the tail visited: +/// +/// ``` +/// ..##.. +/// ...##. +/// .####. +/// ....#. +/// s###.. +/// ``` +/// +/// So, there are 13 positions the tail visited at least once. +/// +/// Simulate your complete hypothetical series of motions. How many positions does the tail of the +/// rope visit at least once? +use clap::Parser; +use itertools::Itertools; + +use std::collections::HashSet; +use std::fs::File; +use std::io::prelude::*; +use std::io::BufReader; +use std::path::PathBuf; + +const FILEPATH: &'static str = "examples/input.txt"; + +#[derive(Parser, Debug)] +#[clap(author, version, about, long_about = None)] +struct Cli { + #[clap(short, long, default_value = FILEPATH)] + file: PathBuf, +} + +#[derive(Copy, Clone, Debug)] +enum Direction { + Up, + Down, + Left, + Right, +} + +#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)] +struct Coord { + x: i32, + y: i32, +} + +#[derive(Clone, Debug)] +struct Command { + dir: Direction, + amount: u32, +} + +#[derive(Clone, Debug)] +struct State { + head: Coord, + tail: Coord, + tail_visited: HashSet<Coord>, +} + +impl Coord { + fn new() -> Self { + Self { x: 0, y: 0 } + } +} + +impl Command { + fn parse(dir: &str, amount: &str) -> Self { + use Direction::*; + let d = match dir { + "U" => Up, + "D" => Down, + "L" => Left, + "R" => Right, + _ => panic!("unknown direction {}", dir), + }; + Self { + dir: d, + amount: amount.parse::<u32>().unwrap(), + } + } +} + +impl State { + fn new() -> Self { + let mut hs = HashSet::new(); + hs.insert(Coord::new()); + State { + head: Coord::new(), + tail: Coord::new(), + tail_visited: hs, + } + } + + fn update_tail(&mut self) { + match (self.head.x - self.tail.x, self.head.y - self.tail.y) { + (0, 0) + | (1, 0) + | (-1, 0) + | (0, 1) + | (0, -1) + | (1, 1) + | (-1, -1) + | (1, -1) + | (-1, 1) => return, + (xdiff, ydiff) => { + self.tail.x += i32::signum(xdiff); + self.tail.y += i32::signum(ydiff); + self.tail_visited.insert(self.tail); + }, + } + } + + fn shift(&mut self, dir: Direction) { + use Direction::*; + match dir { + Up => self.head.y += 1, + Down => self.head.y -= 1, + Right => self.head.x += 1, + Left => self.head.x -= 1, + } + self.update_tail(); + } + + fn process(&mut self, cmd: &Command) { + for _ in 0..cmd.amount { + self.shift(cmd.dir); + } + } +} + +fn main() { + let args = Cli::parse(); + + let file = File::open(&args.file).unwrap(); + let reader = BufReader::new(file); + let mut state = State::new(); + let _ = reader + .lines() + .map(|l| { + l.unwrap() + .split_whitespace() + .map(|s| s.to_owned()) + .collect_tuple::<(String, String)>() + .unwrap() + }) + .map(|(dir, amount)| Command::parse(dir.as_str(), amount.as_str())) + .scan(&mut state, |state, cmd| { + state.process(&cmd); + Some(()) + }) + .last(); + + let res = state.tail_visited.len(); + println!("{res:?}"); +} |