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

Question

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

I was just about to comment on your new python question that your code doesn't actually work properly... — Nick
– Nick, Commented Dec 31, 2020 at 0:12

martin · Accepted Answer · 2020-12-23 18:29:38Z

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!

user14781663 · Accepted Answer · 2020-12-23 18:31:38Z

2

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 :)

answered Dec 23, 2020 at 18:31

user14781663

3 Comments

martin Over a year ago

I think that a more straight-forward solution is to change memo to None and add a simple check at the beginning, as described in my solution.

user14781663 Over a year ago

@MartínSchere i tried you solution and i found problem. Your solution return alway True when i use dict to cache results . Try it yourself - create cahce variable that contain dictionary and pass it in every call as memo argument. You wanted function that can cache results , but your solution cant do that for same reason - it caches only targetSum and not list of numbers

user14781663 Over a year ago

@MartínSchere really , check it if it can cache values

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related