/// --- 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, } 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::().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:?}"); }