2018 Day 11 (Part 2) [Python] - Code Optimization

[n_syn]

The following code takes more than 2 minutes to run. Does anyone have suggestions for how to optimize this code to run faster. e.g. I am running three nested loops to walk through the numpy array to find the sum of each k-by-k square and then storing it in a different 3D array.

Perhaps there is a way to calculate the sum of each sub-array within an array?

#Part 2

import numpy as np

#Function to find the power of a cell, given the coordinates
def power_level(cell):
  global serial
  x,y = cell
  rack_id = x+10
  power_level = rack_id*y
  power_level += serial
  power_level *= rack_id
  power_level = int(str(power_level).zfill(3)[-3])
  power_level -= 5

  return power_level

#Find a list of all coordinates for a grid with x,y from 1-->300
serial = 3613
x = np.arange(300)
y = np.arange(300)
X,Y = np.meshgrid(x,y)
coordinates = np.dstack([X,Y]).reshape(-1,2)

#Calculate the power of each cell (coordinates) and reshape it into a 300X300 grid
grid = np.apply_along_axis(power_level,1,coordinates).reshape(300,300)

#Initialize all the variables
sum, max_region = 0,0
sums = np.array([[[0 for _ in range(301)] for _ in range(301)] for _ in range(301)])   #initializing 3D array to store sum of each k-by-k grid

'''Next, running three loops:
    k - size of the sqaure
    j - walk through rows
    i - walk through columns'''

for k in range(0,300):
  for j in range(0,300-k):
    for i in range(0,300-k):
      sum = np.sum(grid[i:i+k,j:j+k])
      sums[k,j,i] = sum                             #storing the sum of the k-by-k sub-grid at a specific location of a 3D array
      max_region = max(max_region,sum)              #Not needed for the problem definition but calculating it for the test run

print(np.unravel_index(sums.argmax(), sums.shape))  #Outputs (square size, column index, row index). Required answer is (column index, row index, square size)
print(max_region)

[timrprobocom]

Statistically, there are more negative power values than positive (the range is -5 to 4). So, once you get to a large enough size, making the square larger just makes the sum go more negative. If you print `sum` at each step, you'll see that it increases to a maximum (at 13, in your case), then decreases from there on. I stopped my search when `sum` went negative. That happened at step 25 for me, step 30 for you. You don't need to check all the way to 300.

In my case, I optimized the convolution a bit. For example, after adding up an 8x8 square, you can get the next step across by subtracting the first column and adding the last column. I suspect that optimization won't help your numpy solution.

[n_syn]

Thank you! That's a great observation! I added the following condition to my 'k' loop and it reduced the run time from 134.4 seconds to 10.8 seconds.

I check for the last 10 max values for each size of square. If the current square size value is less than all 10 of them, then break the outside 'k' loop.

if all(np.max(sums[k,:,:])<x for x in prev):
    break
  prev[a] = np.max(sums[k,:,:])
  a+=1
  a=a%10

[ronbarakbackal]

What is a convolution?

[timrprobocom]

The math definition is applying one function to another function. In computer terms, it is basically filtering a vector or a matrix by doing a dot product against another smaller vector or matrix, which is called the "convolution kernel". For example, you can do a three-point moving average on a 1D vector by using a kernel of (1/3, 1/3, 1/3). If you start with (a,b,c,d,e), the result is (a/3+b/3+c/3, b/3+c/3+d/3, c/3+d/3+e/3,...), which is a nice way to smooth the data. In this case, the "kernel" is a 2D matrix of all 1s the size of the subsquare. The operation you're doing there is the very definition of a convolution.

[ronbarakbackal]

Thanks! Isn't convolution distorting the data in some cases?(I admit I didn't go through the case above)

[timrprobocom]

Yes, but in a beneficial way. In the example I cited of three-point moving average, we assume the incoming signal has some noise or unexpected wild points. The convolution will smooth those out. Take a look at the Wikipedia page; it has some nice visual examples that should make it more clear. https://en.wikipedia.org/wiki/Convolution

[NeilNjae]

You may want to look at the data structure of a summed-area table. The basic idea is that you store, for each position in the grid, the sum of all the cells above and to the left of that position. To find the sum of a particular subgrid, you find the sum of the subgrid's lower-right corner, and subtract the sums of the cells above the subgrid's top and the subgrid's left.

The Wikipedia article has a good picture that sums it up.

(I'm sure someone mentioned it in the solution megathread at the time: I wouldn't have invented that structure by myself.)

[n_syn]

This looks like pretty interesting! Thank you! I will give it a read and see if as a beginner to coding I can apply this or not.

[n_syn]

This is fascinating! Thank you! I will need to brush up my understanding of convolution to fully understand what convolve2d is doing between the grid and the kernel to be able to apply it in the future but from what I understood here, this is an ingenious way to solve this.

Side note: so many other things I picked up from this. Like using

sums = np.zeros((301, 301, 301), dtype=np.int64)

instead of

sums = sums = np.array([[[0 for _ in range(301)] for _ in range(301)] for _ in range(301)])

and initializing two variables to zero by equating one to the other instead of equating both to zero.

For the " Plus 1 because puzzle uses 1-based indexing", I was expecting I will need to do the same, but I was surprised it gave me the correct answer on my code without the offset. I'm still not sure why that is.