Converting JavaScript function to C++

Question

I was working on a Dynamic Programming Problem and was able to code up a Javascript solution:

function howSum(targetSum,numbers,memo = {}){
    //if the targetSum key already in hashmap,return its value
    if(targetSum in memo) return memo[targetSum]; 

    if(targetSum == 0) return [];
    if(targetSum < 0) return null;

    for(let num of numbers){
        let aWay = howSum(targetSum-num,numbers,memo);
        if(aWay !== null){
            memo[targetSum] = [...aWay,num];
            return memo[targetSum];
        }
    }

    //no way to generate the targetSum using any elements of input array
    memo[targetSum] = null;
    return null;
}

Now I was thinking over how I could translate this into a CPP code. I would have to use a reference to an unordered map for the memo object.

But how should I go about returning the empty array and null values as in the base condition?Should I return an array pointer and realloc it when inserting an element?Wouldnt that be a C way of programming it? Also how should I go about passing the default parameter to the memo unordered map in C++?Currently I have overloaded the function which creates the memo unorderd map and passes its reference.

Any guidance will be appreciated as I can solve future questions.

C++17 and later have std::optional and std::variant templates for these kinds of situations, in general. However C++ is not Javascript. Looking at this overall logic: in C++ the situation where this this returns null would be likely handled by throwing an exception to indicate a fatal error. You cannot really translate Javascript into C++, or any language into any other language, for that matter, by attempting to do it one line at a time. This always ends in tears. The right way is to analyze what the existing code does, and reimplement its overall logic in the new language. — Sam Varshavchik
– Sam Varshavchik, Commented Jun 5, 2021 at 12:01
Okay thanks for the insight.So Should I go about changing the logic of the code?Like returning the empty array and null? — VerilogCoder
– VerilogCoder, Commented Jun 5, 2021 at 12:03
I believe I was pretty clear in indicating that this is not the right approach. The correct approach is to analyze what the shown code does, logically, and then implementing something that's logically equivalent to it, in functionality, in C++. In C++ NULL constants are only valid for pointer types, and C++ functions cannot return arrays. C++ does not work this way. Therefore you will need to find some other replacement for these concepts, for your C++ code, and that's a decision that you will need to make yourself, since only you knows how the replacement code will be used. — Sam Varshavchik
– Sam Varshavchik, Commented Jun 5, 2021 at 12:08
You can return a bool to indicate success eg godbolt.org/z/6s6sb9e5r — QuentinUK
– QuentinUK, Commented Jun 5, 2021 at 18:37

Rohit · Accepted Answer · 2021-10-04 18:48:58Z

I was stuck in this problem too. This is how I made it work.

// howSum function
vector<int> howSum(int target, vector<int> numbers, unordered_map<int, vector<int>> &dp ){

    // base case 1 - for dp
    if(dp.find(target)!=dp.end()) return dp[target];

    // making a vector to return in the following base cases
    vector<int> res;

    // base case 2
    if(target == 0) {
        return res;
    }

    // base case 3
    if(target<0) {
        res.push_back(-1); // using -1 instead of NULL
        return res;
    }

    // the actual logic for the question
    for(int i=0;i<numbers.size();i++){
        int remainder = target - numbers[i];
        vector<int> result = howSum(remainder,numbers,dp); // recursion

        // if result vector doesn't contain -1, push target to result vector
        if(find(result.begin(),result.end(),-1)==result.end()){
            result.push_back(numbers[i]);
            dp.emplace(target,result);
            return result;
        }
    }
    res.push_back(-1);
    dp.emplace(target,res);
    return res;
}

// main function
int main(){

    vector<int>numbers = {20,50};
    unordered_map<int, vector<int>> dp;
    vector<int> res = howSum(300,numbers,dp);

    for(int i=0;i<res.size();i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;
}

Chris Uzdavinis · Accepted Answer · 2021-06-05 16:15:05Z

Here is my take at it:

#include <optional>
#include <vector>
#include <unordered_map>

using Nums = std::vector<int>;
using OptNums = std::optional<Nums>;

namespace detail {

using Memo = std::unordered_map<int, OptNum>>;

OptNums const & howSum(int targetSum, Nums const & numbers, Memo & memo) {
    if (auto iter = memo.find(targetSum); iter != memo.end()) {
        return iter->second; // elements are std::pair<int, OptNums>
    }
    auto & cached = memo[targetSum]; // create an empty optional in the map

    if (targetSum == 0) {
        cached.emplace(); // create an empty Nums in the optional
    }
    else if (targetSum > 0) {
        for (int num : numbers) {
            if (auto const & aWay = howSum(targetSum-num, numbers, memo)) {
                cached = aWay;           // copy vector into optional
                cached->push_back(num); 
            }
        }
    }
    return cached;
}
} // detail

std::optional<Nums> howSum(int targetSum, Nums const & numbers) {
    detail::Memo memo;
    return detail::howSum(targetSum, numbers, memo);
}

Some comments:

using two functions, one that creates the memo and passes it into the real implementation function is a good pattern. It makes the user-facing interface clean.
the "detail" namespace is just a name, no magic meaning, but is often used to indicate implementation detail.
In the implementation, I return references to an optional. This is an optimization to avoid copying the return vectors in every call where the algorithm unwinds from the recursion. This does require some care, however, because you must be careful to return references to objects that will outlive the local scope (so no returning std::nullopt, or the reference binds to a temporary optional, for example.) That is also why I always create the element in the memo object--even in the negative case--so I can return a reference to it safely. Note, operator[] applied to an unordered_map will create the element if it does not exist, while find will not.
Since the reference returned by the detail function has a lifetime only as long as the memo declared in the caller, the caller itself must return a copy of the optional it gets back, to ensure that the data is not destroyed during the cleanup of the function call. Note, it does not return a reference.
Also, the "if" inside the for loop has a little bit going on. It declares a local reference, initializes it to the result of the recursive call. That whole expression is a reference to optional, which has an implicit conversion to bool that is true if the optional holds a value. This is a useful idiom worth pointing out, though to be more explicit this is equivalent:

    if (auto const & aWay = howSum(targetSum-num, numbers, memo); aWay.has_value())

Here's a fleshed out example, with a few test cases to show it work. https://godbolt.org/z/cWrdhvM1n

Collectives™ on Stack Overflow

Converting JavaScript function to C++

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related