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.