### re: AoC Day 11: Chronal Charge VIEW POST

lolol this is incredibly slow, but I noticed a pattern and was able to easy escape based on it. I think using numpy is the way to go in order to speed this up.

``````SERIAL_NUMBER = 1308

def get_power_level(x, y):
rack_id = x + 10
power_level = rack_id * y
power_level += SERIAL_NUMBER
power_level *= rack_id
hundreds_digit = int(str(power_level)[-3]) if power_level > 100 else 0
return hundreds_digit - 5

def gen_grid():
grid = []
for x in range(300):
row = []
for y in range(300):
row.append(get_power_level(x+1, y+1))
grid.append(row)
return grid

def get_box(grid, row, col, size):
_sum = 0
for x in range(0, size):
for y in range(0, size):
_sum += grid[row + x][col + y]
return _sum

def find_max_subgrid(grid):
max_sum = 0
coordinates = [0, 0]
for size in range(3, 300):
for i in range(300 - size):
for j in range(300 - size):
box_sum = get_box(grid, i, j, size)
if box_sum > max_sum:
max_sum = box_sum
coordinates = [i + 1, j + 1, size]
print(coordinates, size, max_sum)
return coordinates, max_sum

print(find_max_subgrid(gen_grid()))
``````

I noticed a pattern and was able to easy escape based on it.

what was the pattern?

It increased to the high point then decreased from there! After it went negative it stayed negative.

And it kept going negative even after you switched block sizes? Huh, cool.

yup! positive up to a point, then all negative!

A speed up I can suggest: pre-compute another grid, say `sumGrid` where `sumGrid[x][y] = sum(grid[i][j]` where `i` is in `range(x, N)` and `j` in `range(y, N)`

So, each element in this new `sumGrid` is the sum of all elements below and right to it, including itself.

Then `sum(x,y,size)` is now just:

``````sum(x,y,size) =
sumGrid[x][y]
- sumGrid[x][y+size]
- sumGrid[x+size][y]
+ sumGrid[x+size][y+size]
``````

As an example, `sum(3,2,5)` would look like this: We need to add that 4th last term `sumGrid[x+size][y+size]` since we have subtracted it twice as part of terms 2 and 3. The solution now avoids two inner `for` loops — making it much faster :)

code of conduct - report abuse  