Helper get_all_neighbors (in a grid) function - python

Question

So a little context to understand the code:

This is a helper function to solve a bigger problem here
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
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?

Travel "right and down" diagonally, or "either right or down"? — Reinderien
– Reinderien, Commented Oct 25, 2021 at 17:37
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. — Reinderien
– Reinderien, Commented Oct 25, 2021 at 17:49
@Reinderien Ok duly noted. I'll return with the rest of the code once I have it done, thanks for the input. — Sergio Bost
– Sergio Bost, Commented Oct 25, 2021 at 17:50
@SergioBost Don't you end up with all the cells (i,j) with i and/or j >= than x,y in your collection? — kubatucka
– kubatucka, Commented Oct 25, 2021 at 20:18

riskypenguin · Accepted Answer · 2021-10-25 19:26:21Z

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

Very clear explanation, thanks. I'll make sure to be more thorough next time around. — Sergio Bost
– Sergio Bost, Commented Oct 25, 2021 at 18:42

Stack Exchange Network

Helper get_all_neighbors (in a grid) function - python

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Helper get_all_neighbors (in a grid) function - python

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions