Reading Time: 25 minutes

Suppose you have a board that looks something like this:

Your job is to find the shortest path from the start (‘S’) to the end (‘E’). You are allowed to step on any spot with a zero (0) in it. You are not allowed to step on any spot with a one (1) in it. You can go straight up, down, left, or right, but you cannot travel diagonally. How would you find the shortest path?

I was once presented with this question in a one hour live coding interview. It’s the kind of problem that I like to do for fun, or with a pair. In that interview, I failed spectacularly. My first attempt, which forewent algorithmic approaches to first get literally anything working, didn’t work. And at that point I froze. I knew this might happen to me in a live pop challenge, but I did not anticipate that level of freezing. Once that happened, I knew it was over. I didn’t get the job. But the challenge haunted me: I don’t like failing, you see. I suspect you can relate.

This conversation on Twitter re-ignited my memory of the incident and made me want to solve the problem as a take-home (which works better for me than a live interview). This blog post will show you how I went about it and explain the choices I made. I put the solution here and made regular commit checkpoints so you can see how long it took me: about 90 minutes in total, counting the writing of tests, not counting a break I took in the middle to go to the beach (I’m on vacation). I didn’t really consult sources beyond some cursory “how do you do a namedtuple in Python” type stuff. I’m going to walk you through it more or less commit by commit so you’ll see my whole process (including mistakes I made!).

I’m hoping you find this explanation entertaining and informative, either about this problem or about my approach to it. Let’s get started.

I Begin with a test.

Always, kids. A test is not only a regression guardrail, but also a communication tool. It allows me to demonstrate precisely what I’m trying to implement.

I’m not importing a testing framework because, whatever, I didn’t feel like it. So I rolled my own test (I used to use assert for this, but now I print from a conditional because I find the blank AssertionError to be useless for debugging).

In this case I want to know the number of steps it will take me to get through this course. The answer is seven because the shortest path goes right, right, down, down, then two lefts and a down in any order.

When I started this exercise I saw two levels of abstraction: one for modeling the board, and one for the algorithm. I wanted to separate these so I wasn’t futzing with list indices and trying to think about cyclomatic complexity at the same time. Hence the Board abstraction, which I create in the next commit along with a function signature for finding the shortest path:

The tests and implementation all live in the same file, and I just run the file to run the tests. Is this the way I’d develop a production application? No. Again, I’m implementing an algorithm for salt value while on my vacation.

At this point I decided I did want to raise an exception if my test failed rather than just printing, so I did that. But I gave it a message instead of opting for a blank AssertionError:

So now, for the question of the hour:

How will I solve this problem?

Rather than jumping right into code, I write out a little plan for myself:

The example board shows the start in the upper left, but we’re not going to assume it has to be there. It could be anywhere. We are gonna assume a rectangular board (more on that later). My program will:

1. Locate the starting space.
2. From the starting space, travel north (up), south (down), east (right), and west (left). For each of those, create a list of visited spaces that starts with the starting space and ends with that space.
3. We now have a list of possible paths. Eliminate the invalid ones: the ones that cross a square with a 1, or backtrack to a visited node (therefore not the shortest path). There’s actually an elimination possibility I left out here, which we’ll add later (foreshadowing!)
4. From the last space that we added to each path list in step 2, repeat steps 2 and 3 until some ending point. Here I said that that ending point is “When every un-eliminated path reaches the ending space.” We’ll revisit this in the end, too.
5. From the paths we created, find the shortest one and report its length.

Time to get started on the plan.

Step 1: Locate the starting space.

First, of course, a test for the functionality I want:

And then the implementation, which is an instance method on Board:

I find the row that ‘S’ is in, and then I find the column within that row. This implementation assumes exactly one ‘S’ in the board.

Step 2: Begin a list of paths.

I intend to track the possible paths by creating a path that begins at the starting point and then creating copies of it, each with each new step that can be taken from that point, over and over. I begin with a test for this tracking behavior, in which I cheat a little:

