1 files changed, 26 insertions, 6 deletions
diff --git a/day11/src/main.rs b/day11/src/main.rs
index 37e1a00..2da851f 100644
--- a/day11/src/main.rs
+++ b/day11/src/main.rs
@@ -1,7 +1,10 @@
+use std::collections::HashMap;
+
 static INPUT: i32 = 9005;
 static SIZE: usize = 300;
 
 type Grid = Vec<Vec<i32>>;
+type Identifier = (usize, usize, usize);
 
 fn build_grid() -> Grid {
   let mut grid = vec![vec![0; SIZE]; SIZE];
@@ -29,14 +32,29 @@ fn nth_digit(number: i32, n: u32) -> i32 {
   (number % 10i32.pow(n)) / 10i32.pow(n - 1)
 }
 
-fn sum_subsquare(grid: &Grid, pos: (usize, usize), size: usize) -> i32 {
-  let mut total = 0i32;
-  for y in pos.1..pos.1 + size {
-    for x in pos.0..pos.0 + size {
+fn sum_subsquare(grid: &Grid, cache: &mut HashMap<Identifier, i32>, id: Identifier) -> i32 {
+  let size = id.2;
+  if size == 1 {
+    grid[id.1][id.0]
+  } else {
+    if cache.contains_key(&id) {
+      return cache[&id]
+    }
+    let sub_id = (id.0, id.1, id.2 - 1);
+    let sub = sum_subsquare(&grid, cache, sub_id);
+    let mut total = 0i32;
+    for y in id.1..id.1 + size {
+      let x = id.0 + size - 1;
+      total += grid[y][x];
+    }
+    for x in id.0..id.0 + size - 1{
+      let y = id.1 + size - 1;
       total += grid[y][x];
     }
+    let sum = sub + total;
+    cache.insert(id, sum);
+    sum
   }
-  total
 }
 
 fn visualize(grid: &Grid) {
@@ -54,11 +72,13 @@ fn main() {
 
   let mut max_sum = std::i32::MIN;
   let (mut mx, mut my, mut msize): (usize, usize, usize) = (0, 0, 0);
+  let mut cache: HashMap<Identifier, i32> = HashMap::new();
   for s in 1..SIZE + 1 {
     println!("Debug: Running for size = {}", s);
     for y in 0..SIZE - s + 1 {
       for x in 0..SIZE - s + 1 {
-        let sum = sum_subsquare(&grid, (x, y), s);
+        let id = (x, y, s);
+        let sum = sum_subsquare(&grid, &mut cache, id);
         if sum > max_sum {
           max_sum = sum;
           mx = x;