Walls and Gates

index.js

// 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)