A Valid Walk — Javascript Algorithm

Another interesting algorithm that I found is a function that receives an array with cardinal points which enumerates the direction of the walk for the same amount of time/distance and returns true if the walker returns in the exact same spot.

This sounds a bit complex when I first read it, but let’s make a small draw.

I will use draw.io

This would be one cardinal point. Having in mind that we need a valid walk so we can visualise it I will draw:

["n',"w","n","w","s","s","e","e"]

After analysing this draw I realised the solution.

The number of N must be equal to the number of S (the opposite direction) and the number of W must be equal with the number of E. If there is any point missing than the start point will be missed.

With that in mind, I’ve created 4 variable.

let n = 0, s = 0, e = 0, w = 0

And then I mapped over the array given and for any direction, I incremented the specific variable.

In this way, I saved the number of each direction. Now what’s left is to compare those numbers.

In this way, we get true if the numbers are equal and false if they are not.

The complete function can be found here.

Conclusion

What I learned from here is that visualising the problem can be very helpful and transform a complicated algorithm, at first sight, into an iteration and an if statement.