Recursive error in homework assignment. I am looking for advice

Question

I take intro comp sci, and the current project is recursive. The program reads a text file with the number of rows and the number of columns - and I The program creates a 2D list which is the grid used for the program. Then the user is prompted to indicate a point in the grid (row, column), and if the user's point is - , the point changes to @ , and then I have to recursively fill the first available space with @ , checking the space at the top, left, right, bottom and filling in the first available space. My recursive function:

 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 a 2D list, the_row is the user row, and the_col is the user column. The program works almost perfectly, but it breaks when it falls into the last two columns. I can’t figure out how to copy the output to this because every time I try, it is blank and doesn't mean anything, so I’ll try to explain.

The program runs fine until I hit the last two lines. The program finds an empty space on the right and for some reason takes the following two spaces on the right, and not just one space. After that, the program incorrectly reads spaces around the current point. At the end of the day, the program still performs the task, but I am curious why the error occurs.

I am not looking for any answers, but advice. If anyone can understand why this could happen, I will be grateful for any information. I also like feedback / constructive criticism.

EDIT: Here are a few steps in a recursive process. The current space first checks it over the neighbor for '-'. If a dash is found, then the spaces are occupied, if the left neighbor is not marked, then the right one, and finally lower.

 - - - - - II - - - - - - - - - - - - I - - II - - - - - - - - - - I - - - - IIII - - - - - I - - - - - - - - III - - I - - - - - - - - - - - - - - - I - - - - - - - - III - - - I - - III - - - I - - - - - I - - I - - I - I - - - - - - IIII - - - I - - - - - - - - - - - - - - - - - - - @ - - - - II - - - - - - - - - - - - I - - II - - - - - - - - - - I - - - - IIII - - - - - I - - - - - - - - III - - I - - - - - - - - - - - - - - - I - - - - - - - - III - - - I - - III - - - I - - - - - I - - I - - I - I - - - - - - IIII - - - I - - - - - - - - - - - - - - - - - - - @ @ - - - II - - - - - - - - - - - - I - - II - - - - - - - - - - I - - - - IIII - - - - - I - - - - - - - - III - - I - - - - - - - - - - - - - - - I - - - - - - - - III - - - I - - III - - - I - - - - - I - - I - - I - I - - - - - - IIII - - - I - - - - - - - - - - - - - - - - - - - @ @ @ - - II - - - - - - - - - - - - I - - II - - - - - - - - - - I - - - - IIII - - - - - I - - - - - - - - III - - I - - - - - - - - - - - - - - - I - - - - - - - - III - - - I - - III - - - I - - - - - I - - I - - I - I - - - - - - IIII - - - I - - - - - - - - - - - - - - - - - - - @ @ @ @ - II - - - - - - - - - - - - I - - II - - - - - - - - - - I - - - - IIII - - - - - I - - - - - - - - III - - I - - - - - - - - - - - - - - - I - - - - - - - - III - - - I - - III - - - I - - - - - I - - I - - I - I - - - - - - IIII - - - I - - - - - - - - - - - - - - - - - - - @ @ @ @ @ II - - - - - - - - - - - - I - - II - - - - - - - - - - I - - - - IIII - - - - - I - - - - - - - - III - - I - - - - - - - - - - - - - - - I - - - - - - - - III - - - I - - III - - - I - - - - - I - - I - - I - I - - - - - - IIII - - - I - - - - - - - - - - - - - - - - - - - @ @ @ @ @ II - - - - - - - - - - - @ I - - II - - - - - - - - - - I - - - - IIII - - - - - I - - - - - - - - III - - I - - - - - - - - - - - - - - - I - - - - - - - - III - - - I - - III - - - I - - - - - I - - I - - I - I - - - - - - IIII - - - I - - - - - - - - - - - - - - - - - - - @ @ @ @ @ II - - - - - - - - - - @ @ I - - II - - - - - - - - - - I - - - - IIII - - - - - I - - - - - - - - III - - I - - - - - - - - - - - - - - - I - - - - - - - - III - - - I - - III - - - I - - - - - I - - I - - I - I - - - - - - IIII - - - I - - - - - - - - - - - - - - - - - - - @ @ @ @ @ II - - - - - - - - - @ @ @ I - - II - - - - - - - - - - I - - - - IIII - - - - - I - - - - - - - - III - - I - - - - - - - - - - - - - - - I - - - - - - - - III - - - I - - III - - - I - - - - - I - - I - - I - I - - - - - - IIII - - - I - - - - - - - - - - - - - - - - - - - @ @ @ @ @ II - - - - - - - - @ @ @ @ I - - II - - - - - - - - - - I - - - - IIII - - - - - I - - - - - - - - III - - I - - - - - - - - - - - - - - - I - - - - - - - - III - - - I - - III - - - I - - - - - I - - I - - I - I - - - - - - IIII - - - I - - - - - - - - - - - - - - - - - - - @ @ @ @ @ II - - - - - - - - @ @ @ @ I - - II - - - - - - @ - - - I - - - - IIII - - - - - I - - - - - - - - III - - I - - - - - - - - - - - - - - - I - - - - - - - - III - - - I - - III - - - I - - - - - I - - I - - I - I - - - - - - IIII - - - I - - - - - - - - - - - - - - - - - - - 

