1
\$\begingroup\$

Below is the problem taken from page6 here.

The TAs want to print handouts for their students. However, for some unfathomable reason, both the printers are broken; the first printer only prints multiples of n1, and the second printer only prints multiples of n2. Help the TAs figure out whether or not it is possible to print an exact number of handouts! First try to solve without a helper function. Also try to solve using a helper function and adding up to the sum.

def has_sum(sum, n1, n2):
"""
>>> has_sum(1, 3, 5)
False
>>> has_sum(5, 3, 5) # 1(5) + 0(3) = 5
True
>>> has_sum(11, 3, 5) # 2(3) + 1(5) = 11
True
"""

Solution

I think there is no mathematical solution except bruteforce recursion.

def f(sum, n1, n2):
    """
    >>> f(1, 3, 5)
    False
    >>> f(5, 3, 5) # 1(5) + 0(3) = 5
    True
    >>> f(11, 3, 5) # 2(3) + 1(5) = 11
    True
    >>> f(189, 4, 9)
    True
    """
    memoiz = []
    value = []   
    def has_sum(sum, n1, n2, x=0, y=0):
        if x == 0 and y == 0:
            value.append(n1)
            value.append(n2)   #execute once to reuse tup
        if (n1 + n2)  == sum:
            return True
        if (memoiz) and ((n1 + n2)  > sum): # inefficient base case, need to improve using math
            return False
        result1 = False
        result2 = False
        if (x+1, y) not in memoiz:
            memoiz.append((x+1, y)) #memoiz
            result1 = has_sum(sum, (x+1)*value[0], y*value[1], x+1, y)
        if (x, y+1) not in memoiz:
            memoiz.append((x, y+1)) #memoiz
            result2 = has_sum(sum, x*value[0], (y+1)*value[1], x, y+1)
        return result1 or result2
    return has_sum(sum, n1, n2)

Can we improve the base case that returns False?

\$\endgroup\$
  • 1
    \$\begingroup\$ Why are you memoizing using a list?! in is O(n) and I've already shown you how to do it with a decorator. \$\endgroup\$ – jonrsharpe Jul 13 '15 at 9:30
  • \$\begingroup\$ See Linear Diophantine equations, two variables \$\endgroup\$ – 200_success Jul 13 '15 at 9:33
  • \$\begingroup\$ Teacher did not teach decorator concept. I will go thru you question. I need to go thru some homework on decorators before using it. \$\endgroup\$ – overexchange Jul 13 '15 at 9:34
  • \$\begingroup\$ @200_success yes, I got the same suggestion here \$\endgroup\$ – overexchange Jul 13 '15 at 9:38
  • 2
    \$\begingroup\$ @jonrsharpe's has already mentioned in a previous answer to one of your questions that the most elegant way to memoize functions is to use a decorator. We don't mind reviewing your code, but it would be more rewarding if we can see that you are learning from our answers. (You may have noticed that your recent questions have not scored as well as your first few questions.) \$\endgroup\$ – 200_success Jul 13 '15 at 9:38
3
\$\begingroup\$

First try to solve without a helper function. Also try to solve using a helper function and adding up to the sum.

You haven't included an implementation without a helper function. You implemented memoization, which was not part of the description. In any case, memoization won't be possible without a helper function or annotations.

Code review

There are several problems with your implementation:

  • memoiz shouldn't be a list, but a set
  • The value variable is confusing: it merely stores the original values of n1 and n2, you could simply save those values before calling the helper function
  • sum is a poor name for a variable, because it shadows the built-in named "sum"
  • There should be spaces around operators to improve readability, for example instead of (x+1)*value[0] it should be (x + 1) * value[0]
  • Instead of multiplying value[0] and value[1], it would be better to accumulate a sum
  • If result1 is True, there's no need to evaluate result2

With the above tips, the solution can be simplified a bit and become more efficient:

memoiz = set()
def has_sum(sum, n1, n2, x=0, y=0):
    if n1 + n2 == sum:
        return True
    if n1 + n2 > sum:
        return False
    if (x+1, y) not in memoiz:
        memoiz.add((x+1, y))
        result1 = has_sum(sum, n1 + orig_n1, n2, x+1, y)
        if result1:
            return True
    if (x, y+1) not in memoiz:
        memoiz.add((x, y+1))
        return has_sum(sum, n1, n2 + orig_n2, x, y+1)
    return False
orig_n1, orig_n2 = n1, n2
return has_sum(sum, 0, 0)

An alternative solution

Consider this alternative algorithm:

  • If target is 0, then we can reach it by 0 times n1 and n2
  • If target is below 0, then we cannot reach it
  • If target can be reached by a sum of multiples of n1 and n2, then target - n1 or target - n2 must be reachable too

Implementation using memoization:

memoize = { 0: True }
def helper(target):
    if target not in memoize:
        if target < 0:
            memoize[target] = False
        else:
            memoize[target] = helper(target - n1) or helper(target - n2)
    return memoize[target]
return helper(target)

Iterative solution

At first I overlooked your requirement of a recursive solution. For the record, this was my original suggestion using iterative logic.


Unless I'm missing something, you can solve this using a much simpler algorithm:

  • If a solution exists, then sum == n1 * A + n2 * B where A and B are integers
  • Loop from A = 0 to sum, by steps of n1
  • If sum - A is divisible by n2, then a solution exists
  • If the end of the loop is reached, then a solution doesn't exist

That is:

for A in range(0, sum + 1, n1):
    if (sum - A) % n2 == 0:
        return True
return False
\$\endgroup\$
  • 1
    \$\begingroup\$ This question is part of recursion lab \$\endgroup\$ – overexchange Jul 13 '15 at 10:20
  • \$\begingroup\$ My bad, I overlooked your title. I rewrote my answer. \$\endgroup\$ – janos Jul 13 '15 at 12:42
  • \$\begingroup\$ you said dict but you are using set(). what is the problem with list? \$\endgroup\$ – overexchange Jul 13 '15 at 12:59
  • \$\begingroup\$ Changed the text to set to match the revised implementation. The problem with a list is that x in somelist is an \$O(n)\$ operation, while x in someset is an \$O(1)\$ operation \$\endgroup\$ – janos Jul 13 '15 at 13:18
  • \$\begingroup\$ OK. how set is efficient from list in finding an element? What is the underlying implementation of set that it is efficient than list? \$\endgroup\$ – overexchange Jul 13 '15 at 13:20

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.