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 trialAlexander Davison
65,469 PointsProgramming 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
65,469 Pointsfrom 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 []