Recursive bug in homework assignment. Looking for advice

Question

I'm taking an intro comp sci course and the current project is recursive. The program reads a text file that has n number of rows and n number of columns of - and I. The program creates a 2D list which is the grid used for the program. The user is then prompted for a point on the grid (row, col) and if the user's point is a - the point is changed to a @ and then I have to recursively fill in the first available space with a @ by checking the space above, left, right, below and filling the first space available. My recursive function is:

def fillWithAt(grid, the_row, the_col):

    if grid[the_row][the_col] == '-':
        grid[the_row][the_col] = '@'
        printFile(grid)

        if the_row != 0:
            if grid[the_row - 1][the_col] == '-':
                fillWithAt(grid, the_row - 1, the_col)

        if the_col != 0:
            if grid[the_row][the_col - 1] == '-':
                fillWithAt(grid, the_row, the_col - 1)

        if the_col != (len(grid[the_row]) - 1):
            if grid[the_row][the_col + 1] == '-':
                fillWithAt(grid, the_row, the_col + 1)

        if the_row != (len(grid) - 1):
            if grid[the_row + 1][the_col] == '-':
                fillWithAt(grid, the_row + 1, the_col)

    else:
        printFile(grid)

grid is the 2D list, the_row is the user's row, and the_col is the user's column. The program works almost perfectly, but it breaks down when it gets to the last two columns. I can't figure out how to copy the output into this because every time I try it is stripped of whitespace and means nothing, so I'll try to explain.

The program works fine until I hit the last two rows. The program finds an empty space to the right and for some reason occupies the next two spaces to the right instead of just one space. After that the program reads the spaces around the current point incorrectly. At the end of the day the program still completes the task, but I'm curious as to why the bug occurs.

I'm not looking for any answers, but advice. If anyone can see any reason as to why this might happen, I'd appreciate any info. I also love feedback/constructive criticism.

EDIT: Here are a few steps into the recursive process. The current space first checks it's above neighbor for a '-'. If a dash is found then that spaces is occupied, if not the left neighbor is checked, and then the right, and finally below.

- - - - - I I - - - - - - - -
- - - - I - - I I - - - - - -
- - - - I - - - - I I I I - -
- - - I - - - - - - - - I I I
- - I - - - - - - - - - - - -
- - - I - - - - - - - - I I I
- - - I - - I I I - - - I - -
- - - I - - I - - I - I - - -
- - - I I I I - - - I - - - -
- - - - - - - - - - - - - - -

@ - - - - I I - - - - - - - -
- - - - I - - I I - - - - - -
- - - - I - - - - I I I I - -
- - - I - - - - - - - - I I I
- - I - - - - - - - - - - - -
- - - I - - - - - - - - I I I
- - - I - - I I I - - - I - -
- - - I - - I - - I - I - - -
- - - I I I I - - - I - - - -
- - - - - - - - - - - - - - -

@ @ - - - I I - - - - - - - -
- - - - I - - I I - - - - - -
- - - - I - - - - I I I I - -
- - - I - - - - - - - - I I I
- - I - - - - - - - - - - - -
- - - I - - - - - - - - I I I
- - - I - - I I I - - - I - -
- - - I - - I - - I - I - - -
- - - I I I I - - - I - - - -
- - - - - - - - - - - - - - -

@ @ @ - - I I - - - - - - - -
- - - - I - - I I - - - - - -
- - - - I - - - - I I I I - -
- - - I - - - - - - - - I I I
- - I - - - - - - - - - - - -
- - - I - - - - - - - - I I I
- - - I - - I I I - - - I - -
- - - I - - I - - I - I - - -
- - - I I I I - - - I - - - -
- - - - - - - - - - - - - - -

@ @ @ @ - I I - - - - - - - -
- - - - I - - I I - - - - - -
- - - - I - - - - I I I I - -
- - - I - - - - - - - - I I I
- - I - - - - - - - - - - - -
- - - I - - - - - - - - I I I
- - - I - - I I I - - - I - -
- - - I - - I - - I - I - - -
- - - I I I I - - - I - - - -
- - - - - - - - - - - - - - -

