Optimise day 6

1 files changed, 25 insertions, 9 deletions

diff --git a/2018/src/day6.rs b/2018/src/day6.rs
index 58fa733..67a0085 100644
--- a/2018/src/day6.rs
+++ b/2018/src/day6.rs
@@ -1,8 +1,6 @@
 use std::io;
 use std::io::BufRead;
 
-const W: i32 = 800;
-
 fn dist(a: (i32, i32), b: (i32, i32)) -> i32 {
     (b.0 - a.0).abs() + (b.1 - a.1).abs()
 }
@@ -15,17 +13,35 @@ pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
         (x, y)
     }).collect();
 
+    let &max_x = pts.iter().map(|(x, _)| x).max().unwrap();
+    let &max_y = pts.iter().map(|(_, y)| y).max().unwrap();
+    let min_x = -1;
+    let min_y = -1;
+
     let mut borderpts = vec![false; pts.len()];
     let mut size = vec![0; pts.len()];
     let mut nsafe = 0;
 
-    for y in -W..W+1 {
-        for x in -W..W+1 {
-            let closest = (0..pts.len()).min_by_key(|&i| dist(pts[i], (x, y))).unwrap();
-            if x == -W || x == W || y == -W || y == W {
-                borderpts[closest] = true;
-            } else {
-                size[closest] += 1;
+    for y in min_y..max_y+1 {
+        for x in min_x..max_x+1 {
+            let mut closest = 0;
+            let mut closest_dist = dist(pts[0], (x, y));
+            for i in 1..pts.len() {
+                let d = dist(pts[i], (x, y));
+                if d < closest_dist {
+                    closest_dist = d;
+                    closest = i;
+                } else if d == closest_dist {
+                    closest = usize::max_value();
+                }
+            }
+
+            if closest != usize::max_value() {
+                if x == min_x || x == max_x || y == min_y || y == max_y {
+                    borderpts[closest] = true;
+                } else {
+                    size[closest] += 1;
+                }
             }
 
             let distsum: i32 = pts.iter().map(|&p| dist(p, (x, y))).sum();