Stumped on this Kata...'Directions Reduction'

i’ve been working on this CodeWars kata for too many hours now…it may be beyond my coding abilities tbh but I feel like I am so close! Could someone help me with the last leg of my solution? You can find the kata here: https://www.codewars.com/kata/550f22f4d758534c1100025a/train/javascript

let arr = ['SOUTH', 'NORTH', 'EAST', 'WEST', 'NORTH', 'SOUTH', 'WEST', 'NORTH', 'WEST', 'EAST', 'NORTH', 'SOUTH', 'WEST', 'EAST']

for (let i = 0; i < arr.length; i++){
  if (arr[i] === 'NORTH' && arr[i+1] === 'SOUTH' || arr[i] === 'SOUTH' && arr[i+1] === 'NORTH' || arr[i] === 'EAST' && arr[i+1] === 'WEST' || arr[i] === 'WEST' && arr[i+1] === 'EAST' ){
    newArray.push(arr[i], arr[i+1])
    }
}

// newArray  =  ['SOUTH', 'NORTH', 'EAST', 'WEST', 'NORTH', 'SOUTH', 'WEST', 'EAST', 'NORTH', 'SOUTH', 'WEST', 'EAST']
// expected output: ['WEST', 'NORTH']

so far i’ve set up this much of my logic to be able to extract all the directions that are not the desired output. I’ve been trying to figure out a way to compare the original array, ‘arr’, with ‘newArray’ to filter out the overlapping elements which would be the correct output. Is there a way of doing this? My attempts at using filter to do this have failed.

I’m not looking for the direct solution but just a nudge in the right direction since I’ve tried everything I can to no avail. Thanks!

Have you walked through your algorithm for first test case?
input [“NORTH”, “SOUTH”, “SOUTH”, “EAST”, “WEST”, “NORTH”, “WEST”]
newArray [ ‘NORTH’, ‘SOUTH’, ‘EAST’, ‘WEST’ ] (is what I’m calculating)
output [“WEST”]

If I understand what you are working towards it doesn’t appear to me that your interim array newArray will have the correct values to yield [“WEST”] even when you figure out how to remove the unwanted elements.

1 Like

yes I’ve console.logged thru my algorithm and the values I got for newArray in my post are correct. The expected output is also correct ( [‘WEST’, ‘NORTH’] ).

If you go thru arr from left to right and take out every opposite pair expressed in the first if-condition, you would take out every pair except arr6 and arr[7] (‘NORTH’) since they are not opposites.

If you compare newArray with arr you will see that the only missing pair in newArray is the expected output of [‘WEST’, ‘NORTH’] .

The only thing left to figure out is how to remove every element in newArray from arr.

I’m actually looking at this test case that I saw on the codewar site at the link
Test.assertSimilar(dirReduc([“NORTH”, “SOUTH”, “SOUTH”, “EAST”, “WEST”, “NORTH”, “WEST”]), [“WEST”])

Possibly I got a different set of test cases?

When I ran that through your calculation for newArray I got [ ‘NORTH’, ‘SOUTH’, ‘EAST’, ‘WEST’ ] identifying only 4 of the 7 directions as pairs, not an expected 6 leaving [‘WEST’]

1 Like

you’re right. I tried updated my approach and it’s close but still getting errors where I am getting the proper outputs but in the reverse order…try it out and let me know if you have any ideas? :

function dirReduc(arr){
	for (let i = 0; i < arr.length; i++){
		if (arr[i] === 'NORTH' && arr[i+1] === 'SOUTH' || arr[i] === 'SOUTH' && arr[i+1] === 'NORTH' || arr[i] === 'EAST' && arr[i+1] === 'WEST' || arr[i] === 'WEST' && arr[i+1] === 'EAST' ){
		
			while (arr.includes('NORTH') && arr.includes('SOUTH')){
				arr.splice(arr.indexOf('NORTH'), 1)
	    		arr.splice(arr.indexOf('SOUTH'), 1)
			}
  
    		while (arr.includes('EAST') && arr.includes('WEST')){
	    		arr.splice(arr.indexOf('EAST'), 1)
	    		arr.splice(arr.indexOf('WEST'), 1)
    		}     
		}
	}
		return arr
}
    

This is a lot simpler than you think. Create a stack (you use an array for this in JS). Iterate through your input array. Each iteration, you peek at the top of the stack and compare to the current value. Reducible? pop the stack. Not reducible? Push to the stack. The stack will contain the correct output once you’ve finished iterating

2 Likes

not really understanding how to implement the stack in this problem…i think i’ve been staring at this problem for too long. would really appreciate another hint

You are ending up with the right directions and the correct number of each direction but they are not always in the same order that the assertion test are expecting.

You are removing opposite pairs but not necessarily pairs adjacent to each other in the array. indexOf is returning the first (lowest index) opposite, not the opposite adjacent.

For instance if you remove a NORTH at index 7 and a SOUTH at index 2 instead of the SOUTH at index 6 you have removed the “wrong” SOUTH.

First pass
[‘EAST’, ‘WEST’, ‘SOUTH’, ‘NORTH’, ‘SOUTH’, ‘WEST’, ‘WEST’, ‘EAST’, ‘SOUTH’, ‘NORTH’]
north 3 south 2 - adjacent

Second pass
[ ‘EAST’, ‘WEST’, ‘SOUTH’, ‘WEST’, ‘WEST’, ‘EAST’, ‘SOUTH’, ‘NORTH’ ]
north 7 south 2 - not adjacent

By removing the wrong opposite you are also leaving the wrong remaining direction which in some cases leaves your resultant array out of order.

1 Like

This is a stack:

var stack = [];

To check the top value of the stack (peek):

var top = stack[stack.length - 1]

push/pop the stack:

stack.pop()
stack.push(value)

Iterate over your array of directions. For each direction, rules are: peek at stack. If value on top of stack + current value in array are N/S or E/W, pop stack. If they aren’t, push the current value in the array to the stack.

This means there is only a single pass, and you don’t need to poke around or manipulate inside the array: the stack will end up having the correct directions in the correct order.

1 Like