What’s the cheat? I force the test to stop before the “over and over” portion of the plan. I want to know I have one step working properly before I release the monster on my whole board. To that end my track_paths method takes in an optional steps parameter, and I will only track paths up to that number of steps. This won’t be used in “production,” which is why it’s kind of cheating—I mean, I guess, unless a production use case wants to call off the program early if the path requires too many steps.

Here’s my stubbed implementation:

BUT WAIT. What’s that ‘Space’ thing up there on lines 36-38 in the test?

That’s a new little construct that I made to represent the location and value of a space on the board. It is, like Board, an abstraction I use to handle implementation details such that I can stay focused on the algorithm itself. I import namedtuple from Python’s collections module and then I do:

That creates the attributes “row,” “column,” and “value” on a little data structure, and I initialize that data structure with those attributes in that order. I can also initialize the data structure with those as named parameters like Space(row=1, column=0, value='S'). For clarity, I should have done that. I didn’t.

Here’s how I implement the basic shape of my idea:

First, I use the find_start method on my inputted Board to figure out where I’m supposed to begin. Then I make a collection of paths and I start it off with one path in there, a path with just one space so far, the starting space. I made this a list. I could have made it a set. I didn’t. That’s arbitrary.

Next, I use the step limit that we delineate on line 54 (automatically defaulting to an intentionally high value for “production” use—I could have used math.INF, I guess, but whatever, I didn’t feel like it). Anyway, as long as I haven’t exhausted the step limit, I extend my paths, each in all viable directions from the final point of the path. So, from the starting point, I’ll run extend(paths, board) and end up with four paths, each with two points: the start, and then the start space’s neighbor in each of the cardinal directions. I’ll also increment a step counter that will track my progress against the max_steps limit.

When the function hits the limit, I return whatever paths I have so far.

So how does extend work?

I create a new, empty list of paths called new_paths. Then for all the existing paths, I grab the last space in that path.

From that space, I try going north, south, east, and west. In each case, I check that there is a space in that direction on the board. If there isn’t, I move on. If there is, get its value from the board, initialize a Space with its location and value, add that to the end of a copy of my original path, and append the extended path to my new_paths list. I return it.

Could I have extracted those common lines of code into a function that I use four times? Eh, sure. I didn’t. I didn’t think the reduction in the code’s verticality would merit the additional level of abstraction. If I were using this same logic in multiple places, maybe I’d abstract it. Or if I were pairing with someone who felt strongly, I’d probably abstract it. But four lines, four times, on top of each other, in the exact same place? I just don’t mind it that much.

This whole implementation differs slightly from my test, which expects that the start space is not in the path. I have decided here to add it. So I add it to the test as well:

I made two other changes: first, I removed the track_paths method from Board and instead pass it to board. I didn’t want Board responsible for both data access and algorithmic design. I also adjusted the success message in each of my tests because they all said “SUCCESS” and now that I have three tests, I want the test output to tell me which ones passed. I made a similar change to the one on line 95 in all the existing tests.

My solution is not recursive.

You’ll note that my explanations so far have said things like “repeat” and “over and over.” I have deliberately avoided the term “recursively” because there are two ways to implement the same thing over and over:

• recursively: call the same function repeatedly until you reach the bottom of the stack of calls, then execute the bottom one, then use the result to execute the second to the bottom one, and so on and so forth until you’re back at the top;
• iteratively: call a function once and return an accumulated value. Check some property of the accumulated value. If it is not satisfied, pass the accumulated value back into the function and call it again. Check the resulting accumulated value of that. Continue until the property is satisfied.

Recursion generates a giant call stack as each instance of the function call waits to be executed. Iteration doesn’t do that, so I tend to like to try that before I try recursion. I talk more about the two approaches in this blog post, if you’re interested.

