Why does this solution work in Javascript but not in Python? (Dynamic programming)

user_11556154 0
Viewed 738

I'm following this tutorial about dynamic programming and I'm struggling to implement memoization in the following problem:

*Write a function called canSum(targetSum, numbers) that returns True only if the numbers in the array can sum to the target sum. All the numbers in the array are positive integers and you can use them more than once for the solution.

Example:

canSum(7, [2, 4]) -> False because you can't form 7 by adding 2 and 4. *

My brute force solution was the following one:

def canSum(targetSum, numbers):
    if targetSum == 0:
        return True
    if targetSum < 0:
        return False

    for n in numbers:
        remainder = targetSum - n
        if canSum(remainder, numbers):
            return True

    return False


print(canSum(7, [2, 3])) # True
print(canSum(7, [5, 3, 4, 7])) # True
print(canSum(7, [2, 4])) # False
print(canSum(8, [2, 3, 5])) # True

Works well, but it'd be faster if we memoized the solutions of the remainders (this is explained at minute 1:28:03 in the video). I did the following with Python, which is exactly what the instructor is doing, but it only returns True and I can't figure out why...

def canSum(targetSum, numbers, memo={}):
    if targetSum in memo:
        return memo[targetSum]
    if targetSum == 0:
        return True
    if targetSum < 0:
        return False

    for n in numbers:
        remainder = targetSum - n
        if canSum(remainder, numbers, memo):
            memo[targetSum] = True
            return True

    memo[targetSum] = False
    return False


print(canSum(7, [2, 3]))
print(canSum(7, [5, 3, 4, 7]))
print(canSum(7, [2, 4]))
print(canSum(8, [2, 3, 5])) # All of them return True
dynamic-programming python-3.x python javascript
2 Answers

Thanks to the article shared by @Jared Smith I was able to figure it out.

The problem is caused by how python handles default arguments. From the article:

In Python, when passing a mutable value as a default argument in a function, the default argument is mutated anytime that value is mutated.

My memo dictionary was being mutated every call. So I simply changed memo=None and added a check to see if it was the first call of the function:

def canSum(targetSum, numbers, memo=None):
    if memo == None:
        memo = {}

    if targetSum in memo:
        return memo[targetSum]
    if targetSum == 0:
        return True
    if targetSum < 0:
        return False

    for n in numbers:
        remainder = targetSum - n
        if canSum(remainder, numbers, memo):
            memo[targetSum] = True
            return True

    memo[targetSum] = False
    return False


print(canSum(7, [2, 3])) # True
print(canSum(7, [5, 3, 4, 7])) # True
print(canSum(7, [2, 4])) # False
print(canSum(8, [2, 3, 5])) # True
print(canSum(3000, [7, 14])) # False -> Works fast with large inputs!
user_115561540

You saving mechanism have bug.

When you call function first time:

print(canSum(7, [2, 3]))

This call will return true and it will create key in dictionary with value true( 7 : true).
This is the reason why it doesnt work

Now we will check 3rd call:

print(canSum(7, [2, 4]))

First thing your function is doing is checking if number 7 is in dictionary:

if targetSum in memo:
    return memo[targetSum]

And because from 1st call you alredy have number 7 in dictionary , it will search it and return its value - and from 1st call , value for number 7 is True

This is dictionary before and after first call.

{}                                    # before first call
{1: False, 3: True, 5: True, 7: True} # after first call

After first call , this dictionary will return True for every time you call function with number 7.
And because Python share default argument (it is explained in comment by Jared Smith), every call will return True for number 7

How to fix this ? You must save both targetSum and nums into dictionary and test for both values.

There are two ways to do this:

1st way: Encapsulate targetSum and nums into tuple and use that tuple as key.
This is how will that dict will look

{
  (7, (2, 3)) : True,
  (7, (5, 3, 4, 7)) : True,
  (7, (2, 4)) : False
}

This is implementation of this:

keyTuple = (targetSum, tuple(numbers))
if keyTuple in memo:
    return memo[keyTuple]

if targetSum == 0:
    return True
if targetSum < 0:
    return False

for n in numbers:
    remainder = targetSum - n
    if canSum(remainder, numbers, memo):
        memo[keyTuple] = True
        return True

memo[keyTuple] = False
return False

You must also convert list into tuple , because python doesnt allow lists as keys for dictionaries.

Second way is use dictionary of dictionaries. Something like this.

{
 7: {
   (2,3): True,
   (5, 3, 4, 7): True
   (2,4): False
 }

}

This is implementation :

def canSum(targetSum, numbers, memo={}):
numbersTuple = tuple(numbers)

if targetSum in memo:
    targetDict = memo[targetSum]
    if numbersTuple in targetDict:
        return targetDict[numbersTuple]
else:
    memo[targetSum] = {}

if targetSum == 0:
    return True
if targetSum < 0:
    return False

for n in numbers:
    remainder = targetSum - n
    if canSum(remainder, numbers, memo):
        targetDict = memo[targetSum]
        targetDict[numbersTuple] = True
        return True

targetDict = memo[targetSum]
targetDict[numbersTuple] = False
return False

If you dont understand something , write comment for me :)

Admin1
Related