complete day 9

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:?}");
+}