martes, 15 de enero de 2019

Spiral Matrix Problem - My solution

I read about this problem while practicing for an interview at Facebook.

You need to write a function that creates a matrix of n*n; where every number from 1 to n*n goes around the square matrix like a spiral:

print(matrix(10));

Result:

[ 1,  2,  3,  4,   5,  6,  7,  8,  9, 10]
[36, 37, 38, 39,  40, 41, 42, 43, 44, 11]
[35, 64, 65, 66,  67, 68, 69, 70, 45, 12]
[34, 63, 84, 85,  86, 87, 88, 71, 46, 13]
[33, 62, 83, 96,  97, 98, 89, 72, 47, 14]
[32, 61, 82, 95, 100, 99, 90, 73, 48, 15]
[31, 60, 81, 94,  93, 92, 91, 74, 49, 16]
[30, 59, 80, 79,  78, 77, 76, 75, 50, 17]
[29, 58, 57, 56,  55, 54, 53, 52, 51, 18]
[28, 27, 26, 25,  24, 23, 22, 21, 20, 19]

These are the notes I took to break down the problem:



After I solved it I researched other solutions but (modesty apart) I think my solution is prettier :-p.

Solution code in Javascript:

function print(m) {
  for (let i = 0; i < m.length; i++) {
    console.log(m[i]);
  }
}

function matrix(n) {
  if (n < 0) return [];
  let p = 0; // pivot
  let r = n + n - 1;
  let m = [];
  for(let i=0; i<n; i++) {
      m[i] = new Array(n);
  }
  
  let i = 0, j = 0, last = n * n;
  for (let k = 1; k <= last; k++) {
    // turn every last - floor(r^2/4)
    m[j][i] = k;
    let s = (last - Math.floor((r*r)/4));
    if(k === s) {
      p++;
      r--;
      if (p > 3) p = 0;
    }
    if (p === 0) i++;
    else if (p === 1) j++;
    else if (p === 2) i--;
    else if (p === 3) j--;
  }
  return m;
}


No hay comentarios.:

Publicar un comentario