Last active
August 22, 2024 13:43
-
-
Save yongjhih/fcc400a8deee71004cf559cc8718cb01 to your computer and use it in GitHub Desktop.
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
/// Weights of [0,0] anchor: | |
/// | j j j j j | |
/// | 0 1 2 3 4 | |
/// ----+----------- | |
/// i 0 | 0 1 2 3 4 | |
/// i 1 | 1 2 2 3 4 | |
/// i 2 | 2 2 3 3 4 | |
/// i 3 | 3 3 3 4 4 | |
/// i 4 | 4 4 4 4 5 | |
/// | |
/// Weights of [2,2] anchor: | |
/// | |
/// | j j j j j | |
/// | 0 1 2 3 4 | |
/// ----+----------- | |
/// i 0 | 4 3 2 3 4 | |
/// i 1 | 3 2 1 2 3 | |
/// i 2 | 2 1 0 1 2 | |
/// i 3 | 3 2 1 2 3 | |
/// i 4 | 4 3 2 3 4 | |
/// | |
/// Example for 2 cells with [2,2] anchor. x means occupied; | |
/// | |
/// | j j j j j | |
/// | 0 1 2 3 4 | |
/// ----+----------- | |
/// i 0 | 4 3 2 3 4 | |
/// i 1 | 3 x x x 3 | |
/// i 2 | 2 x 0 x 2 | |
/// i 3 | 3 2 1 x 3 <-- select [3,2],[3,1] weight: 1+2 = 3 | |
/// i 4 | 4 3 2 3 4 | |
function* weights(matrix, anchor, count) { | |
// count should be >0 | |
if (count <= 0) return; | |
if (!anchor) return; | |
if (!matrix) return; | |
const [x, y] = anchor; | |
const width = Math.max(...matrix.map(it => it.length)); | |
const height = matrix.length; | |
for (let i = 0; i < height; i++) { | |
for (let j = 0; j < width - count + 1; j++) { | |
let sumWeight = 0; | |
const points = []; | |
for (let k = 0; k < count; k++) { | |
sumWeight += Math.abs(i - x) + Math.abs(j + k - y); | |
points.push([i, j+k]); | |
} | |
yield [sumWeight, points]; | |
} | |
} | |
} | |
// For visual debugging | |
function bestWeights(matrix, anchor, count) { | |
if (count <= 0) return; | |
if (!anchor) return; | |
if (!matrix) return; | |
return Array.from( | |
weights(matrix, anchor, count).filter(([_, points]) => | |
points.length == count && points.every(([i, j]) => matrix[i][j].getAttribute('class').startsWith("empty"))) | |
).sortBy(([w, _]) => w).map(([_, points]) => points.map(([i, j]) => matrix[i][j])); | |
} | |
function bestWeight(matrix, anchor, count) { | |
if (count <= 0) return; | |
if (!anchor) return; | |
if (!matrix) return; | |
const best = Array.from( | |
weights(matrix, anchor, count).filter(([_, points]) => | |
points.length == count && points.every(([i, j]) => matrix[i][j].getAttribute('class').startsWith("empty"))) | |
).minBy(([it, _]) => it); | |
if (!best) return null; | |
const [_, points] = best; | |
return points.map(([i, j]) => matrix[i][j]); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment