Spiral traversal of a matrix - recursive solution in JavaScript

Question

I'm trying to come up with a solution that takes in a matrix like this:

[[1,2,3,4],
 [5,6,7,8],
 [9,10,11,12],
 [13,14,15,16]]

and returns an array traversing the array as a spiral, so in this example: [1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]

I'm having trouble getting this recursive solution to work, in which the result array takes the first array, the final elements of the rest of the arrays, the bottom array in reverse order, and then the first elements of the middle arrays, and then reforms the array without that outer "shell" so that it can be recursively called on what's left until there's an array of one element in the center or a 2x2 matrix (my base cases, although the latter might not be necessary...)

My solution, which doesn't work, is as follows. Any suggestions on how I can make this work?

var spiralTraversal = function(matriks){
  var result = [];
    var goAround = function(matrix) {
        var len = matrix[0].length;
        if (len === 1) {
            result.concat(matrix[0]);
            return result;
        }
        if (len === 2) {
            result.concat(matrix[0]);
            result.push(matrix[1][1], matrix[1][0]);
            return result;
        }
        if (len > 2) {
            // right
            result.concat(matrix[0]);
            // down
            for (var j=1; j < matrix.length - 1; j++) {
                result.push(matrix[j][matrix.length -1]);
            }
            // left
            for (var l=matrix.length - 2; l > 0; l--) {
                result.push(matrix[matrix.length - 1][l]);
            }
            // up
            for (var k=matrix.length -2; k > 0; k--) {
                result.push(matrix[k][0]);
            }
        }
        // reset matrix for next loop
        var temp = matrix.slice();
        temp.shift();
        temp.pop();
        for (var i=0; i < temp.length - 1; i++) {
            temp[i] = temp[i].slice(1,-1);
        }
        goAround(temp);
    };
    goAround(matriks);  
};

Answer 1

Your code is very close but it is doing more than it needs to do. Here I simplify and bug fix:

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

var spiralTraversal = function(matriks){
  var result = [];
    var goAround = function(matrix) {
        if (matrix.length == 0) {
            return;
        }

        // right
        result = result.concat(matrix.shift());

        // down
        for (var j=1; j < matrix.length - 1; j++) {
            result.push(matrix[j].pop());
        }

        // bottom
        result = result.concat(matrix.pop().reverse());

        // up
        for (var k=matrix.length -2; k > 0; k--) {
            result.push(matrix[k].shift());
        }

        return goAround(matrix);
    };

    goAround(matriks);

    return result;
};
var result = spiralTraversal(input);

console.log('result', result);

Running it outputs:

result [1, 2, 3, 4, 12, 16, 15, 14, 13, 5, 6, 7, 8, 11, 10, 9]

JSFiddle: http://jsfiddle.net/eb34fu5z/

Important things:

• concat on Array returns the result -- it does not mutate the caller so you need to save the result of the concat like so: result = result.concat(otherArray)
• check the terminating condition at top of recursive array
• for each pass, do the expected (top, right, bottom, left)
• return the result

Here is how I would do it but I would add error checking to verify the array has an equal number of "rows" and "columns". So assuming the input is valid, here we go:

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

function run(input, result) {
    if (input.length == 0) {
        return result;
    }

    // add the first row to result
    result = result.concat(input.shift());

    // add the last element of each remaining row
    input.forEach(function(rightEnd) {
        result.push(rightEnd.pop());
    });

    // add the last row in reverse order
    result = result.concat(input.pop().reverse());

    // add the first element in each remaining row (going upwards)
    var tmp = [];
    input.forEach(function(leftEnd) {    
        tmp.push(leftEnd.shift());
    });
    result = result.concat(tmp.reverse());

    return run(input, result);
}

var result = run(input, []);

console.log('result', result);

Which outputs:

result [1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]

The general idea is we know for each pass we need to do these things:

1. Add the first array in input
2. Add the last item from each remaining array in input
3. Add the last array in input
4. Add the first item from each remaining array in input

So if we do the recursion with doing that at each pass, we can accomplish the spiraling.

JSFiddle: http://jsfiddle.net/2v6k5uhd/