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\$

1 Answer 1

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

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.