AvoidRoads - TopCoder Challenge

Question

I'm learning Dynamic Programming, following the topcoder guide. I just solved the AvoidRoads challenge. It passes all the test cases, but I don't have much experience, so I don't know if it's good.

Challenge Description

Linked description contains images and better illustrates the problem.

You are standing at the corner with coordinates 0,0. Your destination is at corner width,height. You will return the number of distinct paths that lead to your destination. Each path must use exactly width+height blocks. In addition, the city has declared certain street blocks untraversable. These blocks may not be a part of any path. You will be given a String[] bad describing which blocks are bad. If (quotes for clarity) "a b c d" is an element of bad, it means the block from corner a,b to corner c,d is untraversable. For example, let's say

width = 6
length = 6
bad = {"0 0 0 1","6 6 5 6"}
Returns: 252

My Solution:

def allowed(i, j, x, y, banned_set):
 s = "{} {} {} {}"
 options = [
 s.format(i, j, x, y),
 s.format(x, y, i, j)
 ]
 for opt in options:
 if opt in banned_set:
 return False
 return True
def calc(lst, i, j, banned_set):
 result = 0
 if i-1 >= 0 and allowed(i, j, i-1, j, banned_set):
 result += lst[i-1][j]
 if j-1 >= 0 and allowed(i, j, i, j-1, banned_set):
 result += lst[i][j-1]
 return result
def avoid_roads(n, m, banned_set):
 n += 1
 m += 1
 matrix = [[0 for _ in xrange(m)] for _ in xrange(n)]
 matrix[0][0] = 1
 for i in xrange(n):
 for j in xrange(m):
 if i == j == 0:
 continue
 matrix[i][j] = calc(matrix, i, j, banned_set)
 return matrix[-1][-1]

Answer 1

Your logic seems solid, but there's a couple of things I would do differently.

One obvious improvement is that you don't need to hold the full dynamic programming array in memory: it is enough to keep the previous row and the one you are working on. It also leads to a pretty neat handling of edge cases, as you'll see soon enough.

I am also a little weary about the approach of your allowed function: relying on a string representation just doesn't feel right. I also frown at your adding both the forward and the reverse paths to your banned set: the only reason you can use DP in the first place is because you can only move forward in both directions, so you might as well take advantage of that knowledge, and store only the direction you will eventually find.

A possible implementation of all that could be:

def banned_roads(banned_strings):
 banned_paths = {}
 for banned_string in banned_strings:
 banned_coords = [int(item) for item in banned_string.split()]
 banned_coords = [tuple(banned_coords[:2]), tuple(banned_coords[2:])]
 banned_coords.sort() # we always move towards larger coords
 src, dst = banned_coords
 banned_srcs = banned_paths.setdefault(dst, [])
 banned_srcs.append(src)
 return banned_paths
def avoid_roads(rows, cols, banned_paths):
 rows += 1
 cols += 1
 prev_row = [1] + [0] * (cols - 1)
 for row in range(rows):
 this_row = []
 before = 0
 for col, above in enumerate(prev_row):
 banned_srcs = banned_paths.get((row, col), [])
 if (row, col - 1) in banned_srcs:
 before = 0
 if (row - 1, col) not in banned_srcs:
 before += above
 this_row.append(before)
 prev_row = this_row
 return prev_row[-1]
if __name__ == '__main__':
 assert 252 == avoid_roads(6, 6, banned_roads(['0 0 0 1', '6 6 5 6']))
 assert 2 == avoid_roads(1, 1, {}})
 assert 112186277816662845432 == avoid_roads(35, 31, {}})
 assert 0 == avoid_roads(6, 6, banned_roads(['0 0 1 0', '1 2 2 2',
 '1 1 2 1']))

Note how the initialization of prev_row and before spares us from having to check if we are at the first row or column, which I think makes the logic cleaner. I am also a big fan of enumerate over iterating over a range and extracting the entry via indexing, but YMMV.

• Josh Horowitz: Not holding the entire array is great advice. It seems obvious in retrospect. My original solution didn't rely on strings and it figured out the order of the banned squares (and from there which block was untravserable) by doing (i+j) - (x + y) < 0. which would tell me if it was i, j or x, y which was relevant. But I felt like it seriously complicated the function. Assuming that the given inputs are valid, is there any reason other than strings are ugly that the optimization is worth it?
• Jaime: The major concern is that, if you had e.g. an extra space in your input, which is an easy error to make, all of a sudden nothing works. It seems to me much better to have a more meaningful comparison, by actually extracting the meaning of the values you are comparing.