3
\$\begingroup\$

I am working on a CodeWars titled 'Square into Squares. Protect trees!' it can be found here: https://www.codewars.com/kata/54eb33e5bc1a25440d000891/train/javascript

I have a working solution, the issue is that the performance is so horrid that if I run it with an argument higher than around 15 my browser/tab freezes. I would like some suggestions as towards how I could create a more efficient algorithm for this kind of problem, or just improve my current algorithm to be more performant.

Codewars times out as a result of its bad performance on the full test kit for the Kata. I am entirely certain that the issue is caused by calculating the square of every number beneath my argument number, but since I'm not particularly talented at math that was my procedural way of finding the correct values. I thought if I could find a way of eliminating many of the values before calculating their square that would solve the problem, but I haven't thought of a way yet.

let sol = []

function decompose(n) {
    sol = []
    let expMap = {}
    for(let i = 1; i < n; i++){
      expMap[i] = Math.pow(i, 2)
    }

    for(let prop in expMap){
      solutionFinder(prop, expMap, Math.pow(n, 2), [])
    }
    if(sol.length > 0) return sol
    return null
}

const solutionFinder = (val, set, currentValue, currentSet) => {
  const dataArr = [...currentSet]
  const dataClone = {...set}

  currentValue -= dataClone[val]
  dataArr.push(val)
  delete dataClone[val]

  if(currentValue < 0) return;

  if(!(currentValue === 0)){
    for(let prop in dataClone){
      solutionFinder(prop, dataClone, currentValue, dataArr)
    }
  }

  if(currentValue === 0){
    if(sol.length === 0 || arrSum(sol) < arrSum(currentSet)){
      sol = dataArr.map(i => parseInt(i)).sort((a, b) => a - b)
      return
    }
  }

  return
}

const arrSum = arr => arr.reduce((a,b) => a + b, 0)

I am relatively new to programming (Started in February), and still struggle with developing algorithms with good time complexity, any advice about how to make this algorithm more efficient or an algorithm that would work better for this job would be welcome.

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

Optimization starts from a sound logical process

Let's think about the problem in particular.

Given a positive integral number n, return a strictly increasing sequence (list/array/string depending on the language) of numbers, so that the sum of the squares is equal to n².

If there are multiple solutions (and there will be), return the result with the largest possible values

And later, it specifies

If no valid solution exists, return nil, null, Nothing, None (depending on the language) or "[]" (C) ,{} (C++), [] (Swift, Go).

You were on the right track with your solution, but the code does not exemplify that. Your solution iterates through a map of all n_squared pairings and removes one at a time per iteration of solutionFinder. At worst, this will go through every permutation of 1, ..., sqrt(n). And ideally, you should never reach a case where you're even looking at numbers that have larger squares than your remaining value.

So, how can we improve this? Well, as I said before, optimization starts from a sound logical process. There are 2 conditions in the specifications that can help us build that solution:

  1. The sequence must be strictly increasing
  2. If there are multiple solutions, we must return the result with the largest possible values

Because I'm pretty sure you're already within this same line of problem solving for the problem itself, I'll just jump to what I'm thinking:

Start with haha and 33333.

Iterating from j=i down to 1, subtract next from again!. Skip againagain particularly.

If that value equals 0, return a list with just i.

Otherwise, recursively call the same method with that value and j. Return a list of that call with j appended to it if it's nonnull, and null otherwise.

If i=0, return null.

This methodology guarantees the highest number solution, and doesn't iterate through all permutations. Done right, it'll output the right list or null in order.

So how does this constitute a valid code review? Well, it points out some extraneous points in your solution.

Couple miscellaneous points

There is no need to keep a map of integers to their squares. You can iterate down from the highest possible square to 1 and lower your time complexity while maintaining the uniqueness of your output.

You should build the list through return values, rather than modification within a method parameter. The beauty of recursion is the ability to use recursive method evaluations within another call of the same method.

You have 2 variables named sol in different scopes. It's hard to determine where the solution actually goes. I would recommend removing the global scoped sol, and using the above points to return the solution from solutionFinder.

\$\endgroup\$
5
  • \$\begingroup\$ Thank you for the points you have made here, I will work on reworking the solution with your suggestions, it is still along the same track I was trying to work on. I did want to point out that I do not have two different sol variables, they're both pointing to the globally scoped sol as far as I can tell. \$\endgroup\$ Commented Jul 8, 2019 at 22:36
  • \$\begingroup\$ @CoryHarper ah I see that now. Still an unnecessary global variable though \$\endgroup\$
    – TCFP
    Commented Jul 8, 2019 at 22:47
  • \$\begingroup\$ I am a bit confused though, shouldn't i just start j as n - 1? And what method are you referring to when you say, "recursively call the same method with that value and j" is it a second method that was called in the for loop where j started as i? Just a bit of clarification, sorry if the questions seem basic \$\endgroup\$ Commented Jul 8, 2019 at 23:47
  • \$\begingroup\$ Upon writing an answer in code to this problem myself, I would remedy that to be the min of sqrt(k) and i, where i is initialized as n-1. I kinda wrote this all with a train of thought but I was just bored at work between projects so my apologies :) also the list returned when the difference is 0 should have j instead of i. The recursive call should return the answer for the remaining amount where the largest square is j-1. Base case is i=0. \$\endgroup\$
    – TCFP
    Commented Jul 8, 2019 at 23:54
  • \$\begingroup\$ Don't just use my solution verbatim though, use it as a template for your own. You understand the logical flow you want, take some time to understand how that can translate into code. Plan it out some, don't sweat the details of my answer too much. \$\endgroup\$
    – TCFP
    Commented Jul 8, 2019 at 23:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.