How can I traverse a NxN grid in a cyclical manner using JavaScript?

Question

For example a 3x3 grid.

[ 1 ] [ 2 ] [ 3 ]
[ 4 ] [ 5 ] [ 6 ]
[ 7 ] [ 8 ] [ 9 ]

I need traverse the the grid in a cyclical manner and output each number where the path has been.

The input for a 3x3 grid is a multidimensional array:

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

For a 3x3 grid the output should be an array or string.

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

The solution also needs to scale to any NxN grid.

I am looking for the solution of this programming problem. I have tried many different methods to do this but I can not seem to do it. I would love to learn how and also some bonus advice how I can improve my problem solving ability.

Answer 1

Here is a possible solution using some recursion:

function traverseSpiral(n, level=0) {
  //USE A CURSOR TO TRAVERSE THE OUTERMOST LOOP FOR n
  var x=0;
  var y=0;
  //TOP
  while (x<n) {
    output.push(input[level+y][level+x]);
    x++;
  }
  x--;
  y++;
  //RIGHT
  while (y<n) {
    output.push(input[level+y][level+x]);
    y++;
  }
  y--;
  x--;
  //BOTTOM
  while (x>=0) {
    output.push(input[level+y][level+x]);
    x--;
  }
  x++;
  y--;
  //LEFT
  while (y>0) {
    output.push(input[level+y][level+x]);
    y--;
  }
  y++;
  //WE COMPLETED THE LOOP. NOW WE WE ARE LEFT WITH A GRID OF (N-2)x(N-2)
  n = n - 2;
  if (n>1) {
    //TRAVERSE THE NEXT LEVEL INNER LOOP
    return traverseSpiral(n,level+1);
  } else if (n==1) {
    //IF N=1 THEN THERE IS ONE SPACE LEFT. JUST GET THAT LAST SPACE AND WE'RE DONE.
    output.push(input[y][x+1]);
    return output;
  } else {
    //IF N=0 THEN WE ARE DONE.
    return output;
  }
}

Working samples:

4x4 https://jsfiddle.net/mspinks/4gaskn8o/19/

3x3 https://jsfiddle.net/mspinks/4gaskn8o/21/

Note: this works for NxN, as specified. It does not work for NxM.

Answer 2

Here is the fiddle code

See the pattern.

If you get to limit of the array or to the previous position, then you have to either decrease/increase the column variable or row variable.

The pattern for cyclic looping is

1. increase column variable ( j )
2. increase row variable ( i )
3. decrease column variable ( j )
4. decrease row variable ( i )
5. increase column variable ( j )
6. increase row variable ( i ) .... ....

Here is my code

//input array
var input = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]

//get the no of rows
var noOfRows = input.length

//get the no of cols
var noOfCols = input[0].length

//initialize i and j to 0
var i =0, j = 0;

//first we go by increasing var j
var status = "increasingJ";

//output array initalize to empty array
var output = []

//till output is no equal to 9, loop through
while(output.length != noOfCols * noOfRows ){

    if(status == "increasingI"){
        
        if( input[i] == undefined || input[i][j] == null){
            i--;
            j--;
            status = "decreasingJ";     
        }else{
            output.push(input[i][j]);
            input[i][j] = null;
            i++;
        }
    }
    if(status == "increasingJ"){
        if( input[j] == undefined || input[i][j] == null){
        
            j--;
            i++;
            status = "increasingI";     
        }else{
            output.push(input[i][j]);
            input[i][j] = null;
            j++;
        }
    }
    if(status == "decreasingI"){
        if( input[i] == undefined || input[i][j] == null){
            i++;
            j++;
            status = "increasingJ";         
        }else{
            output.push(input[i][j]);
            input[i][j] = null;
            i--;
        }
    }
    if(status == "decreasingJ"){
        if( input[j] == undefined || input[i][j] == null){
            j++;
            i--;    
            status = "decreasingI";         
        }else{
            output.push(input[i][j]);
            input[i][j] = null;
            j--;
        }
    }
}