๐ŸŒง Rainier Ababaolast updated: 1/21/21
โŸจ back to writing


Rainier Ababao ยท October 07, 2016 ยท 3 min read

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, x 0 y -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 -1 to +1.

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[0])-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 ๐Ÿ˜…

React to this article!