2
\$\begingroup\$

I have a rectangle of . (platforms) and # (obstacles). I can start at any platform in the top row and go to the left, right or down to another platform. I cannot visit a platform twice. I need to find the longest path from the top row to the bottom row.


Example input:

#.....#...
#.........
..#.....#.
..#....#.#
..###.#..#

Example output:

21

Explanation:

#54321#...
#6789abc..
..#hgfed#.
..#ijk.#.#
..###l#..#

I marked the longest path as a sequence 123456789abcdefghijkl, which includes 21 platforms.


I tried to use Depth-First-Search with memoization.
Here is the code:

def longest_path(grid):

    if not grid or not grid[0]:
        return 0

    memo = {}

    def dfs(row, col):
        memoKey = [row, col]
        if col == 0:
            memoKey.append(('#', grid[row][1]))
        elif col == len(grid[0]) - 1:
            memoKey.append((grid[row][col - 1], '#'))
        else:
            memoKey.append((grid[row][col - 1], grid[row][col + 1]))

        memoKey = tuple(memoKey)

        if memoKey in memo:
            return memo[memoKey]

        max_path = 0

        directions = []
        if row == len(grid) - 1:  # Reached the bottom
            directions = [(0, 1), (0, -1)]  # Right, Left
        else:
            directions = [(0, 1), (1, 0), (0, -1)]  # Right, Down, Left

        # Mark the current cell as visited
        grid[row][col] = '#'

        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            if 0 <= new_row < len(grid) and 0 <= new_col < len(grid[0]) and grid[new_row][new_col] == '.':
                path_length = dfs(new_row, new_col)
                max_path = max(max_path, 1 + path_length)

        # After exploring all directions, backtrack by marking the cell as unvisited
        grid[row][col] = '.'

        memo[memoKey] = max_path
        return max_path

    max_path = 0
    for col in range(len(grid[0])):
        if grid[0][col] == '.':
            max_path = max(max_path, dfs(0, col))

    return max_path + 1

My memo keys might seem weird. That is because I store the state of the cell to the left and right to prevent visiting a platform twice.
Example for why you need this:
Input:

##..
....
....

Imagine starting at (0, 3) and going to (1, 3). Then you calculate the longest path from (1, 3), and it turns out to be 8, by going to (1, 0), then to (2, 0), and to (2, 3). You memoize this using (1, 3) as the key. Then, you try starting at (0, 2) and going down and to the right. Then you take the memoized value of 8, and it results in a path of length 10. However, this results in visiting (1, 2) twice.


That algorithm was too inefficient for my goals. Suggestions about another algorithm or an optimization of the existing one are appreciated.

\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

test suite

Standard advice in any language: Include an automated test suite with your target code. How do we know the code you write isn't 100% perfect all the time? Because you're posting a request for help. Plus, you're human. Making it easy for strangers to run your code means it will be easy for you to run your code when you revisit it next year.

Standard advice for python language: Avoid nesting defs.

Why? Other than the whole global variable coupling thing? Because they make it very difficult for a subsequent maintenance engineer to come along and write missing unit tests -- the nested functions are inaccessible.


lint

        memoKey = [row, col]

Pep-8 asks that you name it memo_key.

On first reading I thought you intended a (row, col) tuple instead. But it turns out this is a fancier datastructure than that. Its format needs to be documented.


solution

I understand that the problem statement merely asks for "number of platforms". Still, it makes me sad that after laboriously computing 21 we still can't recover that nice 123...jkl path diagram we see in OP. Consider changing your API to export the winning path.

It seems like this could have a positive effect on how instructive a test suite is, and on time to debug issues after attempting a refactor.


spurious comment

        if row == len(grid) - 1:  # Reached the bottom

Well, actually this is kind of helpful. But I wish it wasn't, that is, I wish there was no need for it. Prefer to define width, height temp variables so the code explains itself.


docstring

Your depth first search routine doesn't have one. Nor does longest_path, nor the module. Nor did you include any helpful # comments describing the memo key.

Maybe you feel your code is self explanatory, and it reads as cleanly as sonnet 18. I beg to differ. What I'm specifically looking for is invariants and representations. We're doing DP here, cool. But tell me how you're remembering results so we needn't re-compute them, describe the plan, the datastructure. I see three .append()'s of a pair, but the meaning of pair[0] and pair[1] are not self-evident upon first reading.

I store the state of the cell to the left and right to prevent visiting a platform twice.

Good. Now expand on that. In the source code, where it will be available to a maintenance engineer some months down the road.

Or consider making a memo of (row, col) in a set, which we consult during planning so we don't make a prohibited move.

This seems tedious:

        if col == 0:
            memoKey.append(('#', grid[row][1]))
        elif col == len(grid[0]) - 1:
            memoKey.append((grid[row][col - 1], '#'))
        else:
            memoKey.append((grid[row][col - 1], grid[row][col + 1]))

Consider pre-processing the input map to add '#' boundary lines around it, for example on the left and right walls. It's unclear why we're checking col for out-of-bounds, but not row. I am left wondering: Why is horizontal travel special, why is it handled differently from vertical travel?

OIC. Re-reading the problem statement, there's a requirement that Y coordinate be monotonic, we can go down but never up. Hmmm.

            directions = [(0, 1), (1, 0), (0, -1)]  # Right, Down, Left

Thank you for those (dy, dx) pairs, that's brilliant, very helpful. The logic testing for whether new row,col is feasible is quite clear.

        # Mark the current cell as visited
        grid[row][col] = '#'

nit: IDK, maybe choose an alternate character, such as @, to distinguish between "this was impassable from the outset" and "this is currently impassable due to being visited". Which would trivially change any == '#' tests into != '.'. I'm just looking for more informative debugging sessions, is all.


algorithm

Let's exploit the "no going up!" rule, recursively. Consider a single-row maze -- the bottom row. We will pretend there is an imaginary row of just '.' platforms above it, so we could enter the row from any column position.

Now we have a very simple problem. For entry at any of the column positions, report the maximum possible value, and memoize those results.

Now go up a row, and for all column positions try to maximize the value of L/R traversal within the row plus the memoized value of exiting downward.

Repeat till all rows are consumed.

\$\endgroup\$
2
  • \$\begingroup\$ Thank you very much for the suggestions! However, the improvement of the algorithm is a bit unclear to me. Could you please provide an example? \$\endgroup\$ Dec 6, 2023 at 17:17
  • \$\begingroup\$ It's unclear why we're checking col for out-of-bounds, but not row. The reason for that, is that we are not actually checking for out of bounds. We check for side cases, where there is no left/right cell. There is no vertical analog, as I don't check the cell under the current one. There can't be an out of bounds, because i check for that while testing the next platforms. \$\endgroup\$ Dec 6, 2023 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.