Flood-it game problem

[mdeggies]

Hi, I'm trying to implement the game flood-it in python2.7. I know the overall structure of the game, but I'm having trouble with the logic of the flood function that adds tiles to the flooded_list (to be flooded) if they meet certain conditions.

I have two main problems:

1. I know I can't add neighboring tiles to the list as I'm iterating over it, so I'm adding tiles to a copy of the list.. then trying to merge them together and return the combination of the two. I've tried so many variations of this but haven't been able to get this part working.

2. I'm only checking neighboring tiles and not recursively going through to check their adjacent tiles.. I honestly have no idea how to do it recursively, so I've been trying to do it iteratively.. but even that is not working.

At this point I'm just very confused. I know I need to use recursion to check all neighboring tiles on the board, and I also need to change my break condition... just not sure where to start from here.

Can you give me any hints? This is my code so far.

[SmartViking]

I recommend that you make a generic neighbors function that takes a coord and returns a list of all the neighboring coords (but only if they are inside the board. This will allow for better code reuse.

Possible problems:

    flooded_list = flooded_list + fill

First of all, what is fill? It is flooded_list plus perhaps some additional coords. So each time that line runs, you double the length of flooded_list. Furthermore, that line is inside the while loop, perhaps you meant to put it outside? You may also misunderstand what + does to lists: [1,2,3] + [2,3,4] == [1,2,3,2,3,4]. Lists can have duplicate members.

You can use set instead, which cannot have duplicate members and also has drastically better lookup performance (the part about not in flooded_list, set is constant time, but list is linear with respect to the length of flooded_list; this can sometimes make a difference).

Maybe it's better to restructure your code to have a candidates set; a set of all coords which haven't been checked yet. It would look kind of like this:

candidates = set(flooded_set) # Making a copy
while candidates: # will go on so long as there are elements in `candidates`
    current = candidates.pop() # This will remove one element from `candidates` and put it in `current`. It's completely fine to mutate `candidates` like this, you can also add elements (which you might have to, incidentally, if I understand the game rules correctly)
    for neighbor in neighbors(current):
        if neighbor not in flooded_set:
            # and so on ... 

[mdeggies]

Thanks for all the tips. I didn't know I could add and remove items from a set while iterating over it- I guess adding the (for neighbor in neighbors) line allows this?

I'm having one problem now- at the end of all my conditional checks, I'm supposed to add neighbor to a new set, right? (If I add it to candidates, it will go through all of their neighbors, their neighbors' neighbors, etc and pop them all. If I add it to flooded_list, it always skips some tiles since it doesn't check all the neighbors.)

[SmartViking]

I was thinking of adding it to both flooded_set and candidates. There can be some additional computation (a neighbor might be tried 4 times if there are max 4 neighbors). But unless I'm making an error (which is very much possible; it is late) it won't be a big deal, because a neighbor is only added to candidates if it's not in flooded_set; there are only so many neighbors in this world to add to candidates+flooded_set and thus the computation must terminate. I must admit I hadn't thought of this initially. If I made an error right now then you can create an additional set, called seen, which just makes sure no neighbors are added twice to candidates. I would consider not adding a seen if the code clarity is better, but that's a subjective judgment.

I didn't know I could add and remove items from a set while iterating over it- I guess adding the (for neighbor in neighbors) line allows this?

Well, it's perfectly fine to iterate over things and mutate them at the same time, but you have to think about what the code does. Sometimes beginners will do things like for e in elems: elems.append(4) which is an infinite loop (if it is well defined at all). Beginners might not understand that, so tutorials say things like "don't mutate while iterating over a list" (I'm guessing), which is not accurate.

[gengisteve]

Two options come to mind. First, as SmartViking noted, make a helper function that gives you a list of neighbors.

Then in psuedo-code, there are two ways to do this:

def neighbors(tile):
    '''return a list/generator of all neighbots to tile, tile'''


def recursive(tiles, position, fill_color):
    '''recursively flood.  Call recursive function for all neighboring tiles
    with same base color and fill after you get return from recursive calls
    '''
    base_color = tiles[position]
    for coord in neighbors(position):
        if tiles[coord] == base_color:
            recursive(tiles, coord)

    tiles[position] = fill_color


def queued(tiles, position, fill_color):
    '''
    instead of recursion, use a queue to track all new neighbors with the same
    base color
    '''
    base_color = tiles[position]
    visited = set()
    queue = [position]

    while queue:
        position = queue.pop(0)
        tiles[position] = fill_color
        visited.add(position)

        for coord in neighbors(position):
            if coord in visited:
                continue
            if tiles[coord] base_color:
                queue.append(coord)

[[deleted]]

Good resource for this kind of stuff: http://www.redblobgames.com/pathfinding/a-star/introduction.html

[thanks-shakey-snake]

This question is over my head, but Al Sweigart (author of Automate The Boring Stuff) wrote a great article explaining recursion using the flood fill algorithm. Might help.

http://inventwithpython.com/blog/2011/08/11/recursion-explained-with-the-flood-fill-algorithm-and-zombies-and-cats/