# Perco-koan

October 07, 2016This 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 ðŸ˜…