Skip to content

Instantly share code, notes, and snippets.

@germanescobar
Created January 22, 2022 00:48
Show Gist options
  • Save germanescobar/062262aa4c1dd52d8a563c7c0b7fb693 to your computer and use it in GitHub Desktop.
Save germanescobar/062262aa4c1dd52d8a563c7c0b7fb693 to your computer and use it in GitHub Desktop.
var avoidFlood = function(rains) {
const result = []
const filled = new Set()
return findSolution(rains, filled, result, 0)
};
function findSolution(rains, filled, result, day) {
if (day >= rains.length) { // lo logramos!
return result
}
if (rains[day] > 0 && filled.has(rains[day])) { // inundación!!!!!
return []
}
if (rains[day] > 0) { // ese día llovió
result[day] = -1
filled.add(rains[day])
return findSolution(rains, filled, [...result], day + 1)
} else { // no llovió, tenemos que secar un lago
if (filled.size === 0) { // no hay lagos llenos
result[day] = 1
return findSolution(rains, filled, [...result], day + 1)
} else { // probar secando cada lago
for (lake of filled) {
const lakes = new Set(filled)
lakes.delete(lake) // lo vamos a secar
result[day] = lake
const s = findSolution(rains, lakes, [...result], day + 1)
if (s.length > 0) return s
}
return []
}
}
}
@germanescobar
Copy link
Author

var avoidFlood = function(rains) {
  const filled = {}
  const noRain = []
  const result = []
  for (let i=0; i < rains.length; i++) {
    result.push(-1)
    if (rains[i] === 0) {
      noRain.push(i)
      result[i] = 0
    } else {
      if (filled[rains[i]] !== undefined) {
        if (noRain.length === 0) return []
        const from = filled[rains[i]]
        let found = false
        for (let j=0; j < noRain.length && !found; j++) {
          if (noRain[j] > from) {
            result[noRain[j]] = rains[i]
            noRain.splice(j, 1)
            found = true
          }
        }
        
        if (!found) return []
      } else {
        filled[rains[i]] = i
      }  
    }
  }
  
  for (let i=0; i < result.length; i++) {
    if (result[i] === 0) result[i] = 1
  }
  
  return result
};

Esta solución debería pasar por tiempo pero no está seleccionando bien el día de no lluvia.

@germanescobar
Copy link
Author

Ya encontré el error, faltaba actualizar el último día de lluvia de ese lago!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment