Skip to content

Instantly share code, notes, and snippets.

@BarakChamo
Created August 31, 2021 20:23
Show Gist options
  • Save BarakChamo/231a02aba2e2a58ac62d975cf1609e21 to your computer and use it in GitHub Desktop.
Save BarakChamo/231a02aba2e2a58ac62d975cf1609e21 to your computer and use it in GitHub Desktop.
Walls and Gates
// const table = [
// ["_", "W", "_", "_"],
// ["_", "_", "_", "W"],
// ["_", "W", "_", "W"],
// ["_", "W", "_", "_"],
// ]
const table = [
["G", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_"],
["_", "_", "_", "W","_", "_", "_", "W","_", "W", "_", "W","_", "_", "_", "W","_", "W", "_", "W","_", "W", "_", "W"],
["_", "W", "_", "W","_", "W", "_", "W","_", "W", "_", "W","_", "W", "_", "W","_", "W", "_", "W","_", "W", "_", "W"],
["_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_"],
["_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_"],
["_", "_", "_", "W","_", "W", "_", "W","_", "W", "_", "W","_", "_", "_", "W","_", "w", "_", "W","_", "W", "_", "W"],
["_", "W", "_", "W","_", "W", "_", "W","_", "W", "_", "W","_", "W", "_", "W","_", "W", "_", "W","_", "W", "_", "W"],
["_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_"],
["_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_"],
["_", "_", "_", "W","_", "w", "_", "W","_", "_", "_", "W","_", "_", "_", "W","_", "_", "_", "W","_", "W", "_", "W"],
["_", "W", "_", "W","_", "W", "_", "W","_", "W", "_", "W","_", "W", "_", "W","_", "W", "_", "W","_", "W", "_", "W"],
["_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_"],
["_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_"],
["_", "_", "_", "W","_", "W", "_", "W","_", "W", "_", "W","_", "_", "_", "W","_", "W", "_", "W","_", "W", "_", "W"],
["_", "W", "_", "W","_", "W", "_", "W","_", "W", "_", "W","_", "W", "_", "W","_", "W", "_", "W","_", "W", "_", "W"],
["_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_"],
["_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_"],
["_", "_", "_", "W","_", "W", "_", "W","_", "W", "_", "W","_", "_", "_", "W","_", "W", "_", "W","_", "_", "_", "W"],
["_", "W", "_", "W","_", "W", "_", "W","_", "W", "_", "W","_", "W", "_", "W","_", "W", "_", "W","_", "W", "_", "W"],
["_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_","_", "W", "_", "_"],
]
function sampleCell(r,c) {
let v = Infinity
if(table[r][c] == 'W')
v = Infinity
else if(table[r][c] == '_')
v = Infinity
else if(typeof table[r][c] != 'string')
v = table[r][c] + 1
else if(table[r][c] == 'G')
v = 1
return v
}
function fillCell(r,c) {
if(table[r][c] != '_') return 0
steps = Infinity
if(r > 0) // left
steps = Math.min(steps, sampleCell(r - 1, c))
if(r < (table.length - 1)) // right
steps = Math.min(steps, sampleCell(r + 1, c))
if(c > 0) // up
steps = Math.min(steps, sampleCell(r, c - 1))
if(c < (table[r].length - 1)) // down
steps = Math.min(steps, sampleCell(r, c + 1))
// no valid values to fill
if(steps == Infinity)
return 1
// update steps from gate for cell
table[r][c] = steps
// done with this cell
return 0
}
function fillGates() {
let remaining = 0
for (let r = 0; r < table.length; r++) {
for (let c = 0; c < table[r].length; c++) {
remaining += fillCell(r, c);
}
}
return remaining
}
function solution() {
let i = 0
while(true) {
i++
const remaining = fillGates()
if(remaining == 0) break
}
console.log(i)
}
solution()
console.log(table)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment