user6895092
user6895092

Reputation: 13

how to spirally traverse a matrix recursively - javascript

Please look at this JSFiddle: https://jsfiddle.net/hc2jcx26/

I am trying to spirally traverse a matrix output (any size) so that it prints each element in spiral order to console.log every 2 seconds:

var output = [[0, 1, 2, 3],
              [4, 5, 6, 7]];            

I am expecting this output:

0
1 //after 2 seconds delay
2 //after 2 seconds delay
3 //etc.
7
6
5
4

But I am not getting this with the code above. The output is all over the place and doesn't even have the right number of elements. I am using recursion to add a delay in my loop after every iteration (through setTimeout), but I do not think I am setting the variables correctly. But when I look at the code, it makes sense to me. What am I missing here?

Upvotes: 1

Views: 1138

Answers (4)

acontell
acontell

Reputation: 6922

This is my approach to your problem.

Iterative version

var matrix1 = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
], matrix2 = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
    [10, 11, 12]
], matrix3 = [
    [0, 1, 2, 3],
    [4, 5, 6, 7]
], matrix4 = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];

(function (matrix) {
    var i,
        nRows = matrix.length,
        nCols = matrix[0].length,
        rowLimit = nRows - 1,
        colLimit = nCols - 1,
        rounds = 0,
        printedElements = 0,
        nElements = nRows * nCols,
        timeoutLapse = 2000;

    function print(val) {
        printedElements += 1;
        setTimeout(function () {
            console.log(val);
        }, printedElements * timeoutLapse);
    }

    do {
        for (i = rounds; i <= colLimit - rounds; i += 1) {// from left to right
            print(matrix[rounds][i]);
        }

        for (i = rounds + 1; i <= rowLimit - rounds; i += 1) {// from top to bottom
            print(matrix[i][colLimit - rounds]);
        }

        for (i = colLimit - rounds - 1; i >= rounds; i -= 1) {// from right to left
            print(matrix[rowLimit - rounds][i]);
        }

        for (i = rowLimit - rounds - 1; i >= rounds + 1; i -= 1) {// from bottom to top
            print(matrix[i][rounds]);
        }
        rounds += 1;
    } while (printedElements < nElements);

})(matrix4);

Here's the fiddle (you'll have to open the console in order to see the results).

Recursive version

var matrix1 = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
], matrix2 = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
    [10, 11, 12]
], matrix3 = [
    [0, 1, 2, 3],
    [4, 5, 6, 7]
], matrix4 = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];

(function(matrix){
    var printedElements = 0,
        timeoutLapse = 1000;

    function print(val) {
        printedElements += 1;
        setTimeout(function () {
            console.log(val);
        }, printedElements * timeoutLapse);
    }

    function printArray(arr) {
        for(var i = 0; i < arr.length; i++) {
            print(arr[i]);
        }
    }

    // Recursive algorithm, consumes the matrix.
    function printMatrix(matrix, direction) {
        var dir = direction % 4,
            rowLimit = matrix.length - 1,
            i;

        if (dir === 0) {// from left to right
            printArray(matrix.shift());
        } else if (dir === 1) {// from top to bottom
            for(i = 0; i <= rowLimit; i++) {
                print(matrix[i].pop());
            }
        } else if (dir === 2) {// from right to left
            printArray(matrix.pop().reverse());
        } else {// from bottom to top
            for(i = rowLimit; i >= 0; i--) {
                print(matrix[i].shift());
            }
        }

        if (matrix.length) {// Guard
            printMatrix(matrix, direction + 1);
        }
    }

    // Initial call.
    printMatrix(matrix, 0);
})(matrix4);

I added some examples in order to test it. I just print out elements of the matrix every two seconds following the spiral pattern.

As you can see, the recursive version is more declarative though it empties the matrix completely. Here's the fiddle

Upvotes: 1

Akshar
Akshar

Reputation: 957

Using JS

UPDATE: Leveraging @acontell's print function

function spiral(matrix) {
    if (matrix.length <= 0) {
        return
    }
    for (var i = 0; i < matrix[0].length; i++) {
        print(matrix[0][i])
    }

    //Get last col
    for (var i = 1; i < matrix.length; i++) {
        print(matrix[i][matrix[0].length - 1])
    }

    //Get last row
    for (var i = matrix[0].length - 2; i >= 0; i--) {
        print(matrix[matrix.length-1][i])
    }

    //Get first column
    for (var i = matrix.length - 2; i > 0; i--) {
        print(matrix[i][0])
    }
    matrix = matrix.slice(1, -1)
    for (var i = 0; i < matrix.length; i++) {
        matrix[i] = matrix[i].slice(1, -1)
    }
    spiral(matrix)
}           
function print(val) {
    printedElements += 1;
    setTimeout(function () {
        console.log(val);
    }, printedElements * 2000);
}
var printedElements = 0
matrix = [[1, 2, 3, 4],
            [5, 6, 7, 8],
            [9, 10, 11, 12],
            [13, 14, 15, 16]]