One thing to note is that, each time I take a step in the current path tracking approach, the number of paths to track gets multiplied. I don’t continue paths that go off-board at the moment, but I also don’t want to keep tracking paths that are invalid (that is, they cross a space with a value of 1). So I’ll add a step now to eliminate invalid paths each time I extend the paths.

Step 3: Eliminate invalid paths.

Test first, of course.

After each step I take extending the paths, I’d like to eliminate any path whose most recent space steps on an invalid 1 value. I also want to keep track of any paths that have succeeded at reaching the end point: these paths, having completed successfully, no longer require extension.

So I add some paths to my test that end with 1 and with ‘E’. I make sure my valid paths exclude the ones that end with 1, and all the ones that end with ‘E’ end up in a completed paths list. Again, that could have been a set, I used a list, that’s arbitrary.

At this point, I wanted to change something.

I wanted to have a way of knowing when my program had successfully eliminated a path due to it going off the board, rather than crossing a 1 or finishing. Now, I could add another condition for that in my function. I decided to be sneakier than that, which might have been a mistake: I’ll let you judge.

If a space in a cardinal direction is on the board, I append it to the path with the value at that space. This is the same as before. Here’s the change:

If a space in a cardinal direction is off the board, I used to do nothing. Now, I instead make a fake space with its location listed as the theoretical location (which is off the board) and insert a value of 1. Why? Recall, 1 is an invalid value and we eliminate paths that end with a 1 space. This will cause my paths that end off-board to show up in the output from extend(), but then get immediately eliminated in eliminate_invalid without an extra condition!

Really I could have made that value anything besides ‘E’ or zero (0), because those are the only values that eliminate_invalid checks for:

I probably should change that 1 value to something more indicative that the space is off board, huh? We can come back to that.

In the meantime, my elimination logic still doesn’t eliminate paths that are backtracking. Lemme fix that. Test first:

I’ll know a backtracked path because a Space with the same values will appear twice. Conveniently, named tuples implement value equality, so as long as all their attributes are the same, Python sees them as the same value. That allows me to do this for the implementation:

I create a set of my path list, which eliminates duplicates, and check whether anything actually got eliminated (resulting in the set of the path spaces having a shorter length than the path itself). If so, the path had a duplicate space, which means that a backtrack happened. Eliminate it!

Step 4: Repeat steps 2 and 3 until “done.”

At this point, I sort of did three things at once, which is bad. Don’t do this. The three things:

1. Add the elimination step after each step of extend.
2. Add the condition on line 90 to say “repeat steps 2 and 3 until done.” For now, “done” is “there are no valid paths in progress.” I’ll come back and change this later, but for now it’s going to work.
3. Start keeping track of the paths completed alongside the paths in progress. We’ll need those when it’s time to find the shortest completed path.

Believe it or not, we’re almost there on a minimum viable implementation at this point. But before we get there, I did want to go back and eat my vegetables, which I skipped at one point because I got too excited: I didn’t test extend(). Crap. Vacation brain. Sorry! Let’s fix that:

Okay, now for the fun part:

Step 5: Select the shortest completed path.

Here we are, finally, in my top-level function, for which the first test I ever wrote for this program is still failing. Time to make it pass.

First, I call track_paths and receive the paths in progress as well as the completed paths. I ignore the paths in progress, which currently would be empty anyhow.

I take the completed paths and get their lengths. I find the shortest of those lengths.

Finally, I return that length, plus any paths that have that length. That’s not actually part of the original test, but I wanted to be able to see my path options. It’s satisfying, you know. I also print the options out of the test so I can look at them.

TA-DA!

My thing works:

For the curious, my list of path options looks like this:

You can check these against my original board if you like.

Tying up Loose Ends

At this point I was pretty pleased with what I had, but not quite finished. I need to address a few cases.

First, some quibbles: my implementation introduced an unnecessary level of nesting in paths_completed. I removed that.

Next, I wanted to sweeten up the length calculation in shortest_path with a little syntactic sugar:

Maybe more importantly, I have these three things to address:

1. Right now, even if the shortest path has already been found, the program will run until every path is exhausted. That’s unnecessary. What if S and E are neighbors in a giant board?
2. I want an exception raised if the board has no valid solutions.
3. I also want an exception raised if we hit our step limit before finding a viable solution.

I solved #1 and #2 in one fell swoop by changing track_paths to return immediately once there are completed paths to choose from. Because the algorithm runs step by step, the second there is even one completed path, that one won the race for “smallest number of steps.” We can cut off the program.

Once I had moved the return statement from the end of the function to inside the while block, I could confidently conclude that the flow of execution exhausting the while block meant something had gone wrong.

Well, almost confidently. I of course wrote a test to bolster my confidence.

You know me by now, honey ;).

The problem with this, of course, is that this Exception will also trigger when the program hits the step limit, if I have provided one. And that’s gonna make a test fail. My options are to remove that test, or to add an exception specific to the case I’m testing.

I chose the latter. You’re welcome to have your opinions about that. Here’s the test adjustment:

And then here’s the implementation adjustment:

…er, wait. Missing something in that implementation. Crap!

Addition shown here with the commit message included in the screenshot so that you know, while I am cocky, I am also humble.

Elephant in the room: yep, I am totally attaching arbitrary attributes to the exception on lines 101 and 102, and I am definitely checking on them in the test (see the test screenshot, lines 176 and 177). You can totally do that in Python. I don’t precisely recommend it. I left it because this is an exception that we are literally only raising to differentiate a failure we expect to only happen in tests, and also because, frankly, I had a very important ice cream purchase to make at that moment.

I did come back and change my null object pattern in the path tracking code to more clearly demarcate paths that were eliminated for being off-board. I felt guilty to just leave it all ambiguous like that. Here’s the change in the track_paths test:

And here’s the implementation change:

That about wraps it up. The entire implementation and all the tests live in the same file. You run the file, either from the editor or from the command line with $python shortest_path.py, and you’ll see the test output. You don’t need anything installed besides Python 3+. Not even pip or anything.

Feel free to play with my solution!

Here’s the repo link again, for your convenience. Some fun game suggestions, should you require them:

1. Modify this code to print, or sum, the number of paths it is creating at each step of track_paths. Does the number surprise you? Pass some progressively larger (valid) boards into shortest_path and observe how these numbers change.
2. Would you describe the approach I am taking here as breadth-first or depth-first? Explain your reasoning.
3. Modify this code to print, or sum, the number of steps it takes the program to solve a board. Does the number surprise you? Pass some progressively larger (valid) boards into shortest_path and observe how these numbers change.
4. Apropos of #2, do you think you can come up with an approach that would solve the board in fewer steps? How?
5. What is one implementation or api design choice I made above that confused you, or that you disagree with? See if you can change my program to one that you like better while preserving the basic functionality.

And to sweeten the pot, if anybody does #3&4 or #5 and sends me a solution that teaches me something, I’ll send you a gift certificate for something delicious. I’ll do this for the first ten people, in case this goes viral and I get bombarded (doubtful; I’m not that popular). I’ll list the winners right here so you know if you have a chance to make the cutoff:

1. Juan Miguel Vilar Torres. Check your inbox for a tasty treat voucher!
2. Could the next one be you??

Now, if you don’t mind, there’s a big, fluffy beach towel with my name on it. Thanks for taking this ride with me today. Until next time!

UPDATE: Our first community improvements are in!

Juan Miguel Vilar Torres took a look at my implementation (see comments on this post) and pointed out a few things.

First, because this solution runs step-by-step, the paths are all the same length at each step. I acknowledge this above when I change track_paths to return immediately once there are completed paths to choose from. But it also means we don’t have to check the lengths of the completed paths: the moment there are any, they’re all the same length, and that’s the length of the shortest path. To wit:

