25-09 p2 very ugly but works

1 files changed, 56 insertions, 7 deletions

diff --git a/2025/09/rust/src/main.rs b/2025/09/rust/src/main.rs
index 8c13bcb..32847e3 100644
--- a/2025/09/rust/src/main.rs
+++ b/2025/09/rust/src/main.rs
@@ -28,11 +28,11 @@ impl Floor {
         )
     }
 
-    fn uncomp(self: &Self, (x, y): (usize, usize)) -> (usize, usize) {
+    fn uncomp(&self, (x, y): (usize, usize)) -> (usize, usize) {
         (self.x_comp[x], self.y_comp[y])
     }
 
-    fn area(self: &Self, p1: (usize, usize), p2: (usize, usize)) -> usize {
+    fn area(&self, (p1, p2): ((usize, usize), (usize, usize))) -> usize {
         let (x1, y1) = self.uncomp(p1);
         let (x2, y2) = self.uncomp(p2);
         (x1.abs_diff(x2) + 1) * (y1.abs_diff(y2) + 1)
@@ -51,14 +51,63 @@ fn main() {
 
     let (floor, pts) = Floor::new(pts);
 
-    let silver: usize = pts
+    let xmax = *pts.iter().map(|(x, _)| x).max().unwrap();
+    let ymax = *pts.iter().map(|(_, y)| y).max().unwrap();
+
+    // some padding so that flood fill works correctly
+    let mut grid: Vec<Vec<Option<bool>>> = vec![vec![None; xmax + 3]; ymax + 3];
+
+    // draw green/red tiles
+    for pair in [vec![*pts.last().unwrap()], pts.clone()]
+        .concat()
+        .windows(2)
+    {
+        let (x1, y1) = pair[0];
+        let (x2, y2) = pair[1];
+        (x1.min(x2)..=x1.max(x2)).for_each(|x| {
+            (y1.min(y2)..=(y1.max(y2))).for_each(|y| grid[y + 1][x + 1] = Some(true))
+        });
+    }
+
+    // flood fill from top left
+    let mut q = vec![(0, 0)];
+    while let Some((x, y)) = q.pop() {
+        grid[y][x] = Some(false);
+        let ns = vec![
+            (x.saturating_sub(1), y),
+            ((x + 1).min(xmax + 2), y),
+            (x, y.saturating_sub(1)),
+            (x, (y + 1).min(ymax + 2)),
+        ];
+        q.extend(ns.into_iter().filter(|&(x, y)| grid[y][x].is_none()));
+    }
+
+    // replace inside cells with Some(true) and undo the padding
+    let grid: Vec<Vec<bool>> = grid
+        .into_iter()
+        .skip(1)
+        .map(|r| r.into_iter().skip(1).map(|c| c.unwrap_or(true)).collect())
+        .collect();
+
+    let mut rectangles = pts
         .iter()
         .enumerate()
-        .flat_map(|(idx, p1)| pts.iter().take(idx).map(|p2| floor.area(*p1, *p2)))
-        .max()
-        .unwrap();
+        .flat_map(|(idx, p1)| pts.iter().take(idx).map(move |p2| (*p1, *p2)))
+        .collect::<Vec<_>>();
+    rectangles.sort_unstable_by_key(|&r| std::cmp::Reverse(floor.area(r)));
 
-    let gold: u64 = 0;
+    let silver: usize = floor.area(*rectangles.first().unwrap());
+    let gold: usize = floor.area(
+        *rectangles
+            .iter()
+            .filter(|&&((x1, y1), (x2, y2))| {
+                (x1.min(x2)..=x1.max(x2))
+                    .flat_map(|x| (y1.min(y2)..=y1.max(y2)).map(move |y| (x, y)))
+                    .all(|(x, y)| grid[y][x])
+            })
+            .next()
+            .unwrap(),
+    );
     println!("silver: {silver}");
     println!("gold: {gold}");
 }