From bcc94d79456000cf1fd9acf6eff8c8ac13c805bc Mon Sep 17 00:00:00 2001 From: tomsmeding Date: Sun, 9 Dec 2018 22:33:15 +0100 Subject: Optimise day 6 --- 2018/src/day6.rs | 34 +++++++++++++++++++++++++--------- 1 file 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(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(); -- cgit v1.2.3-54-g00ecf