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];
  for y in 1..SIZE + 1 {
    for x in 1..SIZE + 1 {
      if y == 5 && x == 3 {
        print!("");
      }
      let rack_id: i32 = x as i32 + 10;
      let mut level = rack_id * y as i32;
      level += INPUT;
      level *= rack_id;
      level = nth_digit(level, 3);
      level -= 5;

      let xi = (x - 1) as usize;
      let yi = (y - 1) as usize;
      grid[yi][xi] = level;
    }
  }
  grid
}

fn nth_digit(number: i32, n: u32) -> i32 {
  (number % 10i32.pow(n)) / 10i32.pow(n - 1)
}

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
  }
}

fn visualize(grid: &Grid) {
  for line in grid {
    for ch in line {
      print!("{} ", ch);
    }
    print!("\n");
  }
}

fn main() {
  let grid = build_grid();
  // visualize(&grid);

  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 id = (x, y, s);
        let sum = sum_subsquare(&grid, &mut cache, id);
        if sum > max_sum {
          max_sum = sum;
          mx = x;
          my = y;
          msize = s;
        }
      }
    }
  }

  println!("Max sum {} at ({}, {}), size: {}", max_sum, mx + 1, my + 1, msize);
}