matrix1 = [[1, 2, 3, 4, 31],
            [5, 6, 7, 8, 32],
            [9, 10, 11, 12, 33],
            [13, 14, 15, 16, 34],
            [35, 36, 37, 38, 39]]
spiral(matrix1)

Using Python Note: It's much easier with numpy

def spiral(matrix):
    if len(matrix) <= 0:
        return
    for v in matrix[0]:
        print(v)
    last_col = [matrix[i][len(matrix[0]) - 1] for i in range(1,len(matrix))]
    for v in last_col:
        print(v)
    last_row = reversed(matrix[len(matrix)-1][0:-1])
    for v in last_row:
        print(v)
    first_col = [matrix[i][0] for i in range (1, len(matrix) - 1)]
    first_col = reversed(first_col)
    for v in first_col:
        print(v)
    matrix = matrix[1:len(matrix) - 1]
    matrix = [m[1:len(matrix[0]) - 1] for m in matrix]
    spiral(matrix)
matrix = [[1, 2, 3, 4],
            [5, 6, 7, 8],
            [9, 10, 11, 12],
            [13, 14, 15, 16]]
matrix1 = [[1, 2, 3, 4, 31],
            [5, 6, 7, 8, 32],
            [9, 10, 11, 12, 33],
            [13, 14, 15, 16, 34],
            [35, 36, 37, 38, 39]]

spiral(matrix1)

UPDATE: With numpy

import numpy as np

def spiral(matrix):
    if len(matrix) <= 0:
        return
    for v in matrix[0]:
        print(v)
    last_col = matrix[1:, -1]
    for v in last_col:
        print(v)
    last_row = reversed(matrix[-1, :-1])
    for v in last_row:
        print(v)
    first_col = reversed(matrix[1:-1, 0])
    for v in first_col:
        print(v)
    matrix = matrix[1:-1, 1:-1]
    spiral(matrix)
matrix = [[1, 2, 3, 4],
            [5, 6, 7, 8],
            [9, 10, 11, 12],
            [13, 14, 15, 16]]
matrix1 = [[1, 2, 3, 4, 31],
            [5, 6, 7, 8, 32],
            [9, 10, 11, 12, 33],
            [13, 14, 15, 16, 34],
            [35, 36, 37, 38, 39]]
matrix2 = np.array([[1, 2, 3, 4, 31],
            [5, 6, 7, 8, 32],
            [9, 10, 11, 12, 33],
            [13, 14, 15, 16, 34],
            [35, 36, 37, 38, 39]])


spiral(matrix2)

Upvotes: 0

Andriy
Andriy

Reputation: 15442

try

var output = [[0, 1, 2, 3],
                 [4, 5, 6, 7]];

    var columns = output[0].length;
    var row;

    function spiralOrderRecursive (matrix, rowIndex) {
      rowIndex = rowIndex || 0;
      if (matrix.length) {
        row = rowIndex % 2 ? matrix[0].reverse() : matrix[0];
        row.forEach(function (item, index) {
          setTimeout(function () {
            console.log(item);
          }, (rowIndex * columns + index) * 2000);
        });
        spiralOrderRecursive (matrix.slice(1), ++rowIndex);
      }
    }
spiralOrderRecursive(output);

also NON RECURSIVE

var output = [[0, 1, 2, 3, 5],
                  [6, 7, 8, 9, 10],
                  [11, 12, 13, 14, 15],
                  [16, 17, 18, 19, 20]];;
var columns = output[0].length;

function spiralOrder(output) {
      output.forEach(function (row, rowIndex) {
        row = rowIndex % 2 ? row.reverse() : row;
        row.forEach(function (item, index) {
          setTimeout(function () {
            console.log(item);
          }, (rowIndex * columns + index) * 2000);
        });
      });
    }
spiralOrder(output);

Upvotes: 1

user17144
user17144

Reputation: 438

Pseudo-code for what you want to do

spiral_print(matrix)
{ 
 If the matrix has one row
   print the row and go to new line
 else if the matrix has two rows
  print the first row and go to new line
  sleep(2)
  print the second row in reverse order and go to new line
 else
  print the first row and go to new line
  sleep(2)
  print the second row in reverse order and go to new line
  sleep(2)      
  spiral_print(matrix.slice(2))
}

Upvotes: 0

Related Questions