@ @ @ @ @ I I - - - - - - - -
- - - - I - - I I - - - - - -
- - - - I - - - - I I I I - -
- - - I - - - - - - - - I I I
- - I - - - - - - - - - - - -
- - - I - - - - - - - - I I I
- - - I - - I I I - - - I - -
- - - I - - I - - I - I - - -
- - - I I I I - - - I - - - -
- - - - - - - - - - - - - - -

@ @ @ @ @ I I - - - - - - - -
- - - @ I - - I I - - - - - -
- - - - I - - - - I I I I - -
- - - I - - - - - - - - I I I
- - I - - - - - - - - - - - -
- - - I - - - - - - - - I I I
- - - I - - I I I - - - I - -
- - - I - - I - - I - I - - -
- - - I I I I - - - I - - - -
- - - - - - - - - - - - - - -

@ @ @ @ @ I I - - - - - - - -
- - @ @ I - - I I - - - - - -
- - - - I - - - - I I I I - -
- - - I - - - - - - - - I I I
- - I - - - - - - - - - - - -
- - - I - - - - - - - - I I I
- - - I - - I I I - - - I - -
- - - I - - I - - I - I - - -
- - - I I I I - - - I - - - -
- - - - - - - - - - - - - - -

@ @ @ @ @ I I - - - - - - - -
- @ @ @ I - - I I - - - - - -
- - - - I - - - - I I I I - -
- - - I - - - - - - - - I I I
- - I - - - - - - - - - - - -
- - - I - - - - - - - - I I I
- - - I - - I I I - - - I - -
- - - I - - I - - I - I - - -
- - - I I I I - - - I - - - -
- - - - - - - - - - - - - - -

@ @ @ @ @ I I - - - - - - - -
@ @ @ @ I - - I I - - - - - -
- - - - I - - - - I I I I - -
- - - I - - - - - - - - I I I
- - I - - - - - - - - - - - -
- - - I - - - - - - - - I I I
- - - I - - I I I - - - I - -
- - - I - - I - - I - I - - -
- - - I I I I - - - I - - - -
- - - - - - - - - - - - - - -

@ @ @ @ @ I I - - - - - - - -
@ @ @ @ I - - I I - - - - - -
@ - - - I - - - - I I I I - -
- - - I - - - - - - - - I I I
- - I - - - - - - - - - - - -
- - - I - - - - - - - - I I I
- - - I - - I I I - - - I - -
- - - I - - I - - I - I - - -
- - - I I I I - - - I - - - -
- - - - - - - - - - - - - - -

The program works as expected until this point:

@ @ @ @ @ I I - - - - - - - -
@ @ @ @ I - - I I - - - - - -
@ @ @ @ I - - - - I I I I - -
@ @ @ I - - - - - - - - I I I
@ @ I - - - - - - - - - - - -
@ @ @ I - - - - - - - - I I I
@ @ @ I - - I I I - - - I - -
@ @ @ I - - I @ @ I - I @ - -
@ @ @ I I I I @ @ @ I @ @ - -
@ @ @ @ @ @ @ @ @ @ @ @ - - -

@ @ @ @ @ I I - - - - - - - -
@ @ @ @ I - - I I - - - - - -
@ @ @ @ I - - - - I I I I - -
@ @ @ I - - - - - - - - I I I
@ @ I - - - - - - - - - - - -
@ @ @ I - - - - - - - - I I I
@ @ @ I - - I I I - - - I - -
@ @ @ I - - I @ @ I - I @ @ @
@ @ @ I I I I @ @ @ I @ @ - -
@ @ @ @ @ @ @ @ @ @ @ @ - - -

@ @ @ @ @ I I - - - - - - - -
@ @ @ @ I - - I I - - - - - -
@ @ @ @ I - - - - I I I I - -
@ @ @ I - - - - - - - - I I I
@ @ I - - - - - - - - - - - -
@ @ @ I - - - - - - - - I I I
@ @ @ I - - I I I - - - I @ @
@ @ @ I - - I @ @ I - I @ @ @
@ @ @ I I I I @ @ @ I @ @ - -
@ @ @ @ @ @ @ @ @ @ @ @ - - -

