Spirally Traversing a Two-Dimensional Array in JavaScript

This is a way to traverse a two-dimensional array (or a matrix) from the top left, spirally in a clockwise manner in JavaScript.

This solution is inspired by functional programming and it uses tail recursion.

Steps:

-= Start =-
            [[1,2,3],       undefined
             [4,5,6],
             [7,8,9]]

Take the top off
            [[4,5,6],       "1,2,3"
             [7,8,9]]

Transpose the remaining
            [[4,7],         "1,2,3"
             [5,8],
             [6,9]]

Reverse the transposed
            [[6,9],         "1,2,3"
             [5,8],
             [4,7]]

-= Recurse =-

Top off
            [[5,8],         "1,2,3" + "," + "6,9"
             [4,7]]

Transpose
            [[5,4],         "1,2,3,6,9"
             [8,7]]

Reverse
            [[8,7],         "1,2,3,6,9"
             [5,4]]

-= Recurse =-

Top off
            [[5,4]]         "1,2,3,6,9" + "," + "8,7"

Transpose again
            [[5],           "1,2,3,6,9,8,7"
             [4]]

Reverse again
            [[4],           "1,2,3,6,9,8,7"
             [5]]

-= Recurse =-

Top off again ...
            [[5]]           "1,2,3,6,9,8,7" + "," + "4"

Transpose again ...
            [[5]]           "1,2,3,6,9,8,7,4"

Reverse again ...
            [[5]]           "1,2,3,6,9,8,7,4"

-= Recurse =-

Base Case
            return "1,2,3,6,9,8,7,4" + "," + "5"

JavaScript

/*
 * Accepts a matrix array
 * Returns the spirally traversed formatted string or -1 if invalid
 */
function toSpiralString(matrix) {
    if (matrix && matrix.constructor === Array && matrix[0] && matrix[0].constructor === Array) {
        return spiral(matrix);
    } else {
        var css = "background: #E80B00; color: #fff";
        console.log("%c Invalid input data, must be a matrix array ", css);
        return -1;
    }
}

/* 
 * Tail recursive implementation of displaying a matrix in a string format
 * Traverses the matrix spirally, clockwise rotation
 */
function spiral(matrix, result) {
    if (matrix.length == 1) {
        return (typeof result == "undefined" ? matrix[0].toString() : result + "," + matrix[0].toString());
    } else if (matrix.length >= 1 && matrix[0].length >= 1) {
        return spiral(transpose(matrix.slice(1,matrix.length)).reverse(), (typeof result == "undefined" ? matrix[0] : result + "," + matrix[0].toString()));
    } else {
        return [];
    }
}

// Flip over the diagonal
function transpose(matrix) {
    if (matrix.length >= 1 && matrix[0].length >= 1) {
        return Array.apply(null, Array(matrix[0].length)).map(function(e, i) {
            return matrix.map(function(arr) {
                return arr[i];
            })
        });
    } else {
        return [[]];
    }
}

// Test
toSpiralString([[1,2,3],
                [4,5,6],
                [7,8,9]]) == "1,2,3,6,9,8,7,4,5";
 
83
Kudos
 
83
Kudos

Now read this

Responsive Design

Recently I attended a Responsive Design workshop headed by industry experts Ethan Marcotte and Karen McGrane. This post is a summary of my notes and key takeaways from an e-commerce website’s point of view. What is Responsive Design? #... Continue →