Dynamic programming code works in javascript but not in python

Question

I am learning Dynamic Programming from freecodecamp, the instructor is using JavaScript and i know python so i am converting the logic in python.

Long story short, this problem's JavaScript implementation is working fine, but my python implementation is giving strange output.

I have matched the syntax many times and verified the logic, i can't point out where i am going wrong. Any help would be appreciated.

Problem Statement: Create a program to find the smallest sub-array of integers whose sum is equal to targetsum.

JavaScript Implementation:

const bestsum = (targetsum, numbers, memo={}) => {
    if (targetsum in memo) return memo[targetsum];
    if (targetsum === 0) return [];
    if (targetsum <0) return null;
    
    let shortestcomb = null;
    
    for (let num of numbers){
        const remainder = targetsum - num;
        const remaindercomb = bestsum(remainder, numbers, memo);
        if (remaindercomb !== null){
            const combination = [...remaindercomb, num];
            if (shortestcomb===null || combination.length < shortestcomb.length){
                shortestcomb = combination;
            }
        }
    }
    memo[targetsum] = shortestcomb;
    return shortestcomb;
}
console.log(bestsum(7, [2, 4, 3]));
console.log(bestsum(100, [1, 2, 5, 25]));

Output:

[ 3, 4 ]
[ 10, 10 ]

My Python Implementation:

def bestsum(targetsum, arr, memo=None):
    if memo is None:
        memo={}
    if targetsum in memo: return memo[targetsum]
    if targetsum==0: return []
    elif targetsum < 0: return None
    shortest = None 
    for i in arr:
        remainder = targetsum-i
        seq = bestsum(remainder, arr, memo)
        if seq!=None:
            seq.append(i)
            if (shortest==None or len(seq)<len(shortest)):
                shortest = seq
    memo[targetsum] = shortest
    return shortest

print(bestsum(7, [2, 4, 3]))
print(bestsum(20, [5, 10]))

Output:

[4, 3]
[10, 5, 5, 10]

The obvious answer for the second case is [10, 10] as that would sum to 20 with the least number of elements, also for the first case the JavaScript output is [3, 4] whereas python output is [4, 3], isn't it strange?

EDIT: Someone marked this question as duplicate, i followed that guide and used a placeholder in place of the mutable default argument, but the output is still the same, what is wrong now?

not sure, but might be down to the different way in is used on line 2 of each in JS in is checking if the value of targetsum is a key of memo, I believe Python in is checking if the value of targetsum is a value in memo — tbjgolden
– tbjgolden, Commented Mar 28, 2022 at 23:23
in in python works similar to of in javascript, it was clarified in the tutorial. — anantdark
– anantdark, Commented Mar 28, 2022 at 23:32
This is a great opportunity to practice debugging. You can try an interactive debugger, such as PDB or whatever is provided by your IDE (if using one), or add scaffolding (programming statements for debugging, such as printing memo before bestsum() returns), or even debugging by hand, evaluating the statements yourself and tracking what's stored in the variables. I bet by the time the question is reopened, you'll be able to post an answer to your own question. — outis
– outis, Commented Mar 29, 2022 at 0:23
@outis i tried using the debugger in vscode, but i can't follow the call stack as the whole tree is rather large. — anantdark
– anantdark, Commented Mar 29, 2022 at 6:34

outis · Accepted Answer · 2022-03-29 08:34:29Z

1

While an interactive debugger is the most general (and, often, most powerful) way of examining bugs, here a simple bit of scaffolding can reveal much. By adding a print(f"target = {targetsum}; memo = {memo}") statement just before the end of bestsum, we get:

target = 5; memo = {5: [5]}
target = 10; memo = {5: [5, 5], 10: [10]}
target = 15; memo = {5: [5, 5, 10], 10: [10, 5], 15: [10, 5]}
target = 20; memo = {5: [5, 5, 10], 10: [10, 5, 5, 10], 15: [10, 5, 5, 10], 20: [10, 5, 5, 10]}

Note how the entries for each target sum keep changing. This shouldn't happen, based on the algorithm. Looking at bestsum, the entries of memo come from seq. Looking for lines that alter seq, we find seq.append(i). This mutates the list, which is why the entries of memo keep changing, and why the final result is incorrect. The JavaScript version of bestsum creates a new list for each iteration of the loop body, which is why it doesn't suffer this bug.

Note you could translate the JavaScript directly and use the spread operator, or you could list concatenation: seq = seq + [i].

One approach that would have prevented this bug from arising would be to use an immutable type instead of a list. In Python, that would be tuple. The one wrinkle is than if using tuple concatenation, a single-element tuple must have a comma trailing the element: seq = seq + (i,).

answered Mar 29, 2022 at 8:34

outis

77.7k23 gold badges155 silver badges228 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

anantdark Over a year ago

Swear to god, just figured it out myself. Was about to write an answer myself. Thanks a lot.

anantdark Over a year ago

the memo placeholder at the top isn't making any change. I read many tutorials but still could'nt figure out when and where to use it, any insights?

anantdark · Accepted Answer · 2022-03-29 10:59:44Z

Expanding on @outis's answer, the entries of memo are changing with each iteration, this shouldn't happen. This is happening because when you assign a list to a new variable, instead of creating a new list, python refrences the old list's address to the new one.

This creates a problem when the list is changed, as the changes start to show in all its copies.

Here seq is the master list

shortest is copied from seq

memo[targetsum] is copied from shortest

Ideally after all the children of a recursive tree node are traversed we select the shortest path and assign it to memo[targetsum] but the value inside memo[target] changes with the changes in seq that introduces the unexpected values in memo.

It can be fixed by using an immutable data type as @outis suggested. But we can go a step further and just make a small change to this code itself.

import copy
def bestsum(targetsum, arr, memo=None):
    if memo is None:
        memo = {}
    if targetsum in memo: return copy.deepcopy(memo[targetsum])
    if targetsum==0: return []
    elif targetsum < 0: return None
    shortest = None 
    for i in arr:
        remainder = targetsum-i
        seq = bestsum(remainder, arr, memo)
        if seq!=None:
            seq.append(i)
            if (shortest==None or len(seq)<len(shortest)):
                shortest = seq
    memo[targetsum] = copy.deepcopy(shortest)
    return shortest

print(bestsum(7, [2, 4, 3]))
print(bestsum(20, [5, 10]))

Output:

[3, 4]
[10, 10]

Here we are using deepcopy from the copy module in python. deepcopy essentially creates a new list and populates it recursively with the elements of the original list, therefore the new lists are totally different from each other. Read more about it here

PS- deepcopy is probably overkill here as it is generally used for nested lists, using shallowcopy will also work fine here.

Shallowcopy syntax-

newlist = oldlist.copy()

Collectives™ on Stack Overflow

Dynamic programming code works in javascript but not in python

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related