The seventh episode of our lecture on program design is now online. In this one, we actually assemble a complete version of the program step by step using the pieces designed earlier. The final program still has one nasty bug, though, and I'll award a Software Carpentry mug to the first person who can find it (source code attached to this post). For reference, the first six episodes are listed below, along with another link to this one.
- The Grid
- Finding Neighbors
- Resolving Ties
- Assembling the Program
#!/usr/bin/env python '''Invasion Percolation Simulation usage: invperc.py grid_size value_range random_seed grid_size: the width/height of the grid must be a positive odd integer value_range: number of distinct values in grid must be a positive integer values will be selected randomly in 1..value_range random_seed: random number generation seed must be a positive integer ''' import sys, random FILLED = -1 # Used to mark filled cells. def fail(msg): print >> sys.stderr, msg sys.exit(1) def create_random_grid(N, Z): '''Return an NxN grid of random values in 1..Z. Assumes the RNG has already been seeded.''' assert N > 0, 'Grid size must be positive' assert N%2 == 1, 'Grid size must be odd' grid =  for x in range(N): grid.append() for y in range(N): grid[-1].append(random.randint(1, Z)) return grid def mark_filled(grid, x, y): '''Mark a grid cell as filled.''' assert 0 <= x < len(grid), \ 'X coordinate out of range (%d vs %d)' % \ (x, len(grid)) assert 0 <= y < len(grid), \ 'Y coordinate out of range (%d vs %d)' % \ (y, len(grid)) grid[x][y] = FILLED def is_candidate(grid, x, y): '''Is a cell a candidate for filling?''' N = len(grid) return (x > 0) and (grid[x-1][y] == FILLED) \ or (x < N-1) and (grid[x+1][y] == FILLED) \ or (y > 0) and (grid[x][y-1] == FILLED) \ or (y < N-1) and (grid[x][y+1] == FILLED) def find_candidates(grid): '''Find low-valued neighbor cells.''' N = len(grid) min_val = sys.maxint min_set = set() for x in range(N): for y in range(N): if is_candidate(grid, x, y): if grid[x][y] == min_val: min_set.add((x, y)) elif grid[x][y] < min_val: min_val = grid[x][y] min_set = set([(x, y)]) return min_set def fill_grid(grid): '''Fill an NxN grid until filled region hits boundary.''' N, num_filled = len(grid), 0 while True: candidates = find_candidates(grid) assert candidates, 'No fillable cells found!' x, y = random.choice(list(candidates)) mark_filled(grid, x, y) num_filled += 1 if x in (0, N-1) or y in (0, N-1): break return num_filled # Main driver. if __name__ == '__main__': # Get parameters from command line. arguments = sys.argv[1:] try: grid_size = int(arguments) value_range = int(arguments) random_seed = int(arguments) except IndexError: fail('Expected 3 arguments, got %d' % len(arguments)) except ValueError: fail('Expected integer arguments, got %s' % str(arguments)) # Run simulation. random.seed(random_seed) grid = create_random_grid(grid_size, value_range) mark_filled(grid, grid_size/2, grid_size/2) num_filled_cells = fill_grid(grid) + 1 print '%d cells filled' % num_filled_cells