5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.