2
\$\begingroup\$

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.) enter image description here

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

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ What is closed-form solution? \$\endgroup\$ – overexchange Jun 30 '15 at 12:34
  • \$\begingroup\$ So, ret=0, executes only once? \$\endgroup\$ – overexchange Jun 30 '15 at 12:35
  • \$\begingroup\$ \${(x-1) + (y-1)} \choose {y-1}\$ \$\endgroup\$ – Veedrac Jun 30 '15 at 13:35
  • \$\begingroup\$ ret = 0 executes nearly once per call to paths, which is approximately \$xy\$ times. \$\endgroup\$ – Veedrac Jun 30 '15 at 13:40
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – 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).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.