The program works as expected up to this point:

 @ @ @ @ @ II - - - - - - - - @ @ @ @ I - - II - - - - - - @ @ @ @ I - - - - IIII - - @ @ @ I - - - - - - - - III @ @ I - - - - - - - - - - - - @ @ @ I - - - - - - - - III @ @ @ I - - III - - - I - - @ @ @ I - - I @ @ I - I @ - - @ @ @ IIII @ @ @ I @ @ - - @ @ @ @ @ @ @ @ @ @ @ @ - - - @ @ @ @ @ II - - - - - - - - @ @ @ @ I - - II - - - - - - @ @ @ @ I - - - - IIII - - @ @ @ I - - - - - - - - III @ @ I - - - - - - - - - - - - @ @ @ I - - - - - - - - III @ @ @ I - - III - - - I - - @ @ @ I - - I @ @ I - I @ @ @ @ @ @ IIII @ @ @ I @ @ - - @ @ @ @ @ @ @ @ @ @ @ @ - - - @ @ @ @ @ II - - - - - - - - @ @ @ @ I - - II - - - - - - @ @ @ @ I - - - - IIII - - @ @ @ I - - - - - - - - III @ @ I - - - - - - - - - - - - @ @ @ I - - - - - - - - III @ @ @ I - - III - - - I @ @ @ @ @ I - - I @ @ I - I @ @ @ @ @ @ IIII @ @ @ I @ @ - - @ @ @ @ @ @ @ @ @ @ @ @ - - - 

For some reason, it occupies two spaces on the right, not one, and then on the next move it occupies both spaces over two previously occupied spaces.

My grid code 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 solved the problem thanks to @Blckknght giving me an idea that my printFile () function was the reason. Now it works great. Thanks to everyone who helped!

Answer 1

I made a careless mistake when I first started to perform functions. So my printFile () was

 def printFile(current_list): for i in current_list: for j in i[:-1]: print(j, end = ' ') print(j) print() 

My reasoning about this was when I first tried to use only for j in i: print(j, end = ' ') The problem with this would be to print unwanted space before each new line, and this was the first thing that came to mind.

Now I see that printing j outside the for loop for the last column was an error, because j was still equal to the previous iteration of the for loop, forcing the last 2 columns to act the same (I “Beginner, please don't laugh at me.” My new the function is as follows:

 def printFile(current_list): for i in current_list: print(' '.join(i)) print() 

Now everything works as expected. Thanks again to everyone who helped.

Answer 2

I tried to find out the problem and I rewrote your program. Then I noticed that you solved your problem, but that was not obvious, because you have no accepted answer. I suggest that @Blckknght post his comment “I wonder if there is an output error” as an answer, and you should accept it. Then people will know for sure that this problem is solved.

You can also view my version and see what you think about it.

Perhaps I used some things in Python that you have not yet learned. If so, just ignore him now, I think.

Changes:

• I added a line to initialize the grid and a function that creates a grid from the line

• I changed the_row to row as well as the_col . The the_ prefix adds nothing but visual noise.

• I made an external function that once validates the input grid, and then an internal function that simply performs a recursive fill fill.

• I simply rewrote print_grid() to use a for loop that traverses the grid directly, instead of using range() . This code is clean and a little faster.

• I printed the grid using ''.join(row) , which does not separate grid characters with spaces. This is different than what you did. To get spaces, just do the following: ' '.join(row) In other words, ' '.join(row) string using spaces, not an empty string.

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

• I changed all the names according to the PEP8 standard. (But if you are in class and the teacher wants you to use the 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--II--- ---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)