1
\$\begingroup\$

I have m x n grid. m >= 1 ; n >= 1

I have item in the top-left corner and need to reach bottom-right corner of the grid.

Item can only move either down or right.

I need to find possible unique paths to do it.

I made two solutions for the problem: recursion (slower than the below one) and the one below.

The problem is that I run out of memory when m and n are big e.g. m == 20 and n >= 15 (more than 4 Gb is used - all free memory I have).

How can I improve my solution or there should be absolutely other way to solve the problem?


def unique_paths(m, n):
    assert isinstance(m, int), "m should be integer"
    assert isinstance(n, int), "n shoudl be integer"
    assert m >= 1, "m should be >= 1"
    assert n >= 1, "n should be >= 1"
    if m == 1 and n == 1:  # border case
        return 1

    ch = [(m, n,)]  # for first start
    s = 0  # number of unique paths
    while True:
        new_ch = []
        while ch:
            i = ch.pop()  # I assumed that if decrease len of list it would decrease memory use
            if i[0] == 1 and i[1] == 1:  # we reached opposite corner
                s += 1

            # all other cases:

            elif i[0] != 1 and i[1] != 1:
                new_ch.append((i[0], i[1] - 1, ))
                new_ch.append((i[0] - 1, i[1]))

            elif i[0] == 1 and i[1] != 1:
                new_ch.append((i[0], i[1] - 1,))

            else:
                new_ch.append((i[0] - 1, i[1],))

            del i  # do not need i anymore

        if not new_ch:
            return s
        del ch
        ch = new_ch
        del new_ch

if __name__ == '__main__':
    print(unique_paths(7, 3))  # = 28 - test case

Edit:

lru_cache is really amazing:


from functools import lru_cache


@lru_cache(128)
def numberOfPaths(m, n):
    if m == 1 and n == 1:  # border case
        return 1

    if m != 1 and n != 1:
        return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1)

    if m != 1 and n == 1:
        return numberOfPaths(m - 1, n)

    if m == 1 and n != 1:
        return numberOfPaths(m, n - 1)


if __name__ == '__main__':
    print(numberOfPaths(100, 100))  # 22750883079422934966181954039568885395604168260154104734000

```
\$\endgroup\$
  • 2
    \$\begingroup\$ I didn't downvote, but this seems like it's less a matter of improving the code and more a matter of improving the underlying algorithm. Not sure how much a review of the code on its own will help you. :) \$\endgroup\$ – Samwise Apr 26 at 20:19
  • 3
    \$\begingroup\$ Close / down voter, this is not off-topic as it works with smaller bounds. Please read meta where we have explicitly allowed performance and memory improvements. We have a tag for this with ~150 questions, how's it off-topic 🤦 \$\endgroup\$ – Peilonrayz Apr 26 at 20:41
  • 3
    \$\begingroup\$ @Samwise Please keep the comments for discussing how the question can be improved and the answers for how the question's code can be improved. \$\endgroup\$ – Peilonrayz Apr 26 at 20:42
  • 5
    \$\begingroup\$ As they say, the right algorithm is the key. As long as you bruteforce, lru_cache is just a pair of crutches. OTOH, math does wonders. The answer to this problem is \$\binom{m+n-2}{m-1}\$. \$\endgroup\$ – vnp Apr 26 at 21:25
  • 2
    \$\begingroup\$ It's a binomial coefficient \$\endgroup\$ – vnp Apr 27 at 6:43
0
\$\begingroup\$

Solution: recursion with memoization works really well! Many thanks to Samwise and vnp.

With the help of python lru_cache decorator:

@lru_cache(128)
def number_of_paths(m, n):
    if m == 1 and n == 1:  # border case
        result = 1

    elif m != 1 and n != 1:
        result = number_of_paths(m - 1, n) + number_of_paths(m, n - 1)

    elif m != 1 and n == 1:
        result = number_of_paths(m - 1, n)

    elif m == 1 and n != 1:
        result = number_of_paths(m, n - 1)

    else:
        raise Exception("Something went wrong!")

    return result

With the help of dictionary to store results:

storage = {}
def number_of_paths_no_lru(m, n):
    if storage.get((m, n,)):
        return storage[(m, n)]

    if m == 1 and n == 1:  # border case
        result = 1

    elif m != 1 and n != 1:
        result = number_of_paths_no_lru(m - 1, n) + number_of_paths_no_lru(m, n - 1)

    elif m != 1 and n == 1:
        result = number_of_paths_no_lru(m - 1, n)

    elif m == 1 and n != 1:
        result = number_of_paths_no_lru(m, n - 1)

    else:
        raise Exception("Something went wrong!")

    storage[(m, n, )] = result
    return result

Tests:

if __name__ == '__main__':
    print(number_of_paths(100, 100))
    print(number_of_paths_no_lru(100, 100))
    # Answers:
    # 22750883079422934966181954039568885395604168260154104734000
    # 22750883079422934966181954039568885395604168260154104734000
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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