Next, because eliminate_paths runs at every step, all the path candidates passed into that function contain no duplicates anywhere before the last element (otherwise, they would have already been eliminated). So rather than convert each path list to a set, we can make sure the last space in each path doesn’t appear anywhere prior in the path. I like this change for its additional legibility in addition to its efficiency:

Finally, in addition to eliminating paths whose last space appears earlier in the path, we can also eliminate paths whose last space appears earlier in any path. I love Juan Miguel Vilar Torres’ explanation of why:

If a path p moves to a Space sp that has already been visited by other paths there is no way that p ends being the shortest path to the end (think that if from sp to the end it takes n steps, the path that first visited sp can also take those n steps and therefore be shorter overall). Therefore, a way to prune the alive paths is to keep a set of already visited spaces. That way, eliminate_invalid would need to check that the last element is neither out of bounds nor previously visited.

– Juan Miguel Vilar Torres in the comments on this post

To capture the idea precisely, I changed the test like this:

Then I initialize a set of already visited spaces, which I update each time I call eliminate_paths after making sure the most recent space on each oath isn’t in there:

Finally, I make track_changes responsible for managing the state on this:

Congratulations to Juan Miguel Vilar Torres on pointing out these things! Expect a tasty treat voucher incoming.

UPDATE: More community input!

Joe (see comments below) brought up two great things I’d like to address:

I haven’t written tests in Python before but was interested in your reason for not using ‘assert’. The output from asserts in test frameworks for other languages is really useful. I see that assertEqual in python’s unittest library outputs expected and actual values. But we don’t want to include that for a bit of vacation coding.

Correct! In Python, assert isn’t really for testing. It’s for validating total failure cases before proceeding with a critical operation. If an assert fails in Python, you get AssertionError and zero message whatsoever. Hence, the conditionals where I print a message.

As Joe points out, you can do something like this”

assert updated_paths == [
[Space(row=1, column=3, value=’S’), Space(row=0, column=3, value=0)],
[Space(row=1, column=3, value=’S’), Space(row=1, column=2, value=0)],
[Space(row=1, column=3, value=’S’), Space(row=2, column=3, value=0)],
[Space(row=1, column=3, value=’S’), Space(row=1, column=4, value=’off_board’)]
], 
f”Whoops, extend returned {updated_paths}.”
print("Success on updating paths!")

You could totally do this. I didn’t, but I’m sorta indifferent. I do think you have to stare at it for a second to figure out what’s happening because the failure message appears before the success message without much labeling. I don’t feel strongly, though.

Joe also brought up a good point about eliminating invalid paths earlier in the execution flow:

As a future optimisation, could paths be eliminated before they are added to the list of paths? For example, could extend_paths check if the value is 0 before adding the path to the list?

It absolutely could! This was my initial thought as well. The reason I elected not to do it like this was, essentially, easier separation of concerns. Now each path takes two steps: generate the next step in every path, eliminate paths that are now invalid. I picture it like a pasta machine: push pasta through, cut it off. Push pasta through, cut it off.

We could eliminate paths before generating the next step, but I found it more complicated under that schema to keep the validation and generation logic from getting jumbled together. The other advantage to the current approach is that one can put a breakpoint, or print point, at each step before elimination to see what gets eliminated and why. That’s a little harder to see in an aggregate view if we eliminate before adding, and since a) both steps had to be done anyway and b) the additional space taken up by this approach is, at most, one space per path per pass, I made the choice that the additional observability was worth it. That’s subjective. I’d be thrilled to see someone implement it the other way, especially with good separation of concerns!

If you liked this piece, you might also like:

Me walking you through my implementation of the Raft distributed consensus algorithm (Warning: this is 14 parts. Not for the faint of heart for sure.)

Me walking you through how I implemented error productions in the Lox compiler (it’s okay if you don’t know what an error production is. I explain that in the blog post.)

The feedback from the Tackling Technical Debt Workshop I gave at RubyConf (language-agnostic; you don’t have to be a Rubyist to get it.)