Discussion on: AoC Day 11: Chronal Charge

[Ali Spittel]

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()))

[Mustafa Haddara]

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

what was the pattern?

[Ali Spittel]

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

[Mustafa Haddara]

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

[Ali Spittel]

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

[Anant Jain]

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 :)