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:
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