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, 1000
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()})
ZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgbmFtZWR0dXBsZQpmcm9tIHJhbmRvbSBpbXBvcnQgcmFuZG9tCmZyb20gcHByaW50IGltcG9ydCBwcHJpbnQgYXMgcHAKIApHcmlkID0gbmFtZWR0dXBsZSgnR3JpZCcsICdjZWxsLCBod2FsbCwgdndhbGwnKQogCk0sIE4sIHQgPSAxMCwgMTAsIDEwMDAKIApjbGFzcyBQZXJjb2xhdGVkRXhjZXB0aW9uKEV4Y2VwdGlvbik6IHBhc3MKIApIVkYgPSBbKCcgLicsICcgXycpLCAoJzonLCAnfCcpLCAoJyAnLCAnIycpXSAgIyBIb3JpeiwgdmVydCwgZmlsbCBjaGFycwogCmRlZiBuZXdncmlkKHApOgogICAgaHdhbGwgPSBbW2ludChyYW5kb20oKSA8IHApIGZvciBtIGluIHJhbmdlKE0pXSAKICAgICAgICAgICAgIGZvciBuIGluIHJhbmdlKE4rMSldCiAgICB2d2FsbCA9IFtbKDEgaWYgbSBpbiAoMCwgTSkgZWxzZSBpbnQocmFuZG9tKCkgPCBwKSkgZm9yIG0gaW4gcmFuZ2UoTSsxKV0gCiAgICAgICAgICAgICBmb3IgbiBpbiByYW5nZShOKV0KICAgIGNlbGwgPSBbWzAgZm9yIG0gaW4gcmFuZ2UoTSldIAogICAgICAgICAgICAgZm9yIG4gaW4gcmFuZ2UoTildCiAgICByZXR1cm4gR3JpZChjZWxsLCBod2FsbCwgdndhbGwpCiAKZGVmIHBncmlkKGdyaWQsIHBlcmNvbGF0ZWQ9Tm9uZSk6CiAgICBjZWxsLCBod2FsbCwgdndhbGwgPSBncmlkCiAgICBoLCB2LCBmID0gSFZGCiAgICBmb3IgbiBpbiByYW5nZShOKToKICAgICAgICBwcmludCgnICAgICcgKyAnJy5qb2luKGhbaHdhbGxbbl1bbV1dIGZvciBtIGluIHJhbmdlKE0pKSkKICAgICAgICBwcmludCgnJWkpICAnICUgKG4gJSAxMCkgKyAnJy5qb2luKHZbdndhbGxbbl1bbV1dICsgZltjZWxsW25dW21dIGlmIG0gPCBNIGVsc2UgMF0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZm9yIG0gaW4gcmFuZ2UoTSsxKSlbOi0xXSkKICAgIG4gPSBOCiAgICBwcmludCgnICAgICcgKyAnJy5qb2luKGhbaHdhbGxbbl1bbV1dIGZvciBtIGluIHJhbmdlKE0pKSkKICAgIGlmIHBlcmNvbGF0ZWQ6IAogICAgICAgIHdoZXJlID0gcGVyY29sYXRlZC5hcmdzWzBdWzBdCiAgICAgICAgcHJpbnQoJyEpICAnICsgJyAgJyAqIHdoZXJlICsgJyAnICsgZlsxXSkKIApkZWYgcG91cl9vbl90b3AoZ3JpZCk6CiAgICBjZWxsLCBod2FsbCwgdndhbGwgPSBncmlkCiAgICBuID0gMAogICAgdHJ5OgogICAgICAgIGZvciBtIGluIHJhbmdlKE0pOgogICAgICAgICAgICBpZiBub3QgaHdhbGxbbl1bbV06CiAgICAgICAgICAgICAgICBmbG9vZF9maWxsKG0sIG4sIGNlbGwsIGh3YWxsLCB2d2FsbCkKICAgIGV4Y2VwdCBQZXJjb2xhdGVkRXhjZXB0aW9uIGFzIGV4OgogICAgICAgIHJldHVybiBleAogICAgcmV0dXJuIE5vbmUKIAogCmRlZiBmbG9vZF9maWxsKG0sIG4sIGNlbGwsIGh3YWxsLCB2d2FsbCk6CiAgICAjIGZpbGwgY2VsbCAKICAgIGNlbGxbbl1bbV0gPSAxCiAgICAjIGJvdHRvbQogICAgaWYgbiA8IE4gLSAxIGFuZCBub3QgaHdhbGxbbiArIDFdW21dIGFuZCBub3QgY2VsbFtuKzFdW21dOgogICAgICAgIGZsb29kX2ZpbGwobSwgbisxLCBjZWxsLCBod2FsbCwgdndhbGwpCiAgICAjIFRIRSBib3R0b20KICAgIGVsaWYgbiA9PSBOIC0gMSBhbmQgbm90IGh3YWxsW24gKyAxXVttXToKICAgICAgICByYWlzZSBQZXJjb2xhdGVkRXhjZXB0aW9uKChtLCBuKzEpKQogICAgIyBsZWZ0CiAgICBpZiBtIGFuZCBub3QgdndhbGxbbl1bbV0gYW5kIG5vdCBjZWxsW25dW20gLSAxXToKICAgICAgICBmbG9vZF9maWxsKG0tMSwgbiwgY2VsbCwgaHdhbGwsIHZ3YWxsKQogICAgIyByaWdodAogICAgaWYgbSA8IE0gLSAxIGFuZCBub3QgdndhbGxbbl1bbSArIDFdIGFuZCBub3QgY2VsbFtuXVttICsgMV06CiAgICAgICAgZmxvb2RfZmlsbChtKzEsIG4sIGNlbGwsIGh3YWxsLCB2d2FsbCkKICAgICMgdG9wCiAgICBpZiBuIGFuZCBub3QgaHdhbGxbbl1bbV0gYW5kIG5vdCBjZWxsW24tMV1bbV06CiAgICAgICAgZmxvb2RfZmlsbChtLCBuLTEsIGNlbGwsIGh3YWxsLCB2d2FsbCkKIAppZiBfX25hbWVfXyA9PSAnX19tYWluX18nOgogICAgc2FtcGxlX3ByaW50ZWQgPSBGYWxzZQogICAgcGNvdW50ID0ge30KICAgIGZvciBwMTAgaW4gcmFuZ2UoMTEpOgogICAgICAgIHAgPSAoMTAgLSBwMTApIC8gMTAuMCAgICAjIGNvdW50IGRvd24gc28gc2FtcGxlIHByaW50IGlzIGludGVyZXN0aW5nCiAgICAgICAgcGNvdW50W3BdID0gMAogICAgICAgIGZvciB0cmllcyBpbiByYW5nZSh0KToKICAgICAgICAgICAgZ3JpZCA9IG5ld2dyaWQocCkKICAgICAgICAgICAgcGVyY29sYXRlZCA9IHBvdXJfb25fdG9wKGdyaWQpCiAgICAgICAgICAgIGlmIHBlcmNvbGF0ZWQ6CiAgICAgICAgICAgICAgICBwY291bnRbcF0gKz0gMQogICAgICAgICAgICAgICAgaWYgbm90IHNhbXBsZV9wcmludGVkOgogICAgICAgICAgICAgICAgICAgIHByaW50KCdcblNhbXBsZSBwZXJjb2xhdGluZyAlaSB4ICVpIGdyaWQnICUgKE0sIE4pKQogICAgICAgICAgICAgICAgICAgIHBncmlkKGdyaWQsIHBlcmNvbGF0ZWQpCiAgICAgICAgICAgICAgICAgICAgc2FtcGxlX3ByaW50ZWQgPSBUcnVlCiAgICBwcmludCgnXG4gcDogRnJhY3Rpb24gb2YgJWkgdHJpZXMgdGhhdCBwZXJjb2xhdGUgdGhyb3VnaCcgJSB0ICkKIAogICAgcHAoe3A6Yy9mbG9hdCh0KSBmb3IgcCwgYyBpbiBwY291bnQuaXRlbXMoKX0p