static INPUT: i32 = 9005;
static WIDTH: usize = 300;
static HEIGHT: usize = 300;

type Grid = Vec<Vec<i32>>;

fn build_grid() -> Grid {
  let mut grid = vec![vec![0; WIDTH]; HEIGHT];
  for y in 1..HEIGHT + 1 {
    for x in 1..WIDTH + 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, 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 {
      total += grid[y][x];
    }
  }
  total
}

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: usize = 0;
  let mut my: usize = 0;
  let mut msize: usize = 0;
  for s in 1..301 {
    println!("Debug: Running for size = {}", s);
    for y in 0..HEIGHT - s + 1 {
      for x in 0..WIDTH - s + 1 {
        let sum = sum_subsquare(&grid, (x, y), s);
        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);
}