🌧 Rainier Ababaolast updated: 6/4/20
⟨ back to writing

# Perco-koan

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