num-paths exercise

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Clay Shentrup

Clay Shentrup

advocate of score voting and approval voting. software engineer. father. husband. american.