# CS 190C LAB 7: Friday, February 27, 2009

## In-Lab Problem

Your task is to implement a simple, vertical percolation algorithm. In vertical percolation, you start at the top of the grid and check whether there exists a column allowing flow to the bottom (which does not include left or right flow). In other words, a grid percolates vertically if there is a column of zeroes in the grid.

The definition of `vertical_percolation()` is already given to you. It is similar to the other two functions. It takes in a required argument that represents the grid, and an optional argument that determines whether or not you should draw the grid using `visualize()`. Also as in the project, you should return both the flow grid AND whether or not the grid percolates (to return two variables x and y, simply use “return x, y”).

Note that your flow grid may differ based on your implementation. For example, you may decide to stop once a column reaches the bottom of the grid, rather than testing every single column in the grid.

The given code for the main function lets you load a grid to test fixed cases. You can use these three files as starting points: empty.txt no_perc.txt x.txt.

## Solution

```from percolation_provided import *
from visual import rate

def vertical_percolation(input_grid, trace=False):
size = len(input_grid)
flow_grid = grid(size, -1)

for col in xrange(size):
# Initialize two variables, row and flow_blocked for the while loop.
# "row" simply represents the row of the grid; flow_blocked determines
# if we hit a grid cell in input_grid that does not allow flow. If we
# do, we set flow_blocked to True and the while loop will exit.
row = 0
flow_blocked = False
while row < size and not flow_blocked:
if input_grid[row][col] == 0:
flow_grid[row][col] = '*'
row += 1
# Visualize the grid and pause for 0.2 seconds (1/5)
if trace:
visualize(flow_grid, input_grid)
rate(5)
else:
flow_blocked = True

# If our row variable has iterated up to be the same value as the size
# of our grid, then we've percolated and can return right now. Otherwise
# we must keep looking in the other columns.
if size == row:
return flow_grid, True

# We've exhausted all columns and nothing has returned so far, so the grid
# doesn't percolate.
return flow_grid, False

if __name__ == '__main__':
input_grid = readgrid(raw_input('Enter grid filename: '))
flow_grid, percolates = vertical_percolation(input_grid, True)
if percolates:
print 'The grid percolates'
else:
print 'The grid does not percolate'```        