This week I messed up on an question whose solution involved a BFS over an element's left, right, and bottom neighbors in a grid. This post exists to make sure I don't mess it up again.
This requires writing the function to get the neighbor coordinates of the element in a grid, like this...
grid = \ [[0 0 0 1 0 0], [0 0 1 X 1 0], [0 0 0 1 0 0]] # let's say we want the neighbors of the coordinate where 'X' is get_neighbors(grid, 1, 3) # -> [(1, 2), (2, 3), (1, 4)]
The part in question where I messed up on is my version of a koan (that was the word, Ben!) that I learned from competitive programming class (thanks Arnav, though I doubt you'll ever read this). This is the incorrect version of a function that I should have really committed to memory by now...
def get_neighbors(grid, visited, i, j): dx = [-1, 0, 1] dy = [0, -1, 0] return [(i+x, j+y) for x, y in zip(dx, dy) \ if legal(grid, i+x, j+y) \ and grid[i+x][j+y] == PASS \ # problem-dependent and (i+x, j+y) not in visited]
Do you see it??
There are a few things wrong with it, based on my forgetting that Cartesian coordinates
!= the convention for multi-dimensional array indexing. When I'm coding it and saying it out loud in my head, like "Yeah, the change in
x will be
-1, change in
y will be
0 if you go left,
-1 if you go bottom", it makes total sense, but it's wrong. Applying a
-1 transformation to the index associated with
y (which is not
j, by the way, but
i, so that was another mistake) is wrong -
that will examine the neighbor above the input coordinate.
This is the correct way to get the left, right, and bottom neighbors:
def get_neighbors(grid, visited, i, j): di = [0, 1, 0] dj = [-1, 0, 1] return [(i+y, j+x) for y, x in zip(di, dj) \ if legal(grid, i+y, j+x) \ and grid[i+y][j+x] == PASS \ # problem-dependent and (i+y, j+x) not in visited]
Do you see the difference? I flipped the indices I made the association with x-y coordinates for, and changed the
Another interesting problem came up today, which involved a series of sums of a sub-matrix of size K*K in a matrix of size N*M. Here's a candidate for a new personal koan:
def subsum(grid, i1, i2, j1, j2): psum = 0 for i in range(i1, i2): psum += sum(grid[i][j1:j2]) return psum for i in range(len(grid)-K+1): for j in range(len(grid)-K+1): subsum(grid, i, i+K, j, j+K) # do something with this
Do you think there is a better way to do this? Please email me, so I can get a job 😅