Below is the problem taken from Berkeley's Cs61A page here
Question 9: Insect Combinatorics*
Consider an insect in an M by N grid. The insect starts at the bottom left corner, (0, 0), and wants to end up at the top right corner, (M-1, N-1). The insect is only capable of moving right or up. Write a function paths that takes a grid length and width and returns the number of different paths the insect can take from the start to the goal. (There is a closed-form solution to this problem, but try to answer it procedurally using recursion.)
For example, the 2 by 2 grid has a total of two ways for the insect to move from the start to the goal. For the 3 by 3 grid, the insect has 6 diferent paths (only 3 are shown above).
def paths(m, n): """Return the number of paths from one corner of an M by N grid to the opposite corner. >>> paths(2, 2) 2 >>> paths(5, 7) 210 >>> paths(117, 1) 1 >>> paths(1, 157) 1 """ "*** YOUR CODE HERE ***"
This solution is with the knowledge of 'higher order function' and 'recursion'. I've yet to learn data structures and algorithms (if required).
Idea: Started from the destination and found the possibilities. As per the skill level, the solution took 3 hours of my time. Please provide feedback on this.
def paths(m, n):
"""Return the number of paths from one corner of an
M by N grid to the opposite corner.
>>> paths(2, 2)
2
>>> paths(5, 7)
210
>>> paths(117, 1)
1
>>> paths(1, 157)
1
"""
count_paths = 0
def find_number_of_paths(x, y):
if x == 0 and y == 0:
nonlocal count_paths
count_paths += 1
return
if x > 0:
find_number_of_paths(x-1, y)
if y > 0:
find_number_of_paths(x, y-1)
find_number_of_paths(m-1, n-1)
return count_paths
- Can we avoid re-assignment operator on
count_paths
? - Can we avoid nested function definitions?
- Is there a name for above solution approach in algorithm world? Any better approach?
Note: As per this assignment, no usage of data model is recommended.