fork download
copy 
  1. from collections import namedtuple
  2. from random import random
  3. from pprint import pprint as pp
  4.  
  5. Grid = namedtuple('Grid', 'cell, hwall, vwall')
  6.  
  7. M, N, t = 10, 10, 1000
  8.  
  9. class PercolatedException(Exception): pass
  10.  
  11. HVF = [(' .', ' _'), (':', '|'), (' ', '#')]  # Horiz, vert, fill chars
  12.  
  13. def newgrid(p):
  14.     hwall = [[int(random() < p) for m in range(M)] 
  15.              for n in range(N+1)]
  16.     vwall = [[(1 if m in (0, M) else int(random() < p)) for m in range(M+1)] 
  17.              for n in range(N)]
  18.     cell = [[0 for m in range(M)] 
  19.              for n in range(N)]
  20.     return Grid(cell, hwall, vwall)
  21.  
  22. def pgrid(grid, percolated=None):
  23.     cell, hwall, vwall = grid
  24.     h, v, f = HVF
  25.     for n in range(N):
  26.         print('    ' + ''.join(h[hwall[n][m]] for m in range(M)))
  27.         print('%i)  ' % (n % 10) + ''.join(v[vwall[n][m]] + f[cell[n][m] if m < M else 0]
  28.                                           for m in range(M+1))[:-1])
  29.     n = N
  30.     print('    ' + ''.join(h[hwall[n][m]] for m in range(M)))
  31.     if percolated: 
  32.         where = percolated.args[0][0]
  33.         print('!)  ' + '  ' * where + ' ' + f[1])
  34.  
  35. def pour_on_top(grid):
  36.     cell, hwall, vwall = grid
  37.     n = 0
  38.     try:
  39.         for m in range(M):
  40.             if not hwall[n][m]:
  41.                 flood_fill(m, n, cell, hwall, vwall)
  42.     except PercolatedException as ex:
  43.         return ex
  44.     return None
  45.  
  46.  
  47. def flood_fill(m, n, cell, hwall, vwall):
  48.     # fill cell 
  49.     cell[n][m] = 1
  50.     # bottom
  51.     if n < N - 1 and not hwall[n + 1][m] and not cell[n+1][m]:
  52.         flood_fill(m, n+1, cell, hwall, vwall)
  53.     # THE bottom
  54.     elif n == N - 1 and not hwall[n + 1][m]:
  55.         raise PercolatedException((m, n+1))
  56.     # left
  57.     if m and not vwall[n][m] and not cell[n][m - 1]:
  58.         flood_fill(m-1, n, cell, hwall, vwall)
  59.     # right
  60.     if m < M - 1 and not vwall[n][m + 1] and not cell[n][m + 1]:
  61.         flood_fill(m+1, n, cell, hwall, vwall)
  62.     # top
  63.     if n and not hwall[n][m] and not cell[n-1][m]:
  64.         flood_fill(m, n-1, cell, hwall, vwall)
  65.  
  66. if __name__ == '__main__':
  67.     sample_printed = False
  68.     pcount = {}
  69.     for p10 in range(11):
  70.         p = (10 - p10) / 10.0    # count down so sample print is interesting
  71.         pcount[p] = 0
  72.         for tries in range(t):
  73.             grid = newgrid(p)
  74.             percolated = pour_on_top(grid)
  75.             if percolated:
  76.                 pcount[p] += 1
  77.                 if not sample_printed:
  78.                     print('\nSample percolating %i x %i grid' % (M, N))
  79.                     pgrid(grid, percolated)
  80.                     sample_printed = True
  81.     print('\n p: Fraction of %i tries that percolate through' % t )
  82.  
  83.     pp({p:c/float(t) for p, c in pcount.items()})
Success #stdin #stdout 2.07s 12248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Sample percolating 10 x 10 grid
     _ _ _ . _ . . _ _ .
0)  | | : |#| |#:#:#| |#|
     _ _ _ _ _ _ _ _ _ .
1)  | | | | | | : | |#:#|
     _ _ _ _ . _ . _ . _
2)  | : | : | | | | |#: |
     _ _ _ _ _ . _ . . _
3)  | : | : | | : : :#: |
     _ _ . . _ . _ . . .
4)  | | | | | : : | |#| |
     _ _ . _ . _ _ . . .
5)  | : | | | | : | :#| |
     _ _ _ _ _ _ . _ . _
6)  | | | : | : | | |#| |
     . . _ _ _ _ _ _ . .
7)  | : : | | | | | |#| |
     . _ . _ _ _ _ _ . .
8)  | | | : : : : | |#:#|
     _ . _ . _ . . _ _ .
9)  | | | : : | | | : |#|
     _ . . _ _ . _ _ . .
!)                     #

 p: Fraction of 1000 tries that percolate through
{0.0: 1.0,
 0.1: 1.0,
 0.2: 1.0,
 0.3: 0.999,
 0.4: 0.905,
 0.5: 0.427,
 0.6: 0.063,
 0.7: 0.002,
 0.8: 0.0,
 0.9: 0.0,
 1.0: 0.0}
https://ideone.com/ik57yE
language:
Python 3 (python  3.9.5)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!