Rearrange elements in two-dimensional array spiral order

Question

Recently I was asked to write algorithm to rearrange elements in two-dimensional array in spiral order.

Input array: Output array:

[  1,  2,  3,  4]           [  1,  2,  3,  4 ]
[  5,  6,  7,  8]    = >    [  8, 12, 11, 10 ]
[  9, 10, 11, 12]           [  9,  5,  6,  7 ]

I came up with the following solution using JavaScript:

(function(){
var Spiralify = function(matrix){
    function isArray(obj){
        return Object.prototype.toString.call(obj) === '[object Array]'
    }

    //Matrix is not specified or not an array
    if( !matrix || !isArray(matrix) ) { console.log('Matrix is not an array'); return; }

    var rows = matrix.length;
    if( rows <= 1 ) return matrix;
    //If first element of matrix is not an array, we cant define amount of columns in matrix, so just wrap it in array and return
    if(!isArray(matrix[0])) return [matrix];

    var cols = matrix[0].length;
    //If rows of the matrix are empty arrays, return null
    if( cols == 0 ) return matrix;

    //If arrays, corresponding to rows, have different amount of elements, return null
    if(matrix.some(function(el){ return el.length != cols; })) { console.log('All rows must have equal amount of columns'); return; }

    //If we have only one column, just transpond the array and wrap it into another array
    if( cols == 1) return [matrix.map(function(i){ return i[0]; })];

    function getUpperCorner(r1,c1,r2,c2)
    {
        for(var i=c1;i<=c2;i++)
            tmpArray.push(matrix[r1][i]);

        for(var j=r1+1;j<=r2;j++)
            tmpArray.push(matrix[j][c2]);

        if(r2-r1 > 0)
            getLowerCorner(r1+1,c1,r2,c2-1);
    }

    function getLowerCorner(r1,c1,r2,c2)
    {
        for(var i=c2;i>=c1;i--)
            tmpArray.push(matrix[r2][i]);

        for(var j=r2-1;j>=r1;j--)
            tmpArray.push(matrix[j][c1]);

        if(r2-r1 > 0)
            getUpperCorner(r1,c1+1,r2-1,c2);
    }

    var tmpArray = [];
    getUpperCorner(0,0,rows-1,cols-1);

    var result = new Array(rows);
    for(var i=0;i<rows;i++)
        result[i] = tmpArray.splice(0,cols);

    return result;
}

var matrix1 = [[1,2,3,4,5],[6,7,8,9,10],[11,12,13,14,15]];
var matrix2 = [[1,2,3,4,5],[6,7,8],[11,12,13,14,15]];
var matrix3 = [[1,2,3,4]];
var matrix4 = [[1],[2],[3],[4],[5],[6]];
var matrix5 = null;
var matrix6 = 1234;
var matrix7 = [];
var matrix8 = [[],[],[]];
var matrix9 = [1,2,3,4];
var matrix10 = 'Hello';

console.log (Spiralify(matrix1));
console.log (Spiralify(matrix2));
console.log (Spiralify(matrix3));
console.log (Spiralify(matrix4));
console.log (Spiralify(matrix5));
console.log (Spiralify(matrix6));
console.log (Spiralify(matrix7));
console.log (Spiralify(matrix8));
console.log (Spiralify(matrix9));
console.log (Spiralify(matrix10));
})(window);

But this solution was a show-stopper. I'm trying to learn from the defeat and would really appreciate some feedback on why this code is unappropriate.

Answer 1

I'm not sure what exactly about your code made it a "show-stopper." Your use of tmpArray has a bit of a smell to it. There are issues of readability (why does the line for(var i=c1;i<=c2;i++) only have one space in it??). Your core algorithm (getUpperCorner and getLowerCorner) isn't documented and is fairly hard to read.

Personally, though, I would have approached this as a straight recursion problem. So you have the following matrix:

 1  2  3  4
 5  6  7  8
 9 10 11 12

Your "spiral" begins with the the top row, 1 2 3 4. So chop that off and save it.

   1  2  3  4
✂ ┄┄┄┄┄┄┄┄┄┄┄┄
   5  6  7  8
   9 10 11 12

Now you'll notice that the rightmost column of the remaining part, 8 12, is the next part of the spiral. But what if we turn it 90º counter-clockwise?

 5  6  7  8  =>   8 12
 9 10 11 12       7 11
                  6 10
                  5  9

Now 8 12 the top row! Chop it off and repeat:

   8 12
✂ ┄┄┄┄┄┄
   7 11  =>  11 10  9  =>    11 10  9
   6 10       7  6  5     ✂ ┄┄┄┄┄┄┄┄┄┄
   5  9                       7  6  5  =>  5  =>   5
                                           6    ✂ ┄┄┄
                                           7       6  =>  6  7  (end!)
                                                   7

By now you've seen the pattern. To get a matrix's "spiral" you just take off the top row, rotate what's left, then get its spiral, and so on.

Def Spiralify( Matrix )
  If( Matrix has only one row )
    Return( the row )

  Else
    FirstRow     := first row of Matrix
    RestOfMatrix := all of Matrix except the first row

    NextMatrix := RotateLeft( RestOfMatrix )

    NextSpiral := Spiralify( NextMatrix )

    Result := JoinArrays( FirstRow, NextSpiral )

    Return( Result )

RotateLeft will actually make up the most lines of code, but it's just a straightforward nested loop, and the rest basically writes itself.

Update

I had some time to write up an actual implementation. Rather than paste it here you can check it out on jsFiddle.