# Insect combinatorics challenge

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
"""


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

1. Can we avoid re-assignment operator on count_paths?
2. Can we avoid nested function definitions?
3. 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.

Using nonlocal rather than global is certainly good, but better yet would be returning values.

def paths(m, n):
def find_number_of_paths(x, y):
if x == 0 and y == 0:
return 1

ret = 0

if x > 0:
ret += find_number_of_paths(x-1, y)

if y > 0:
ret += find_number_of_paths(x, y-1)

return ret

return find_number_of_paths(m-1, n-1)


That lets us elide the outer function entirely:

def paths(x, y):
if x == 1 and y == 1:
return 1

ret = 0

if x > 1:
ret += paths(x-1, y)

if y > 1:
ret += paths(x, y-1)

return ret


It's a bit strange to critique this since "no closed-form solution" basically means no good solution. There are ways of speeding this up, though, that avoid that. A trivial one is memoization:

_paths_cache = {(1, 1): 1}
def paths(x, y):
if (x, y) in _paths_cache:
return _paths_cache[x, y]

ret = 0

if x > 1:
ret += paths(x-1, y)

if y > 1:
ret += paths(x, y-1)

_paths_cache[x, y] = ret
return ret

• What is closed-form solution? – overexchange Jun 30 '15 at 12:34
• So, ret=0, executes only once? – overexchange Jun 30 '15 at 12:35
• ${(x-1) + (y-1)} \choose {y-1}$ – Veedrac Jun 30 '15 at 13:35
• ret = 0 executes nearly once per call to paths, which is approximately $xy$ times. – Veedrac Jun 30 '15 at 13:40
• Each call to the function has a different ret. Look at each function call in isolation: find_number_of_paths(4, 3) is equal to find_number_of_paths(3, 3) + find_number_of_paths(4, 2), so we add each to ret and return the answer. – Veedrac Jul 1 '15 at 0:28

## protected by Vogel612♦Jul 5 at 8:56

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).