diff options
Diffstat (limited to 'day09b/src/main.rs')
| -rw-r--r-- | day09b/src/main.rs | 605 |
1 files changed, 605 insertions, 0 deletions
diff --git a/day09b/src/main.rs b/day09b/src/main.rs new file mode 100644 index 0000000..7cee4ad --- /dev/null +++ b/day09b/src/main.rs @@ -0,0 +1,605 @@ +/// --- Part Two --- +/// +/// A rope snaps! Suddenly, the river is getting a lot closer than you remember. The bridge is +/// still there, but some of the ropes that broke are now whipping toward you as you fall through +/// the air! +/// +/// The ropes are moving too quickly to grab; you only have a few seconds to choose how to arch +/// your body to avoid being hit. Fortunately, your simulation can be extended to support longer +/// ropes. +/// +/// Rather than two knots, you now must simulate a rope consisting of ten knots. One knot is still +/// the head of the rope and moves according to the series of motions. Each knot further down the +/// rope follows the knot in front of it using the same rules as before. +/// +/// Using the same series of motions as the above example, but with the knots marked H, 1, 2, ..., +/// 9, the motions now occur as follows: +/// +/// ``` +/// == Initial State == +/// +/// ...... +/// ...... +/// ...... +/// ...... +/// H..... (H covers 1, 2, 3, 4, 5, 6, 7, 8, 9, s) +/// +/// == R 4 == +/// +/// ...... +/// ...... +/// ...... +/// ...... +/// 1H.... (1 covers 2, 3, 4, 5, 6, 7, 8, 9, s) +/// +/// ...... +/// ...... +/// ...... +/// ...... +/// 21H... (2 covers 3, 4, 5, 6, 7, 8, 9, s) +/// +/// ...... +/// ...... +/// ...... +/// ...... +/// 321H.. (3 covers 4, 5, 6, 7, 8, 9, s) +/// +/// ...... +/// ...... +/// ...... +/// ...... +/// 4321H. (4 covers 5, 6, 7, 8, 9, s) +/// +/// == U 4 == +/// +/// ...... +/// ...... +/// ...... +/// ....H. +/// 4321.. (4 covers 5, 6, 7, 8, 9, s) +/// +/// ...... +/// ...... +/// ....H. +/// .4321. +/// 5..... (5 covers 6, 7, 8, 9, s) +/// +/// ...... +/// ....H. +/// ....1. +/// .432.. +/// 5..... (5 covers 6, 7, 8, 9, s) +/// +/// ....H. +/// ....1. +/// ..432. +/// .5.... +/// 6..... (6 covers 7, 8, 9, s) +/// +/// == L 3 == +/// +/// ...H.. +/// ....1. +/// ..432. +/// .5.... +/// 6..... (6 covers 7, 8, 9, s) +/// +/// ..H1.. +/// ...2.. +/// ..43.. +/// .5.... +/// 6..... (6 covers 7, 8, 9, s) +/// +/// .H1... +/// ...2.. +/// ..43.. +/// .5.... +/// 6..... (6 covers 7, 8, 9, s) +/// +/// == D 1 == +/// +/// ..1... +/// .H.2.. +/// ..43.. +/// .5.... +/// 6..... (6 covers 7, 8, 9, s) +/// +/// == R 4 == +/// +/// ..1... +/// ..H2.. +/// ..43.. +/// .5.... +/// 6..... (6 covers 7, 8, 9, s) +/// +/// ..1... +/// ...H.. (H covers 2) +/// ..43.. +/// .5.... +/// 6..... (6 covers 7, 8, 9, s) +/// +/// ...... +/// ...1H. (1 covers 2) +/// ..43.. +/// .5.... +/// 6..... (6 covers 7, 8, 9, s) +/// +/// ...... +/// ...21H +/// ..43.. +/// .5.... +/// 6..... (6 covers 7, 8, 9, s) +/// +/// == D 1 == +/// +/// ...... +/// ...21. +/// ..43.H +/// .5.... +/// 6..... (6 covers 7, 8, 9, s) +/// +/// == L 5 == +/// +/// ...... +/// ...21. +/// ..43H. +/// .5.... +/// 6..... (6 covers 7, 8, 9, s) +/// +/// ...... +/// ...21. +/// ..4H.. (H covers 3) +/// .5.... +/// 6..... (6 covers 7, 8, 9, s) +/// +/// ...... +/// ...2.. +/// ..H1.. (H covers 4; 1 covers 3) +/// .5.... +/// 6..... (6 covers 7, 8, 9, s) +/// +/// ...... +/// ...2.. +/// .H13.. (1 covers 4) +/// .5.... +/// 6..... (6 covers 7, 8, 9, s) +/// +/// ...... +/// ...... +/// H123.. (2 covers 4) +/// .5.... +/// 6..... (6 covers 7, 8, 9, s) +/// +/// == R 2 == +/// +/// ...... +/// ...... +/// .H23.. (H covers 1; 2 covers 4) +/// .5.... +/// 6..... (6 covers 7, 8, 9, s) +/// +/// ...... +/// ...... +/// .1H3.. (H covers 2, 4) +/// .5.... +/// 6..... (6 covers 7, 8, 9, s) +/// ``` +/// +/// Now, you need to keep track of the positions the new tail, 9, visits. In this example, the +/// tail never moves, and so it only visits 1 position. However, be careful: more types of motion +/// are possible than before, so you might want to visually compare your simulated rope to the one +/// above. +/// +/// Here's a larger example: +/// +/// ``` +/// R 5 +/// U 8 +/// L 8 +/// D 3 +/// R 17 +/// D 10 +/// L 25 +/// U 20 +/// ``` +/// +/// These motions occur as follows (individual steps are not shown): +/// +/// ``` +/// == Initial State == +/// +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// ...........H.............. (H covers 1, 2, 3, 4, 5, 6, 7, 8, 9, s) +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// +/// == R 5 == +/// +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// ...........54321H......... (5 covers 6, 7, 8, 9, s) +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// +/// == U 8 == +/// +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// ................H......... +/// ................1......... +/// ................2......... +/// ................3......... +/// ...............54......... +/// ..............6........... +/// .............7............ +/// ............8............. +/// ...........9.............. (9 covers s) +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// +/// == L 8 == +/// +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// ........H1234............. +/// ............5............. +/// ............6............. +/// ............7............. +/// ............8............. +/// ............9............. +/// .......................... +/// .......................... +/// ...........s.............. +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// +/// == D 3 == +/// +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .........2345............. +/// ........1...6............. +/// ........H...7............. +/// ............8............. +/// ............9............. +/// .......................... +/// .......................... +/// ...........s.............. +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// +/// == R 17 == +/// +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// ................987654321H +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// ...........s.............. +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// +/// == D 10 == +/// +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// ...........s.........98765 +/// .........................4 +/// .........................3 +/// .........................2 +/// .........................1 +/// .........................H +/// +/// == L 25 == +/// +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// ...........s.............. +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// H123456789................ +/// +/// == U 20 == +/// +/// H......................... +/// 1......................... +/// 2......................... +/// 3......................... +/// 4......................... +/// 5......................... +/// 6......................... +/// 7......................... +/// 8......................... +/// 9......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// ...........s.............. +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// +/// Now, the tail (9) visits 36 positions (including s) at least once: +/// +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// .......................... +/// #......................... +/// #.............###......... +/// #............#...#........ +/// .#..........#.....#....... +/// ..#..........#.....#...... +/// ...#........#.......#..... +/// ....#......s.........#.... +/// .....#..............#..... +/// ......#............#...... +/// .......#..........#....... +/// ........#........#........ +/// .........########......... +/// ``` +/// +/// Simulate your complete series of motions on a larger rope with ten knots. 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"; +const KNOTS: usize = 10; + +#[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, + knots: [Coord; KNOTS - 1], + 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(), + knots: [Coord::new(); KNOTS - 1], + tail_visited: hs, + } + } + + fn update_knot(&mut self, idx: usize, h_idx: Option<usize>) { + let head = match h_idx { + None => &self.head, + Some(h_idx) => &self.knots[h_idx], + }; + match (head.x - self.knots[idx].x, head.y - self.knots[idx].y) { + (0, 0) + | (1, 0) + | (-1, 0) + | (0, 1) + | (0, -1) + | (1, 1) + | (-1, -1) + | (1, -1) + | (-1, 1) => return, + (xdiff, ydiff) => { + self.knots[idx].x += i32::signum(xdiff); + self.knots[idx].y += i32::signum(ydiff); + if idx == KNOTS - 2 { + self.tail_visited.insert(self.knots[idx]); + } + } + } + } + + 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, + } + for idx in 0..(KNOTS - 1) { + let h_idx = match idx { + 0 => None, + _ => Some(idx - 1), + }; + self.update_knot(idx, h_idx); + } + } + + 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:?}"); +} |