Optimise day 10

1 files changed, 29 insertions, 5 deletions

diff --git a/2018/src/day10.rs b/2018/src/day10.rs
index 28da8de..99be244 100644
--- a/2018/src/day10.rs
+++ b/2018/src/day10.rs
@@ -1,5 +1,6 @@
 use std::io;
 use std::io::BufRead;
+use std::cmp::max;
 use std::collections::HashSet;
 
 fn parse_pt(l: &str) -> ((i32, i32), (i32, i32)) {
@@ -19,6 +20,10 @@ fn parse_pt(l: &str) -> ((i32, i32), (i32, i32)) {
         (s3.trim().parse().unwrap(), s4.trim().parse().unwrap()))
 }
 
+fn dist((x, y): (i32, i32), (u, v): (i32, i32)) -> i32 {
+    return ((u - x) as f32 * (u - x) as f32 + (v - y) as f32 * (v - y) as f32).sqrt() as i32;
+}
+
 pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
     let dots: Vec<((i32, i32), (i32, i32))> =
         reader.lines().map(|l| l.unwrap())
@@ -28,15 +33,26 @@ pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
     let mut pts: Vec<_> = dots.iter().map(|&(xy, _)| xy).collect();
     let vels: Vec<_> = dots.iter().map(|&(_, v)| v).collect();
 
+    let maxvel = vels.iter().map(|&xy| dist(xy, (0, 0)) + 1).max().unwrap();
+
     let mut maxscore = -1;
-    let mut maxat = (-1, vec![], HashSet::new());
-    for iter in 0..20000 {
+    let mut maxat;
+    let mut iter = 0;
+    loop {
         let mut has_dot: HashSet<(i32, i32)> = HashSet::new();
+
+        let mut avg = (0, 0);
         let mut score = 0;
         for &xy in &pts {
             if has_dot.contains(&xy) { score += 1; }
-            has_dot.insert(xy);
+            else { has_dot.insert(xy); }
+            avg.0 += xy.0;
+            avg.1 += xy.1;
         }
+        avg.0 /= dots.len() as i32;
+        avg.1 /= dots.len() as i32;
+
+        let maxdist = pts.iter().map(|&xy| dist(xy, avg)).max().unwrap();
 
         if score > maxscore {
             maxscore = score;
@@ -46,10 +62,18 @@ pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
             }
         }
 
+        let multiplier =
+                if maxdist > maxvel && maxdist > 100 { max(1, (maxdist - 100) / maxvel) }
+                else { 1 };
+
+        // println!("iter={} multiplier={} maxdist={} maxvel={}", iter, multiplier, maxdist, maxvel);
+
         for i in 0..dots.len() {
-            pts[i].0 += vels[i].0;
-            pts[i].1 += vels[i].1;
+            pts[i].0 += multiplier * vels[i].0;
+            pts[i].1 += multiplier * vels[i].1;
         }
+
+        iter += multiplier;
     }
 
     let mut part1 = String::new();