Created
August 31, 2021 20:23
-
-
Save BarakChamo/231a02aba2e2a58ac62d975cf1609e21 to your computer and use it in GitHub Desktop.
Walls and Gates
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
// 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