CODEWITHSUNDEEP
javascriptc++dynamic-programming
VerilogCoder
VerilogCoder

Reputation: 106

Converting JavaScript function to C++

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.

Upvotes: 1

Views: 2841

Answers (2)

Rohit
Rohit

Reputation: 21

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;
}

Upvotes: 2

Chris Uzdavinis
Chris Uzdavinis

Reputation: 6131

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:

  1. 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.

  2. the "detail" namespace is just a name, no magic meaning, but is often used to indicate implementation detail.

  3. 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.

  4. 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.

  5. 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

Upvotes: 1

Related Questions