Skip to content

Instantly share code, notes, and snippets.

@marwahaha
Last active November 23, 2018 12:39
Show Gist options
  • Save marwahaha/05353002180a3be1ea6011b90a604ce3 to your computer and use it in GitHub Desktop.
Save marwahaha/05353002180a3be1ea6011b90a604ce3 to your computer and use it in GitHub Desktop.
function unspiral(i, j) {
/**
* j
* ^
* |
* 12 13 14 15 16
* 11 2 3 4 17
* 10 1 0 5 18 --> i
* 9 8 7 6 19
* 24 23 22 21 20
*
* If you put a spiral on a grid,
* this finds the number located at (i, j).
*
* Assumptions:
* 1. Spiral starts at (0, 0) with 0.
* 2. Spiral increments by 1 each time.
* 3. Spiral moves clockwise.
* 4. Loop n of the spiral finishes at (-n, -n)
* (bottom left corner in Cartesian plane).
*
* The idea of this solution is to find the loop we're on,
* then walk backwards on the spiral
* until we reach the end of the previous loop.
*
* Note that every point on loop k has |i| = k and/or |j| = k.
*
* We increment at every point after the center,
* so the value at the last point in loop n
* is the number of points in a square from (-n, -n) to (n, n)
* with the center removed.
*/
const loopNum = Math.max(Math.abs(i), Math.abs(j));
const getLastPointInLoop = (n) => (2*n + 1)**2 - 1;
const endOfPreviousLoop = getLastPointInLoop(loopNum - 1);
const onTopSide = (x,y) => y > x && y > -x;
const onLeftSide = (x,y) => y > x && y < -x;
const onBottomSide = (x,y) => y < x && y < -x;
const onRightSide = (x,y) => y < x && y > -x;
const onBottomLeftCorner = (x,y) => y < 0 && x === y;
const onBottomRightCorner = (x,y) => y < 0 && x === -y;
const onTopRightCorner = (x,y) => y > 0 && x === y;
const onTopLeftCorner = (x,y) => y > 0 && x === -y;
if (onLeftSide(i,j) || onTopLeftCorner(i,j) ) {
return endOfPreviousLoop + (loopNum + j);
} else if (onTopSide(i,j) || onTopRightCorner(i,j)) {
return endOfPreviousLoop + 2*loopNum + (loopNum + i);
} else if (onRightSide(i,j) || onBottomRightCorner(i,j)) {
return endOfPreviousLoop + 4*loopNum + (loopNum - j);
} else if (onBottomSide(i,j) || onBottomLeftCorner(i,j)) {
return endOfPreviousLoop + 6*loopNum + (loopNum - i);
}
return 0;
}
// Testing
console.assert(unspiral(0, 0) === 0, "center should be at origin and should be zero");
console.assert(unspiral(-2, -2) === 24, "each loop should end at bottom left corner");
console.assert(unspiral(-3, -2) === 25, "spiral should go clockwise");
console.assert(unspiral(-3, -1) === 26, "spiral should go clockwise");
console.assert(unspiral(3, 1) === 38, "(3, 1) should be 38");
// see https://hackernoon.com/clean-code-challenge-unspiral-b607a8bc7e83
console.assert(unspiral(-2, -1) === 9, "should match test in Medium post");
console.assert(unspiral(-123, 456) === 831165, "should match test in Medium post");
// Visualize spiral (note: not Cartesian plane, but matches table in Medium post)
function seeSpiral(numLoops) {
const output = [];
for (idx = -numLoops; idx <= numLoops; idx++) {
const row = []
for (jdx = -numLoops; jdx <= numLoops; jdx++) {
row.push(unspiral(idx, jdx));
}
output.push(row);
}
return output;
}
console.log(seeSpiral(3));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment