re: AoC Day 11: Chronal Charge VIEW POST

FULL DISCUSSION
 

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.

 

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