84 lines
2.6 KiB
Python
84 lines
2.6 KiB
Python
from collections import namedtuple
|
|
from random import random
|
|
from pprint import pprint as pp
|
|
|
|
Grid = namedtuple('Grid', 'cell, hwall, vwall')
|
|
|
|
M, N, t = 10, 10, 100
|
|
|
|
class PercolatedException(Exception): pass
|
|
|
|
HVF = [(' .', ' _'), (':', '|'), (' ', '#')] # Horiz, vert, fill chars
|
|
|
|
def newgrid(p):
|
|
hwall = [[int(random() < p) for m in range(M)]
|
|
for n in range(N+1)]
|
|
vwall = [[(1 if m in (0, M) else int(random() < p)) for m in range(M+1)]
|
|
for n in range(N)]
|
|
cell = [[0 for m in range(M)]
|
|
for n in range(N)]
|
|
return Grid(cell, hwall, vwall)
|
|
|
|
def pgrid(grid, percolated=None):
|
|
cell, hwall, vwall = grid
|
|
h, v, f = HVF
|
|
for n in range(N):
|
|
print(' ' + ''.join(h[hwall[n][m]] for m in range(M)))
|
|
print('%i) ' % (n % 10) + ''.join(v[vwall[n][m]] + f[cell[n][m] if m < M else 0]
|
|
for m in range(M+1))[:-1])
|
|
n = N
|
|
print(' ' + ''.join(h[hwall[n][m]] for m in range(M)))
|
|
if percolated:
|
|
where = percolated.args[0][0]
|
|
print('!) ' + ' ' * where + ' ' + f[1])
|
|
|
|
def pour_on_top(grid):
|
|
cell, hwall, vwall = grid
|
|
n = 0
|
|
try:
|
|
for m in range(M):
|
|
if not hwall[n][m]:
|
|
flood_fill(m, n, cell, hwall, vwall)
|
|
except PercolatedException as ex:
|
|
return ex
|
|
return None
|
|
|
|
|
|
def flood_fill(m, n, cell, hwall, vwall):
|
|
# fill cell
|
|
cell[n][m] = 1
|
|
# bottom
|
|
if n < N - 1 and not hwall[n + 1][m] and not cell[n+1][m]:
|
|
flood_fill(m, n+1, cell, hwall, vwall)
|
|
# THE bottom
|
|
elif n == N - 1 and not hwall[n + 1][m]:
|
|
raise PercolatedException((m, n+1))
|
|
# left
|
|
if m and not vwall[n][m] and not cell[n][m - 1]:
|
|
flood_fill(m-1, n, cell, hwall, vwall)
|
|
# right
|
|
if m < M - 1 and not vwall[n][m + 1] and not cell[n][m + 1]:
|
|
flood_fill(m+1, n, cell, hwall, vwall)
|
|
# top
|
|
if n and not hwall[n][m] and not cell[n-1][m]:
|
|
flood_fill(m, n-1, cell, hwall, vwall)
|
|
|
|
if __name__ == '__main__':
|
|
sample_printed = False
|
|
pcount = {}
|
|
for p10 in range(11):
|
|
p = (10 - p10) / 10.0 # count down so sample print is interesting
|
|
pcount[p] = 0
|
|
for tries in range(t):
|
|
grid = newgrid(p)
|
|
percolated = pour_on_top(grid)
|
|
if percolated:
|
|
pcount[p] += 1
|
|
if not sample_printed:
|
|
print('\nSample percolating %i x %i grid' % (M, N))
|
|
pgrid(grid, percolated)
|
|
sample_printed = True
|
|
print('\n p: Fraction of %i tries that percolate through' % t )
|
|
|
|
pp({p:c/float(t) for p, c in pcount.items()})
|