Find the correct path through a 5 x 5 grid (coderbyte 'Correct path')

Question

I've completed the following coderbyte question and would like feedback as to whether it follows Python best practices, is efficient and so forth.

The coderbyte problem:

Have the function calcpath(str) read the str parameter being passed, which will represent the movements made in a 5x5 grid of cells starting from the top left position The characters in the input string will be entirely composed of: r, l, u, d, ?. Each of the characters stand for the direction to take within the grid, for example: r = right, l = left, u = up, d = down. Your goal is to determine what characters the question marks should be in order for a path to be created to go from the top left of the grid all the way to the bottom right without touching previously travelled on cells in the grid.

For example: if str is "r?d?drdd" then your program should output the final correct string that will allow a path to be formed from the top left of a 5x5 grid to the bottom right. For this input, your program should, therefore, return the string rrdrdrdd. There will only ever be one correct path and there will always be at least one question mark within the input string.

Examples

Input: "???rrurdr?", Output: "dddrrurdrd"

Input: "drdr??rrddd?", Output: "drdruurrdddd"

Code:

import itertools
import numpy as np


def calcpath(s):
    _map = {"d": 1, "u": -1, "l": -1, "r": 1}

    q_count = s.count("?")
    move_combinations = itertools.product(_map.keys(), repeat=q_count)

    while True:
        arry = np.array([[0]*5 for i in range(5)])
        arry[0][0] = 1  # start at 0, 0

        current_x = 0
        current_y = 0

        try:
            moves = next(move_combinations)
        except StopIteration:
            return None

        ss = s[::].replace("?", "{}").format(*moves)

        for move in ss:

            if move in "lr":
                current_x += _map.get(move)
            elif move in "du":
                current_y += _map.get(move)

            if current_x < 0 or current_x > 4:
                break
            elif current_y < 0 or current_y > 4:
                break
            elif arry[current_x][current_y]:
                break
            else:
                arry[current_x][current_y] = 1

        # check for completion
        if (current_x, current_y) == (4, 4):
            return ss

assert calcpath("???rrurdr?") == "dddrrurdrd"
assert calcpath("drdr??rrddd?") == "drdruurrdddd"
assert calcpath("??ddd??lrlddd?") == None

Answer 1

Unnecessary Import

numpy is not required for this challenge. You are using none of its special capabilities. The following:

arry = np.array([[0]*5 for i in range(5)])

could easily and simply be replaced with

arry = [[0] * 5 for _ in range(5)]

Notice the throw-away _ variable being used for the unused loop comprehension variable. If you don't use it, don't name it.

StopIteration

It is rarely necessary to use try: ... except: ... to catch the StopIteration exception. You just need to use a loop structure.

    move_combinations = itertools.product(_map.keys(), repeat=q_count)

    while True:
        arry = np.array([[0]*5 for i in range(5)])
        arry[0][0] = 1  # start at 0, 0

        current_x = 0
        current_y = 0

        try:
            moves = next(move_combinations)
        except StopIteration:
            return None

        ...

could be written much more simply as:

    for move in itertools.product(_map.keys(), repeat=q_count):

        arry = [[0] * 5 for _ in range(5)]
        arry[0][0] = 1  # start at 0, 0

        current_x = 0
        current_y = 0

        ...

    return None

Variable Names

_map is an odd local variable name. A single leading underscore is used to signify private/protected object members. Local variables are never visible in an outer scope, so do not need to be flagged as "private". A trailing underscore is usually used to avoid name collisions, in which case the variable should be named map_. But confusion may be better avoided by naming the variable not with its type but with its role; this dictionary mapping contains directions, so it may be better named directions.

arry is also a poor name. visited would be a better choice.

True / False

You are storing 0 and 1 in your arry matrix, and then testing for the truthiness of arry[current_x][current_y]. It would be clearer to store False and True in these.

visited = [[False] * 5 for _ in range(5)]

...

    ...
    elif visited[current_x][current_y]:
        break
    else:
        visited[current_x][current_y] = True

Unnecessary Slicing

Neither s.replace(...) nor s[::].replace(...) will modify the original s contents. There is no need to use slicing to create a copy prior to the replace operation:

        ss = s.replace("?", "{}").format(*moves)

(And as Carcigenicate mentioned, move it out of the loop)

Magic Numbers

The code is littered with 4's and 5's. What if you want to change this to work with a 5x6 or 4x7 grid? You need to correctly change a lot of numbers. Perhaps you should pass in the size of the grid, instead of using hard-coded values:

def calcpath(s, rows=5, columns=5):

    start = (0, 0)
    end = (columns - 1, rows - 1)

    ...

       visited = [[False] * columns for _ in range(rows)]
       current_x, current_y = start

       ...

           if current_x < 0 or current_x >= columns:
               break
           ...

       if (current_x, current_y) == end:
           ...

    ...

Optimizations

There should be several obvious checks you can make. For the 5x5 grid case:

• len(s) must be even
• len(s) must be >= 8
• len(s) must be < 25

Moreover, the directed counts of the left-right and up-down moves will produce a reduced search space.

With s = "???rrurdr?":

>>> print(*(sum(c == dir for c in s) for dir in "lrud?"))
0 4 1 1 4

There are 0 lefts, 4 rights, so we need to move +0 right to yield a net +4 right; there is 1 up and 1 down, so we need to move +4 down to yield a net +4 down. We have 4 moves up for grabs, so they all need to be downs. There is no point checking for combinations including up, left and right moves!

You can expand the logic of this for other cases: "drdr??rrddd?" has a net 4 right, 5 down, so the additional moves must include 1 up. Then, it could add either a left/right pair, or an up/down pair, so you only need to check permutations of "ulr" and "uud", for a total of 12 possibilities, instead of your \$4^3\$ search space.

Answer 2

calcpath should be calc_path as per PEP8. This seems like it's a name decided on by the challenge, but I thought I'd mention it.

---

_map = {"d": 1, "u": -1, "l": -1, "r": 1}

This should have a better name. "map" indicates that it's a mapping between things, but doesn't give any more information than that.

I'd change it to something like:

DIRECTION_CHAR_TO_OFFSET = {"d": 1, "u": -1, "l": -1, "r": 1}

Capitalized to indicate that it's a constant. I'd also move it outside of calc_path. Its definition isn't dependent on anything within the function, and that function is quite long, so I think moving some stuff out would be a good idea.

Arguably, a Enum would be a better fit here as well if you wanted to be strict. Using strings as keys opens the door for accidental mistypes, although the only opportunity for it here is in the definition of DIRECTION_CHAR_TO_OFFSET since all the data is supplied by the challenge.

---

The replace("?", "{}") bit should be taken out of the loop for performance reasons. It likely won't make any noticeable difference, but that part is entirely reliant on s which doesn't change, so there's no point in recalculating it repeatedly. There's also no reason to do a slice copy of the string before calling replace on it. replace returns a new string. Strings are immutable, so it can't modify s:

move_mask = s.replace("?", "{}")
. . .
while True:
    . . .
    ss = move_mask.format(*moves)

---

[AJ's for suggestion is a much better idea than what I'm about to propose. Just go with what he suggests. I'm going to keep this section though to indroduce := in case you don't know about it.]

You can get rid of that try if you make use of Python 3.8's assignment expression, and next's second argument:

while moves := next(move_combinations, None):
    . . .

When move_combinations is exhausted, next will return None which will end the loop. This isn't exactly equivalent as your original version since it isn't returning directly from the loop. It does behave the same though since there is nothing after the loop. I added a return None at the bottom though to comply with PEP8.

I won't say that I completely recommend this way since it requires the latest Python and uses new, fancy features. It does help reduce some bulk though.

---

DIRECTION_CHAR_TO_OFFSET.get(move)

Can simply be

DIRECTION_CHAR_TO_OFFSET[move]

Again, this isn't exactly equivalent, but it acts the same here. I'd say though that using [] is better in this scenario. get will return None on a bad lookup (should one be allowed to happen due to a typo or something). With None returned, you'll attempt to add None to current_x, which will cause:

TypeError: unsupported operand type(s) for +=: 'int' and 'NoneType'

Using [] though will cause a KeyError:

KeyError: 'a'

I think the latter gives more useful debugging information than the former.

---

if current_x < 0 or current_x > 4:
    break
elif current_y < 0 or current_y > 4:
    break

This can make use of operator chaining if you're willing to add some negation to the condition:

if not 0 <= current_x <= 4:
    break
elif not 0 <= current_y <= 4:
    break

And since those both result in the same operation, they can be combined:

if not (0 <= current_x <= 4 and 0 <= current_y <= 4):
    break

I adjusted the condition a bit using one of DeMorgan's Laws:

not (A and B) = not A or not B

---

---

import itertools
import numpy as np

DIRECTION_CHAR_TO_OFFSET = {"d": 1, "u": -1, "l": -1, "r": 1}

def calc_path(s):
    q_count = s.count("?")
    move_mask = s.replace("?", "{}")

    move_combinations = itertools.product(DIRECTION_CHAR_TO_OFFSET.keys(), repeat=q_count)

    while moves := next(move_combinations, None):
        arry = np.array([[0]*5 for i in range(5)])
        arry[0][0] = 1  # start at 0, 0

        current_x = 0
        current_y = 0

        ss = move_mask.format(*moves)

        for move in ss:
            if move in "lr":
                current_x += DIRECTION_CHAR_TO_OFFSET[move]
            elif move in "du":
                current_y += DIRECTION_CHAR_TO_OFFSET[move]

            if not (0 <= current_x <= 4 and 0 <= current_y <= 4):
                break
            elif arry[current_x][current_y]:
                break
            else:
                arry[current_x][current_y] = 1

        # check for completion
        if (current_x, current_y) == (4, 4):
            return ss

    return None

assert calc_path("???rrurdr?") == "dddrrurdrd"
assert calc_path("drdr??rrddd?") == "drdruurrdddd"
assert calc_path("??ddd??lrlddd?") == None