# test suite

Standard advice in any language: Include an automated
[test suite](https://docs.python.org/3/library/unittest.html#unittest.TestCase)
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 `def`s.

Why? Other than the whole
[global variable](https://en.wikipedia.org/wiki/Global_variable)
[coupling](https://en.wikipedia.org/wiki/Coupling_(computer_programming))
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](https://peps.python.org/pep-0008/#naming-conventions)
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](https://en.wikipedia.org/wiki/Dynamic_programming)
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 it's unclear
what `pair[0]` _means_, and how it differs from `pair[1]`.

> 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

Sooo, here's the aspect of the current DFS that I'm dissatisfied with.
Imagine the bottom portion of the maze is boring switchbacks that keep
taking us from left margin to right, back to left, back to right,
eventually we exit at the bottom.
And the top of the maze is pretty free, only a few obstacles, many starting paths.
So we will be forced to begin with one of those paths, and then we spend
a lot of time traversing those boring switchbacks.
Then we try another of those paths, plus switchbacks.
Yeah, I'm getting tired of the switchbacks, they're time consuming,
and the maze fundamentally just isn't all that hard.

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.