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 90o 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.