Helper get_all_neighbors (in a grid) function - python

Question

So a little context to understand the code:

1. This is a helper function to solve a bigger problem here
2. Quick summary: A Knight is in a dungeon/2D grid of Ints, starts at 0,0 and must reach the last cell at the bottom right to find the princess
3. The purpose of this helper function is to return all neighbors of a given starting point, given some constraints:

• The knight's starting point is always upper-left - 0,0
• The knight can only travel right or down, 1 cell at a time
• The target / base case is bottom right of the grid/dungeon where the princess is

Code below

def get_neighbors(d, x, y, coll):
 # d == abbr. for dungeon is our board
 # For example:
 #[-8, -13, -8]
 #[-24, 28, 28]
 #[-13, -13, -30]
 # coll == abbr. for collection, how I keep track of all returned neighbors
 # We start our knight in the upper left hand corner
 row_length = len(d)
 col_length = len(d[0])
 if (x,y) == (row_length - 1, col_length - 1): # Once we reach the bottom right corner we are done
 return coll
 for dx in range(0, 2):
 for dy in range(0, 2):
 if dx == 0 and dy == 0 or dx == 1 and dy == 1: # If cell is not to the bottom or to the right, skip it
 continue
 if x + dx > len(d[x]) - 1 or y + dy > len(d) - 1: # Out of bounds check
 continue
 neighbor = (x + dx, y + dy)
 # I'm wondering why I even need this line, if I am only going to the right and to the bottom each time
 # Why do I need to guard against duplicates
 if neighbor not in coll:
 coll.append(neighbor)
 get_neighbors(d, x + dx, y + dy, coll)
 return coll

Is there anything I should do differently?

• Reinderien: Travel "right and down" diagonally, or "either right or down"?
• Sergio Bost: @Reinderien Right or down, no diagonal, good point
• Reinderien: I think you need to show much more of your code, not just this function - because some of the issues with this code, when fixed, will require a different calling convention.
• Sergio Bost: @Reinderien Ok duly noted. I'll return with the rest of the code once I have it done, thanks for the input.
• kubatucka: @SergioBost Don't you end up with all the cells (i,j) with i and/or j >= than x,y in your collection?

Answer 1

Welcome to CodeReview!

Disclaimer: As noted in the comments, a review of this code is limited since I don't know the entire codebase / algorithmic approach. So this review is limited to this function's current implementation.

---

Naming

d and coll are hard-to-understand names, dungeon and collection are already an improvement. collection however is almost meaningless, as it says nothing about the data stored in the variable. Since the function is called get_neighbors, the return value should probably be called neighbors (coll.append(neighbor) is another hint). If you find yourself needing comments to explain your variable names, you should change them. Reading this line # d == abbr. for dungeon is our board is already a lot of unnecessary work compared to simply reading dungeon in the first place. Stick to meaningful and readable variable names, that do not require further explanation.

---

Type annotations

Including type annotations significantly increases the readability of your code. It also allows for better error-checking:

def get_neighbors(dungeon: list[list[int]], x: int, y: int, neighbors: list[tuple[int, int]])\
 -> list[tuple[int, int]]:

---

Miscellaneous

---

You might have rows and columns the wrong way round. I would expect dungeon to be a list of rows, y to indicate the row and x to indicate the column. Your current implementation handles dungeon like a list of columns.

---

if x + dx > len(d[x]) - 1 or y + dy > len(d) - 1: # Out of bounds check:

• You don't need to access len(d[x]) (d[x] should also be d[y] by the way), as dungeon is a rectangle, simply use len(d[0])
• You already calculated and stored row_length & col_length, use them

---

for dx in range(0, 2):
 for dy in range(0, 2):
 if dx == 0 and dy == 0 or dx == 1 and dy == 1:
 continue

should be way simpler:

for dx, dy in ((1, 0), (0, 1)):

While this might be fine for only two directions, a module- or class-level constant DIRECTIONS = ((1, 0), (0, 1)) would be even better, especially once the number of directions increases.

for dx, dy in DIRECTIONS:

---

# I'm wondering why I even need this line, if I am only going to the right and to the bottom each time
# Why do I need to guard against duplicates
if neighbor not in coll:
 coll.append(neighbor)

In you current implementation you need to perform this check, because different paths can lead to the same cell. Consider the simplest example of the two paths (1. DOWN -> 2. RIGHT) and (1. RIGHT-> 2. DOWN).

• Sergio Bost: Very clear explanation, thanks. I'll make sure to be more thorough next time around.