From f4618e7ec3cba37f4fccae225f5b3f29081d69da Mon Sep 17 00:00:00 2001
From: Greg Burri <greg.burri@gmail.com>
Date: Fri, 9 Dec 2022 14:10:28 +0100
Subject: [PATCH] Day[9]

---
 src/day09.rs | 112 +++++++++++++++++++++++++++++++++++++++++++++++++++
 src/main.rs  |   7 ++++
 2 files changed, 119 insertions(+)
 create mode 100644 src/day09.rs

diff --git a/src/day09.rs b/src/day09.rs
new file mode 100644
index 0000000..106b947
--- /dev/null
+++ b/src/day09.rs
@@ -0,0 +1,112 @@
+use std::{cmp::max, collections::HashSet};
+
+enum Direction {
+    Left,
+    Up,
+    Right,
+    Down,
+}
+
+pub struct Movement {
+    direction: Direction,
+    distance: i32,
+}
+
+pub fn parse(input: &str) -> Vec<Movement> {
+    input.lines().map(|l| {
+        let split: Vec<&str> = l.trim().split(' ').collect();
+        Movement {
+            direction: match split[0] {
+                "L" => Direction::Left,
+                "U" => Direction::Up,
+                "R" => Direction::Right,
+                "D" => Direction::Down,
+                other => panic!("Uknown movement: {}", other),
+            },
+            distance: split[1].parse().expect("Can't parse distance"),
+        }
+    }).collect()
+}
+
+fn chebyshev_distance(p1: (i32, i32), p2: (i32, i32)) -> i32 {
+    max((p2.0 - p1.0).abs(), (p2.1 - p1.1).abs())
+}
+
+pub fn nb_positions_visited_by_tail<const N: usize>(movements: &[Movement]) -> usize {
+    let mut visited: HashSet<(i32, i32)> = HashSet::new();
+    visited.insert((0, 0));
+
+    let mut rope = [(0, 0); N]; // First element is the tail, last element is the head.
+
+    for m in movements {
+        for _ in 0..m.distance {
+            // 1) Move the head.
+            let h = &mut rope[N-1];
+            *h = match m.direction {
+                Direction::Left => (h.0 - 1, h.1),
+                Direction::Up => (h.0, h.1 - 1),
+                Direction::Right => (h.0 + 1, h.1),
+                Direction::Down => (h.0, h.1 + 1),
+            };
+
+            // 2) Move the rest of the rope.
+            for i in (0..N-1).rev() {
+                let target = rope[i+1];
+                let mut node = &mut rope[i];
+                if chebyshev_distance(*node, target) >= 2 {
+                    let (dx, dy) = (node.0 - target.0, node.1 - target.1);
+                    (node.0, node.1) =
+                        if dx.abs() > dy.abs() {
+                            (target.0 + dx.signum(), target.1)
+                        } else if dx.abs() < dy.abs() {
+                            (target.0, target.1 + dy.signum())
+                        } else {
+                            (target.0 + dx.signum(), target.1 + dy.signum())
+                        };
+                    if i == 0 {
+                        visited.insert(*node);
+                    }
+                }
+            }
+        }
+    };
+    visited.len()
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    static MOVEMENTS: &str =
+        "R 4
+         U 4
+         L 3
+         D 1
+         R 4
+         D 1
+         L 5
+         R 2";
+
+    #[test]
+    fn part1() {
+        let movements = parse(MOVEMENTS);
+        assert_eq!(nb_positions_visited_by_tail::<2>(&movements), 13);
+    }
+
+    #[test]
+    fn part2() {
+        let movements = parse(MOVEMENTS);
+        assert_eq!(nb_positions_visited_by_tail::<10>(&movements), 1);
+
+        let movements_2 = parse(
+            "R 5
+             U 8
+             L 8
+             D 3
+             R 17
+             D 10
+             L 25
+             U 20");
+        assert_eq!(nb_positions_visited_by_tail::<10>(&movements_2), 36);
+    }
+}
\ No newline at end of file
diff --git a/src/main.rs b/src/main.rs
index 28b0f67..44cbcd1 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -9,6 +9,7 @@ mod day05;
 mod day06;
 mod day07;
 mod day08;
+mod day09;
 
 fn day01() -> String {
     let f = fs::File::open("data/day01.input").unwrap();
@@ -70,6 +71,11 @@ fn day08() -> String {
     format!("part1: {}, part2: {}", day08::number_of_visible_trees(&forest), day08::best_scenic_score(&forest))
 }
 
+fn day09() -> String {
+    let movements = day09::parse(&fs::read_to_string("data/day09.input").unwrap());
+    format!("part1: {}, part2: {}", day09::nb_positions_visited_by_tail::<2>(&movements), day09::nb_positions_visited_by_tail::<10>(&movements))
+}
+
 fn format_micros(t: u128) -> String {
     if t < 10_000 {
         format!("{} μs", t)
@@ -97,6 +103,7 @@ fn main() {
         day06,
         day07,
         day08,
+        day09,
     );
 
     let args: Vec<String> = env::args().skip(1).collect();
-- 
2.45.2