num-paths exercise
1 min readJun 8, 2022
our challenge is to write a function to return the number of paths we can traverse from the upper-left corner of a grid to the lower-right corner. i’ve chosen ruby as my language.
MAZE = [
[0, 0, 0],
[0, 1, 0],
[0, 0, 0],
]
def num_paths(x, y, path_so_far)
# we made it!
return 1 if x == 2 && y == 2 # out of bounds.
return 0 if x < 0 || x > 2 || y < 0 || y > 2 # obstacle in our path.
return 0 if MAZE[y][x] == 1 this_point = [x, y]
# double-crossing our path.
return 0 if path_so_far.include?(this_point) # now compute the number of paths from *this* point.
new_path_so_far = path_so_far + [this_point]
return num_paths(x - 1, y, new_path_so_far) + # left
num_paths(x, y - 1, new_path_so_far) + # up
num_paths(x + 1, y, new_path_so_far) + # right
num_paths(x, y + 1, new_path_so_far) # down
end
puts num_paths(0, 0, []) # 2
