rotate a matrix 45 degrees in javascript

Question

given a matrix like this one:

1 2 3
4 5 6
7 8 9

which can be represented as a 2 dimensional array:

arr = [[1,2,3], [4,5,6], [7,8,9]];

rotate the array so that it is read diagonally at a 45 degree angle and prints out this:

1
4 2
7 5 3
8 6
9

I spent a while coming up with a solution that I don't even fully intuitively understand, but it works, at least for 3x3 and 4x4 matrices. I was hoping to see more logical and clean implementations.

Here's my solution:

arr = [[1,2,3,0],[4,5,6,0],[7,8,9,0], [0,0,0,0]];
// arr[i][j];

transform(arr);

function transform(ar) {
    // the number of lines in our diagonal matrix will always be rows + columns - 1
    var lines = ar.length + ar[0].length - 1;
    // the length of the longest line...
    var maxLen = ~~(ar.length + ar[0].length)/2;
    var start = 1;
    var lengths = [];
    // this for loop creates an array of the lengths of each line, [1,2,3,2,1] in our case
    for (i=0;i<lines; i++) {
        lengths.push(start);
        if (i+1 < maxLen) {
            start++;
        } else {
            start--;
        }
    }
    // after we make each line, we're going to append it to str
    var str = "";
    // for every line
        for(j=0; j<lengths.length; j++) {
            // make a new line
            var line = "";
            // i tried to do it all in one for loop but wasn't able to (idk if it's possible) so here we use a particular for loop while lengths of the lines are increasing
            if (j < maxLen) {
                // lengths[j] is equal to the elements in this line, so the for loop will run that many times and create that many elements
                for(c=0; c<lengths[j]; c++) {
                    // if ar[r][c], the pattern here is that r increases along rows (as we add new lines), and decreases along columns. c stays the same as we add rows, and increases across columns 
                    line += ar[lengths[j]-1-c][c] + " ";
                    // when we've added all the elements we need for this line, add it to str with a line break
                    if (c == lengths[j]-1) { 
                        line += "\n"; str += line; 
                    }

                }
            } else {
                // when we're headed down or decreasing the length of each line
                for (r=0; r<lengths[j]; r++) {
                    // the pattern here tripped me up, and I had to introduce another changing variable j-maxLen (or the distance from the center).  r stays the same as rows increase and decreases across columns.  c increases along rows and decreases across columns
                    line += ar[lengths[j]-r+j-maxLen][j-maxLen+r +1] + " ";
                    // that's all our elements, add the line to str;
                    if (r == lengths[j] -1) {
                        line += "\n"; str += line; 
                    }
                }
            }
        }
        console.log(str);

}

Answer 1

The main idea is to partition the original matrix indexed by (i,j) according to i+j.

This is expressed in the code snippet rotated[i+j].push(arr[i][j]) below:

arr = [[1,2,3], [4,5,6], [7,8,9]];

var summax = arr.length + arr[0].length - 1; // max index of diagonal matrix
var rotated = []; // initialize to an empty matrix of the right size
for( var i=0 ; i<summax ; ++i ) rotated.push([]);
// Fill it up by partitioning the original matrix.
for( var j=0 ; j<arr[0].length ; ++j )
    for( var i=0 ; i<arr.length ; ++i ) rotated[i+j].push(arr[i][j]);
// Print it out.
for( var i=0 ; i<summax ; ++i ) console.log(rotated[i].join(' '))

Output:

1
4 2
7 5 3
8 6
9

---

In Ruby

Produces same output:

puts arr.transpose.flatten.group_by.with_index { |_,k|
    k.divmod(arr.size).inject(:+) }.values.map { |a| a.join ' ' }

Answer 2

The Idea: Walk the Diagonals and Clip

You could use the diagonal enumeration from Cantor, see Cantor pairing function, which is used to show that the set N x N has the same cardinality as the set N (i.e. natural numbers can be mapped one to one to pairs of natural numbers) and combine it with a condition that one skips those values which lie outside the rectangular matrix.

The Cantor pairing function pi takes two natural numbers i and j, i.e. the pair (i, j) and maps it to a natural number k

pi : |N x |N -> |N : pi(i, j) = k 

Use the reverse mapping to get this

pi^-1 : |N -> |N x |N : pi^-1(k) = (i, j)

i.e. one enumerates the cells of the "infinite Matrix" N x N diagonally. So counting up k and applying the inverse function will give the proper pair of indices (i, j) for printing the rotated matrix.

Example:

0->(0, 0)  2->(0, 1) | 5->(0, 2)  9->(0, 3)  . . 
1->(1, 0)  4->(1, 1) | 8->(1, 2)   
3->(2, 0)  7->(2, 2) |
---------------------+ <- clipping for 3 x 2 matrix
6->(3, 0)
.
. 

Calculation of the Inverse Cantor Pair Function

For input k these formulas give the pair (i, j):

w = floor((sqrt(8*k + 1) - 1) / 2)
t = (w*w + w) / 2
j = k - t
i = w - j

See the link given above for a derivation.

Resulting Algorithm

Given a m x n matrix A: i from [0, .., m - 1] enumerates the rows, and j from [0, .., n - 1] enumerates the columns

1. Start at k = 0
2. calculate the corresponding index pair (i, j)
3. print the matrix value A[i, j] if the indices i and j lie within your matrix dimensions m and n
4. print a new line, once your i hit the top of the matrix, i.e. if i == 0
5. increment k
6. continue with step 2 until you arrived at the index pair (i, j) = (n - 1, n - 1)

Sample Implementation in JavaScript

Note: I tried this out in the MongoDB shell, using its print() function.

Helper functions

function sprint(k) {
  var s = '' + k;
  while (s.length < 3) {
    s = ' ' + s;
  }
  return s;
}

function print_matrix(a) {
  var m = a.row_size;
  var n = a.column_size;
  for (var i = 0; i < m; i++) {
    var s = '';
    for (var j = 0; j < n; j++) {
      s += sprint(a.value[i][j]);
    }
    print(s);
  }
}

The Inverse of the Cantor pairing function

// inverse of the Cantor pair function
function pi_inv(k) {
  var w = Math.floor((Math.sqrt(8*k + 1) - 1) / 2);
  var t = (w*w + w) /2;
  var j = k - t;
  var i = w -j;
  return [i, j];
}

The algorithm

// "rotate" matrix a
function rot(a) {
  var m = a.row_size;
  var n = a.column_size;
  var i_max = m - 1;
  var j_max = n - 1;
  var k = 0;
  var s = '';
  do {
    var ij = pi_inv(k);
    var i = ij[0];
    var j = ij[1];
    if ((i <= i_max) && (j <= j_max)) {
      s += sprint(a.value[i][j]);
    }
    if (i == 0) {
      print(s);
      s = '';
    }
    k += 1
  } while ((i != i_max) || (j != j_max));
  print(s);
}

Example usage

// example
var a = { 
  row_size: 4, 
  column_size: 4, 
  value: [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16] ] 
};
print('in:');
print_matrix(a);
print('out:');
rot(a);

Output for 4x4 Matrix

in:
  1  2  3  4
  5  6  7  8
  9 10 11 12
 13 14 15 16
out:
   1
   5  2
   9  6  3
   13 10  7  4
   14 11  8
   15 12
   16

This method works for any m x n Matrix, e.g. 4 x 5:

in:
  1  2  3  4  5
  6  7  8  9 10
 11 12 13 14 15
 16 17 18 19 20
out:
  1
  6  2
 11  7  3
 16 12  8  4
 17 13  9  5
 18 14 10
 19 15
 20

or 4 x 3:

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

Answer 3

Here's my approach:

var origMatrix = [[1,2,3,4,5], [4,5,6,7,8], [9,10,11,12,13], [14,15,16,17,18], [19,20,21,22,23]];

var maxSize = origMatrix.length;//Presuming all internal are equal!
var rotatedMatrix = [];
var internalArray;
var keyX,keyY,keyArray;
for(var y=0;y<((maxSize * 2)-1);y++){
    internalArray = [];
    for(var x=0;x<maxSize;x++){
        keyX = x;
        keyY = y - x;
        if(keyY > -1){
            keyArray = origMatrix[keyY];
            if(typeof(keyArray) != 'undefined' && typeof(keyArray[keyX]) != 'undefined'){
                internalArray.push(keyArray[keyX]);
            }
        }
    }
    rotatedMatrix.push(internalArray);
}

//log results
for(var i=0;i<rotatedMatrix.length;i++){
    console.log(rotatedMatrix[i]);
}

Here's a JSFiddle of it in action (open the Console to see the results)

Answer 4

function transform(ar) {
    var result = [],
        i, x, y, row;
    for (i = 0; i < ar.length; i++) {
        row = [];
        for (x = 0, y = i; y >= 0; x++, y--) {
            row.push(ar[y][x]);
        }
        result.push(row);
    }
    for (i = 1; i < ar[0].length; i++) {
        row = [];
        for (x = i, y = ar[0].length - 1; x < ar[0].length; x++, y--) {
            row.push(ar[y][x]);
        }
        result.push(row);
    }
    return result;
}

This returns the rotated array, to print it out as you go just replace each result.push(row); line with console.log(row.join(" "));.