Welcome to the Treehouse Community

Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community!

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.

Start your free trial

General Discussion

Programming puzzle for advanced programmers: Pathfinder

Hello fellow coders!

This isn't exactly a question, it's more of a problem everybody can attempt to solve and play around with. It is more on the difficult side, though, so clever algorithms may need to be needed for solving this problem.

You may do this in any language; I've done it in Python. If you are looking for solutions, look in the answers below. I've posted my solution down there, and if you wish, you may post it as well.

The challenge:

Given a square NxN matrix, compute a path from the top-left corner to the bottom-right corner. The grid consists of .'s and #'s. The path must be within the bounds of the matrix, and you also may not walk through #'s, as they are obstacles you must avoid.

Once you've solved this, try to solve it assuming N can be up to 50. You will need to have a more efficient algorithm to be able to do this. (An empty 50x50 grid has a LOT of possibilities.)

My code, which in fact can handle a 50x50 grid, is posted below. (It's in Python.)

Note that your code doesn't have to look clean, it just has to work.

1 Answer

from copy import deepcopy

def find_path(grid, r=0, c=0, path=[(0, 0)]):
    if r < 0 or r >= len(grid):
        return []

    if c < 0 or c >= len(grid[0]):
        return []

    if grid[r][c] == '#':
        return []

    if r == len(grid) - 1 and c == len(grid[0]) - 1:
        return path

    copy = deepcopy(grid)
    copy[r][c] = '#'

    right = find_path(copy, r=r, c=c+1, path=path+[(r, c + 1)])
    if right:
        return right

    down = find_path(copy, r=r+1, c=c, path=path+[(r + 1, c)])
    if down:
        return down

    left = find_path(copy, r=r, c=c-1, path=path+[(r, c - 1)])
    if left:
        return left

    up = find_path(copy, r=r-1, c=c, path=path+[(r - 1, c)])
    if up:
        return up

    return []