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?
in
is used on line 2 of each in JSin
is checking if the value of targetsum is a key of memo, I believe Pythonin
is checking if the value of targetsum is a value in memoin
in python works similar toof
in javascript, it was clarified in the tutorial.memo
beforebestsum()
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.