Optimise day 11

1 files changed, 35 insertions, 21 deletions

diff --git a/2018/src/day11.rs b/2018/src/day11.rs
index 4503561..0be5e61 100644
--- a/2018/src/day11.rs
+++ b/2018/src/day11.rs
@@ -1,44 +1,58 @@
 use std::io;
 use std::io::BufRead;
-use std::ops::Range;
 
 fn power(x: i32, y: i32, serial: i32) -> i32 {
     (y * (x + 10) + serial) * (x + 10) / 100 % 10 - 5
 }
 
-fn optimise(grid: [[i32; 300]; 300], srange: Range<usize>) -> (usize, usize, usize) {
+pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
+    let serial = reader.lines().next().unwrap().unwrap().parse::<i32>().unwrap();
+
+    let grid = {
+        let mut grid = [[0; 300]; 300];
+        for y in 0..300 {
+            for x in 0..300 {
+                grid[y][x] = power(x as i32, y as i32, serial);
+            }
+        }
+        grid
+    };
+
     let mut maxval = i32::min_value();
     let mut maxat = (0, 0, 0);
-    for s in srange {
+    let mut maxval3 = i32::min_value();
+    let mut maxat3 = (0, 0);
+
+    let mut prevs = [[0; 300]; 300];
+    let mut prevs_h = [[0; 300]; 300];
+    let mut prevs_v = [[0; 300]; 300];
+
+    for s in 1..301 {
         for y in 0..301-s {
             for x in 0..301-s {
-                let tot = (0..s).map(|dy| (0..s).map(|dx| grid[y+dy][x+dx]).sum::<i32>()).sum();
+                let lt = prevs[y][x];
+                let right = prevs_v[y][x+s-1];
+                let bottom = prevs_h[y+s-1][x];
+                let rb = grid[y+s-1][x+s-1];
+                let tot = lt + right + bottom + rb;
 
                 if tot > maxval {
                     maxval = tot;
                     maxat = (x, y, s);
                 }
-            }
-        }
-    }
-
-    maxat
-}
-
-pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
-    let serial = reader.lines().next().unwrap().unwrap().parse::<i32>().unwrap();
+                if s == 3 && tot > maxval3 {
+                    maxval3 = tot;
+                    maxat3 = (x, y);
+                }
 
-    let mut grid = [[0; 300]; 300];
-    for y in 0..300 {
-        for x in 0..300 {
-            grid[y][x] = power(x as i32, y as i32, serial);
+                prevs[y][x] = tot;
+                prevs_h[y+s-1][x] = bottom + rb;
+                prevs_v[y][x+s-1] = right + rb;
+            }
         }
     }
 
-    let maxat = optimise(grid, 3..4);
-    let part1 = format!("{},{}", maxat.0, maxat.1);
-
-    let maxat = optimise(grid, 1..301);
+    let part1 = format!("{},{}", maxat3.0, maxat3.1);
     let part2 = format!("{},{},{}", maxat.0, maxat.1, maxat.2);
 
     Ok((part1, part2))