percolationv.py

Below is the syntax highlighted version of percolationv.py from §2.4 Case Study: Percolation.

#-----------------------------------------------------------------------
# percolationv.py
#-----------------------------------------------------------------------

import stdarray
import stdio

#-----------------------------------------------------------------------

# isOpen is a matrix that represents the open sites of a system. 
# Compute and return a matrix that represents the full sites of
# that system. For now, consider only vertical percolation.

def flow(isOpen):
    n = len(isOpen)
    isFull = stdarray.create2D(n, n, False)
    for j in range(n):
        isFull[0][j] = isOpen[0][j]
    for i in range(1, n):
        for j in range(n):
            if isOpen[i][j] and isFull[i-1][j]:
                isFull[i][j] = True
    return isFull

#-----------------------------------------------------------------------

# open is matrix that represents the open sites of a system. Return
# True if that system percolates, and False otherwise.

def percolates(isOpen):
    
    # Compute the full sites of the system.
    isFull = flow(isOpen)
    
    # If any site in the bottom row is full, then the system
    # percolates.
    n = len(isFull)
    for j in range(n):
        if isFull[n-1][j]:
            return True
    return False

#-----------------------------------------------------------------------

# Read from standard input a boolean matrix that represents the
# open sites of a system. Write to standard output a boolean
# matrix representing the full sites of the system. Then write
# True if the system percolates and False otherwise.

def main():
    isOpen = stdarray.readBool2D()
    stdarray.write2D(flow(isOpen))
    stdio.writeln(percolates(isOpen))
    
if __name__ == '__main__':
    main()
    
#-----------------------------------------------------------------------

# python percolationv.py < test5.txt
# 5 5
# 0 1 1 0 1 
# 0 0 1 0 1 
# 0 0 0 0 1 
# 0 0 0 0 1 
# 0 0 0 0 1 
# True

# python percolationv.py < test8.txt
# 8 8
# 0 0 1 1 1 0 0 0 
# 0 0 0 1 1 0 0 0 
# 0 0 0 0 0 0 0 0 
# 0 0 0 0 0 0 0 0 
# 0 0 0 0 0 0 0 0 
# 0 0 0 0 0 0 0 0 
# 0 0 0 0 0 0 0 0 
# 0 0 0 0 0 0 0 0 
# False