Last active
November 23, 2018 12:39
-
-
Save marwahaha/05353002180a3be1ea6011b90a604ce3 to your computer and use it in GitHub Desktop.
clean code challenge at https://hackernoon.com/clean-code-challenge-unspiral-b607a8bc7e83
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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