Dynamic programming code works in javascript but not in python

anantdark

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?

enter image description here

outis

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,).

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

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

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

what is wrong in this code for dynamic programming?

How this code works in python?

Code works in Java but not Python?

Efficient Dynamic programming using Python

Python dynamic programming performance difference

Code works with a static PHP value but not a dynamic variable

How does this javascript code works?

Javascript code works on desktop but not on mobile

Javascript functional programming and dynamic values in an Array

Javascript closure in fibonacci series using dynamic programming

Python regex works online but not in code

How to change this backtracking code into a dynamic programming code by using memoization?

Python find the largest square in the matrix dynamic programming

Python: Numba njit mode for faster dynamic programming

Dynamic Javascript code for multiple elements

Python code works, same Java code does not

Sudoku solver works in python but not javascript

Why it works in Javascript but in Python dont?

Dynamic Programming?

Why does the code not work with malloc but works with non dynamic allocation?

How to code a strcat function that works with two dynamic arrays

jQuery slider works but it's hard-code, how to make it dynamic

In javascript how does the below code works

the javascript code works but I get an error

Javascript code works in JSFiddle but does not work in browser

javascript code not working locally but works in jsfiddle

Javascript regex works on online validator but fails in code