Help optimize my code!

I can’t pass this challenge because my code is too SLOW

I’m not sure why its so slow, is it because of SWITCH usage inside for the for loop? or the ternary operators inside the switch statement?

Code Challenge: Training on Directions Reduction | Codewars

function dirReduc(arr){
  if (arr.length === 0  || arr.length === 1) return []; 
  let lengthTracker = arr.length;  // AMENDED
  for (let i = 0; i < arr.length; i++) { 
  if (lengthTracker > arr.length) {
    lengthTracker = arr.length;
    i = 0;
  }
    switch(arr[i]) {
  case "NORTH":
 arr[i-1] === "SOUTH"? arr.splice(i-1,2) : 
 arr[i+1] === "SOUTH"? arr.splice(i,2) : null
  break;
  case "SOUTH":
 arr[i-1] === "NORTH"? arr.splice(i-1,2) : 
 arr[i+1] === "NORTH"? arr.splice(i,2) : null
    break;
  case "EAST":
 arr[i-1] === "WEST"? arr.splice(i-1,2) : 
 arr[i+1] === "WEST"? arr.splice(i,2) : null
    break;
  case "WEST":
 arr[i-1] === "EAST"? arr.splice(i-1,2) : 
 arr[i+1] === "EAST"? arr.splice(i,2) : null
    break;
}
if(i===arr.length-1 && lengthTracker > arr.length) i=0   // AMENDED
  }
 return arr;
}

dirReduc(["NORTH", "EAST", "SOUTH", "EAST", "WEST", "NORTH", "WEST"])

It is failing because when I run the second one of their tests:

Test.assertSimilar(
  dirReduc(["NORTH", "WEST", "SOUTH", "EAST"]),
  ["NORTH", "WEST", "SOUTH", "EAST"]
)

It is in an infinite loop.

We should always be very, very careful about messing with out iteration variables:

i===arr.length-1? i=0:null

I’d rethink that. You code looks like O(n) but when you add that it, it becomes O(Infinity).

2 Likes

So here are a few oddities I can see in your code:

if (arr.length === 0 || arr.length === 1) return [];

Could an array of directions containing one element be reduced further? Here you are saying if you get an input of ["WEST"], you can reduce it to [].

if (lengthTracker > arr.length) {
    lengthTracker = arr.length;
    i = 0;
  }

This has no meaning, you declared lengthTracker, but never initialized or assigned a value to it. So lengthTracker is always undefined.

Here is the major issue:

i===arr.length-1? i=0:null

Here you are saying if i ever reaches the last element, you loop back to the beginning. This creates a dangerous situation where you enter an infinite loop.

And here are some potential small issues:

  • Your switch statement cases each contain two checks for element before and after. But consider if you are always checking the one after, would there ever be a situation where you even need to check the element before?

  • Your ternary statements often result in null in one of the conditions, usually in that case we would just use a regular if statement.

I have made 2 minor amendments, now its not in an infinite loop and works (though its still like 700+ms, i assume that’s very slow?). splicing is some tricky stuff, its always the index problem.

oh nvm, yeah like u said i could just use if statements, ill try that.

So I just found someone’s answer to this problem:

function dirReduc(arr){
    if (arr.length === 0 || arr.length === 1) return [];
    let lengthTracker = 0;                  // the write-point

    for(let i = 0; i < arr.length; i++) {   // i is the read-point
        if(lengthTracker == 0) {
            // if no output, copy readpoint to write-point and advance
            arr[lengthTracker++] = arr[i];
        } else {
            // replaces switch()
            if (((arr[lengthTracker-1] === "NORTH") && (arr[i] === "SOUTH"))
             || ((arr[lengthTracker-1] === "SOUTH") && (arr[i] === "NORTH"))
             || ((arr[lengthTracker-1] === "EAST") && (arr[i] === "WEST"))
             || ((arr[lengthTracker-1] === "WEST") && (arr[i] === "EAST"))) {
                lengthTracker--;    // annihilate by decrementing the writepoint
            } else {
                // copy readpoint to writepoint and advance
                arr[lengthTracker++] = arr[i];
            }
        }
    }
    //trim the array to only include what was written
    arr.splice(lengthTracker);
    return arr;
}

dirReduc(["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]) // WEST

And I must say its a big ball of confusion. Usage of write-point and read-point etc. Can you explain this flow of algorithm to me? I’m not understanding how the answer is gotten correctly.

Yeah, it’s an odd little solution. It is keeping track of where it is in the array and it is overwriting the answer into the portion of the array that has already been checked. It makes for an efficient solution, if a little hard to read. Personally, I probably would have wanted something a little more “wasteful” but easier to read.

If you want to understand this, I think putting a console.log statement at the beginning of the loop, something like:

console.log(`i=${i} lengthTracker=${lengthTracker}  arr=${arr.join()} 
 prev=${arr[lengthTracker-1]}  curr=${arr[lengthTracker]}`)

to watch it in action.

This is a good answer, and to answer your question:

  • write-point/read-point aren’t really a thing, they are describing:
    • write-point:where your next change of data will take place in the arr
    • read-point:where your next intake of data will take place in the arr

Essentially, the author reuses the original array by setting two pointers in the array, one where you will be writing in the actual directions, and one where you will be reading the input directions. Then realizing that anytime you find an opposing direction pair, you can go back one on the writing pointer, essentially overwriting that pair in the original array.

Eventually you are left with an array that’s in most cases having too many elements, but you can splice out the actual right number of elements by realizing that only the elements that had been passed over by the writing pointer can contain correct data.

The pros/cons of this method: Pros are: It is linear in time, which is best case scenario here, and by reusing the original array, the author achieves constant space, which is best case scenario as well.

Cons are: It reuses the original array, meaning the input is mutated, which in my opinion is not great. It means in a large scale app, too many of these input-mutating functions and you can have unintended side effects difficult to catch.

3 ways you can attempt to read/understand your own or other people’s code:

  1. console.log() in the right places
  2. debug mode to step through the code if your coding app supports it
  3. pen/paper, initialize the variables on paper and write down the change as you pretend to step through the code like a computer