1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
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);
}
|
