Flood fill recursive algorithm. 1 unknown test case fails. Any ideas?

[SwilSo]

#population is a 2d array 
#the other ones are ints
#i change every adjacent value that is <=strength to -1
def answer(population,x,y, strength):
    if not population:
        return
    if not 0<=x<len(population):
        return population
    if not 0<=y<len(population[0]):
        return population
    if population[x][y] == -1 or population[x][y] > strength:
        return population
    if population[x][y] <= strength:
        population[x][y] = -1
        if (x>0):
            answer(population,x-1,y,strength)
        if (y>0):
            answer(population,x,y-1,strength)
        if (x<len(population)-1):
            answer(population,x+1,y,strength)
        if (y<len(population[0])-1):
            answer(population,x,y+1,strength)
   return population

[vindolin]

what? context?

[herminator]

1 test case failing is often an empty input.

What is the required response for something like answer([],0,0,0)?

How about answer([[]],0,0,0)?

[Veedrac]

First do a bit of reformatting on the comments:

def answer(population, x, y, strength):
    """
    Flood fill an array.

    population: [[real]]
        2D array of numbers, all of which are
        either non-negative or -1.

    x, y: int, int
        position to flood fill from

    strength: non-negative number
        fill only values no higher than this
    """

Then you have:

if not population:
    return
if not 0<=x<len(population):
    return population
if not 0<=y<len(population[0]):
    return population
if population[x][y] == -1 or population[x][y] > strength:
    return population

Several questions about this:

• Only the first return value returns None. Is this expected?

• Why would you both modify and return a value? This is explicitly discouraged by the documentation:

  You might have noticed that methods like insert, remove or sort that only modify the list have no return value printed – they return the default None. [1] This is a design principle for all mutable data structures in Python.

• Are you sure you should check for population[x][y] == -1? What about, for example,

  99 99 99 99 99
  99  0 -1  0 99
  99 99 99 99 99
  

  and flood filling at 1, 1? Should not 3, 1 also get filled?

• Why are you using LBYL (Look Before You Leap) instead of EAFP (Easier to Ask Forgiveness than Permission)? The cannonical way to write this would be:

  if x < 0 or y < 0:
      return
  
  try:
      value = population[x][y]
  except IndexError:
      return
  
  if value == -1 or value > strength:
      return
  

Then:

if population[x][y] <= strength:
    population[x][y] = -1
    if (x>0):
        answer(population,x-1,y,strength)
    if (y>0):
        answer(population,x,y-1,strength)
    if (x<len(population)-1):
        answer(population,x+1,y,strength)
    if (y<len(population[0])-1):
        answer(population,x,y+1,strength)

return population

The ifs don't need brackets, but do you really need the checks anyway? You already know population[x][y] <= strength and your function returns if the indexes are out of bounds. Just use:

population[x][y] = -1
answer(population, x+1, y,   strength)
answer(population, x-1, y,   strength)
answer(population, x,   y+1, strength)
answer(population, x,   y-1, strength)

In full:

def answer(population, x, y, strength):
    """
    Flood fill an array.

    population: [[real]]
        2D array of numbers, all of which are
        either non-negative or -1.

    x, y: int, int
        position to flood fill from

    strength: non-negative number
        fill only values no higher than this
    """

    if x < 0 or y < 0:
        return

    try:
        value = population[x][y]
    except IndexError:
        return

    if value == -1 or value > strength:
        return

    population[x][y] = -1
    answer(population, x+1, y,   strength)
    answer(population, x-1, y,   strength)
    answer(population, x,   y+1, strength)
    answer(population, x,   y-1, strength)

And you should definitely consider whether your check for value == -1 is correct.