DEV Community

loading...

Ouch! Oh no, I recursion'd myself!

hydroweaver profile image Karan ・2 min read

image

Hey Devers!

What's happening? Here's another short post about me cutting myself with concepts I don't know.

This one is about Best Travel from codewars, it's very simple if you code in Python, but in JS(if you're like me) you'll have to bang your head on the table and bang your head on the table and bang your head on the table and...maximum stack size exceeded!😭

Problem:

  1. Get distinct fixed length(say f) combinations from the input array without replacement
  2. Calculate sum of each combination derived from step 1.
  3. Compare each sum with a given input parameter, say K
  4. Return sum closest to K otherwise Null etc.

If you're using python, getting the combination is as easy as follows:

import itertools

arr = [1,2,3,4,5,6,7,8]

combinations = itertools.combinations(arr, 5) # f is 5

#print each combination
for i in combinations:
    print(i)

Check out the post from geeksforgeeks By the way, I just saw this now! lol wut!

So...I didn't know this when I tried this problem and I tried it with JS, looky here, and as you know based on my last post, it's replusive, grotesque!😬

ts = [ 91, 74, 73, 85, 73, 81, 87 ];

function chooseBestSum(t, k, ls){
    var km = t;
    var towns = k;
    var arr = ls;
    var tuple = [];
    var km_sum = [];
    var count = 0;
    var result = 0;
    function karan(arr){
    if(arr.length==0){
        return null;
    }
    else{
        if(tuple.length===towns-1){
            for(var i =0;i<arr.length;i++){
                tuple[towns-1]=arr[i];
                console.log('we are here', tuple);
                km_sum.push(tuple.reduce((i,c)=>i+c));
            }
            //tuple.splice(1,2)
            tuple.splice(1,tuple.length);
        }
        tuple.push(arr[0]);
        karan(arr.slice(count+1, arr.length));
    }
    //return Math.max(...km_sum.filter(i=>i<=km?i:null))
    }

    for(var i = 0;i<=arr.length-towns;i++){
        tuple = [];
        karan(arr.slice(i,arr.length));
    };
    console.log(km_sum);
    result = Math.max(...km_sum.filter(i=>i<=km)); 
    if(result===-1 || result===-Infinity){
        return null;
    }
    else{
        return result;
    }
    //result = Math.max(...km_sum.filter(i=>(km_sum.length>0&&i<=km)?i:null));
}

chooseBestSum(331, 4, ts);

What I'm trying to do:

  1. Thinking too much that only RECURSION will solve it! WRONG! Although it is the best and shortest solution.
  2. Not able to really visualize the problem.
  3. Never read or discovered what this is, until I saw the stuff online
  4. Absolutely confused about where function returns would work etc.

And so I wasn't able to solve it myself! The code you see above works 22/30 times because it does not return all the correct combinations BECAUSE it's a hit and miss BECAUSE it was primarily fashioned for f = 3! 😳😳😳😳

And I leave you all with this : RTFM, train again and a quote from Scott Eastwood:

Keep your head down, work hard, and don't ever believe your own hype, because... you just keep working.

Good Day!

Discussion (0)

pic
Editor guide