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! While you're at it, check out some resources Treehouse students have shared here.

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

Posted by Alexander Davison
Alexander Davison
65,469 Points

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

Alexander Davison
Alexander Davison
65,469 Points
Alexander Davison
Alexander Davison
65,469 Points 
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 []