Created
January 9, 2022 10:44
-
-
Save blzjns/42985bdf6e4d151bc53a2f50c5e02560 to your computer and use it in GitHub Desktop.
BinarySearch on multi-dimensional (2D grid), best jump/move from position [X, Y] given a set of directions (up, down, left, right)
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
/* | |
Using BinarySearch, | |
from a given point [x, y] on a 2D grid (WxH) find the next-best position in order to reach an element as soon as possible. | |
*/ | |
const W = readInt('Building width: '); // width of the building. | |
const H = readInt('Building height: '); // height of the building. | |
const N = readInt('Max. no of turns: '); // maximum number of turns before game over. | |
let X = readInt('Start from X: '); | |
let Y = readInt('Start from Y: '); | |
var building = { | |
maxX: W - 1, // x right-most | |
minX: 0, // x left-most | |
maxY: H - 1, // y down-most | |
minY: 0, // y up-most | |
}; | |
// game loop | |
let count = 0; | |
while (count <= N) { | |
const bombDir = readline(); // the direction of the bombs from batman's current location (U, UR, R, DR, D, DL, L or UL) | |
if (bombDir.includes("U")) { | |
building.maxY = Y - 1; | |
} | |
if (bombDir.includes("D")) { | |
building.minY = Y + 1; | |
} | |
if (bombDir.includes("L")) { | |
building.maxX = X - 1; | |
} | |
if (bombDir.includes("R")) { | |
building.minX = X + 1; | |
} | |
// using bitwise operator >> to avoid Math.floor: | |
// 11 >> 1 == Math.floor(11 / (2^1)) => 5 != 5.5 | |
// 11 >> 2 == Math.floor(11 / (2^2)) => 2 != 2.75 | |
X = (building.maxX + building.minX) >> 1; | |
Y = (building.maxY + building.minY) >> 1; | |
// the location of the next window Batman should jump to. | |
console.log(X + ' ' + Y); | |
count++; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment