Strict Standards: Declaration of Doku_Renderer_metadata::table_open() should be compatible with Doku_Renderer::table_open($maxcols = NULL, $numrows = NULL, $pos = NULL) in /home2/cp-wiki/htdocs/inc/parser/metadata.php on line 480

Strict Standards: Declaration of Doku_Renderer_metadata::table_close() should be compatible with Doku_Renderer::table_close($pos = NULL) in /home2/cp-wiki/htdocs/inc/parser/metadata.php on line 480

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

In-Lab Problem

Download the following files: and

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.


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)
                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'
        print 'The grid does not percolate'
cs190c/lab7_09.txt · Last modified: 2009/03/01 18:03 by tang
Recent changes RSS feed Creative Commons License Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki