From 62849d01ab9cf2e2a0763d2306e1a8942793bd2d Mon Sep 17 00:00:00 2001
From: Greg Burri <greg.burri@gmail.com>
Date: Wed, 14 Dec 2022 10:36:47 +0100
Subject: [PATCH] Day 14

---
 src/day14.rs | 83 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/days.rs  |  9 ++++++
 src/main.rs  |  2 ++
 3 files changed, 94 insertions(+)
 create mode 100644 src/day14.rs

diff --git a/src/day14.rs b/src/day14.rs
new file mode 100644
index 0000000..fcc9f9f
--- /dev/null
+++ b/src/day14.rs
@@ -0,0 +1,83 @@
+use std::collections::HashSet;
+
+use itertools::Itertools;
+
+type Rocks = HashSet<(i32, i32)>;
+
+pub fn parse(input: &str) -> (Rocks, i32) {
+    let mut max_i = 0;
+    let mut rocks = Rocks::new();
+    for l in input.lines().map(|l| l.replace(" ", "")) {
+        for ((i1, j1), (i2, j2)) in l
+            .split("->")
+            .map(|p| {
+                let ji: Vec<&str> = p.split(',').collect();
+                (ji[1].parse::<i32>().unwrap(), ji[0].parse::<i32>().unwrap())
+            })
+            .tuple_windows()
+        {
+            for i in i1.min(i2)..=i1.max(i2) {
+                for j in j1.min(j2)..=j1.max(j2) {
+                    rocks.insert((i, j));
+                    max_i = i.max(max_i);
+                }
+            }
+        }
+    }
+    (rocks, max_i + 2)
+}
+
+pub fn poor_sand(mut rocks: Rocks, floor: i32) -> (i32, i32) {
+    let mut n = 0;
+    let mut first_n_touching_floor = 0;
+
+    fn is_obstruct(i: i32, j: i32, rocks: &Rocks, floor: i32) -> bool {
+        i >= floor || rocks.contains(&(i, j))
+    }
+
+    loop {
+        let mut grain = (0, 500);
+
+        if rocks.contains(&grain) {
+            return (first_n_touching_floor, n);
+        }
+
+        loop {
+            if first_n_touching_floor == 0 && grain.0 + 1 >= floor {
+                first_n_touching_floor = n;
+            }
+
+            if !is_obstruct(grain.0 + 1, grain.1, &rocks, floor) {
+                grain = (grain.0 + 1, grain.1);
+            } else if !is_obstruct(grain.0 + 1, grain.1 - 1, &rocks, floor) {
+                grain = (grain.0 + 1, grain.1 - 1);
+            } else if !is_obstruct(grain.0 + 1, grain.1 + 1, &rocks, floor) {
+                grain = (grain.0 + 1, grain.1 + 1);
+            } else {
+                rocks.insert(grain);
+                break;
+            }
+        }
+        n = n + 1;
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    static ROCKS: &str = "498,4 -> 498,6 -> 496,6
+        503,4 -> 502,4 -> 502,9 -> 494,9";
+
+    #[test]
+    fn part1() {
+        let (rocks, floor) = parse(ROCKS);
+        assert_eq!(poor_sand(rocks, floor).0, 24);
+    }
+
+    #[test]
+    fn part2() {
+        let (rocks, floor) = parse(ROCKS);
+        assert_eq!(poor_sand(rocks, floor).1, 93);
+    }
+}
diff --git a/src/days.rs b/src/days.rs
index 9e999b3..415dc72 100644
--- a/src/days.rs
+++ b/src/days.rs
@@ -142,3 +142,12 @@ pub fn day13() -> String {
         day13::product_indices_special_signals(&signals)
     )
 }
+
+pub fn day14() -> String {
+    let (rocks, floor) = day14::parse(&fs::read_to_string("data/day14.input").unwrap());
+    let (first_grain_touching_floor, last_grain) = day14::poor_sand(rocks, floor);
+    format!(
+        "part1: {}, part2: {}",
+        first_grain_touching_floor, last_grain
+    )
+}
diff --git a/src/main.rs b/src/main.rs
index 85ca7e3..557f3b1 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -16,6 +16,7 @@ mod day10;
 mod day11;
 mod day12;
 mod day13;
+mod day14;
 mod days;
 
 #[derive(Parser, Debug)]
@@ -45,6 +46,7 @@ fn main() {
         days::day11,
         days::day12,
         days::day13,
+        days::day14,
     ];
 
     let args = Args::parse();
-- 
2.45.2