For some reason it occupies two spaces to the right instead of one, and then on the next move it occupies both spaces above the two previously occupied spaces.

My code to generate the grid is:

def get2DList(fo):
    full_list = []

    for line in fo:
        full_list.append(list(line.strip()))

    fo.close()
    return full_list

fo is a file

EDIT: I have solved my issue thanks to @Blckknght giving me the idea that my printFile() function was the cause. It's working perfectly now. Thank you to everyone that helped!

Answer 1

I was trying to figure out the problem and I re-wrote your program. Then I noticed that you solved your problem, but it wasn't obvious because you don't have an accepted answer. I suggest that @Blckknght should post his comment "I'm wondering if there's an output bug" as an answer and you should accept it. Then people will know for sure that this problem is solved.

You might as well look over my version and see what you think of it.

It's possible that I used some stuff in Python that you haven't learned yet. If so, just ignore it for now I guess.

Changes:

• I added a string to init a grid, and a function that makes a grid from the string

• I changed the_row to just row and likewise for the_col. The prefix the_ adds nothing but visual noise.

• I made an outer function that, one time, does sanity checks on the input grid, and then an inner function that just does the recursive flood fill.

• I just re-wrote print_grid() to use a for loop that loops over the grid directly, rather than using range(). That's cleaner code and runs a little bit faster.

• I printed out the grid using ''.join(row) which doesn't separate the grid characters with spaces. This is different from what you did. To get the spaces, simply do this: ' '.join(row) In other words, join the row using spaces rather than an empty string.

• I wrote this to run unchnaged on either Python 2.x or Python 3.x. The only tricky thing is that I had to call 'print('') instead of just print(), because in Python 2.x print() will actually print () rather than nothing. (This is because in Python 2.x, print is a statement rather than a function, and it evaluates the () as an empty tuple, and prints the empty tuple as ()!)

• I changed all names to match PEP8 standard. (But if you are taking a class, and the teacher wants you to use camelCase names, do what the teacher says.)

http://legacy.python.org/dev/peps/pep-0008/

# grid flood fill program
# http://en.wikipedia.org/wiki/Flood_fill

s_grid = """\
-----II--------
----I--II------
----I----IIII--
---I--------III
--I------------
---I--------III
---I--III---I--
---I--I--I-I---
---IIII---I----
---------------
"""

def grid_from_str(s):
    s = s.strip()
    rows = s.split('\n')
    return [list(row) for row in rows]

def print_grid(grid):
    for row in grid:
        print(''.join(row))
    print('')


def flood_fill(grid, row, col, blank='-', fill='@'):
    row_max = len(grid)
    col_max = len(grid[row])

    if grid[row][col] != blank:
        print("skipping: row {}, col {}".format(row, col))
        return

    grid[row][col] = fill
    print_grid(grid)

    if row > 0:
        if grid[row - 1][col] == blank:
            flood_fill(grid, row - 1, col)

    if col > 0:
        if grid[row][col - 1] == blank:
            flood_fill(grid, row, col - 1)

    if col < (len(grid[row]) - 1):
        if grid[row][col + 1] == blank:
            flood_fill(grid, row, col + 1)

    if row < (len(grid) - 1):
        if grid[row + 1][col] == blank:
            flood_fill(grid, row + 1, col)


def fill_grid_with_at(grid, row, col):
    row_max = len(grid)
    col_max = len(grid[0])

    assert row_max > 0 and col_max > 0

    # make sure grid is regular
    assert all(col_max == len(row) for row in grid)

    # make sure grid only contains legal stuff
    assert all(ch in ('-', 'I', '@') for row in grid for ch in row)

    flood_fill(grid, row, col)


grid = grid_from_str(s_grid)
fill_grid_with_at(grid, 0, 0)