58 lines
1.3 KiB
Python
58 lines
1.3 KiB
Python
import sys
|
|
|
|
# Can handle 10k sand grains in 0.4s.
|
|
|
|
|
|
def show_terrain(terrain):
|
|
width = len(terrain)
|
|
for x in range(width):
|
|
for y in range(width):
|
|
print(" ·●⬤#"[min(4, terrain[x][y])], end="")
|
|
print()
|
|
|
|
|
|
def topple(terrain, x, y):
|
|
div, terrain[x][y] = divmod(terrain[x][y], 4)
|
|
|
|
terrain[x - 1][y] += div
|
|
|
|
if terrain[x-1][y] >= 4:
|
|
topple(terrain, x - 1, y)
|
|
|
|
terrain[x + 1][y] += div
|
|
terrain[x][y - 1] += div
|
|
terrain[x][y + 1] += div
|
|
|
|
|
|
|
|
def apply_gravity(terrain):
|
|
"""
|
|
$ python -m pyperf timeit --fast -s 'from examples.sandpile3 import main' 'main(10_000, False)'
|
|
...........
|
|
Mean +- std dev: 2.02 sec +- 0.04 sec
|
|
|
|
"""
|
|
width = len(terrain)
|
|
while True:
|
|
did_someting = False
|
|
for x in range(width):
|
|
for y in range(width):
|
|
if terrain[x][y] >= 4:
|
|
topple(terrain, x, y)
|
|
did_someting = True
|
|
if not did_someting:
|
|
return
|
|
|
|
|
|
def main(height, show=True):
|
|
width = int(height ** .5) + 1
|
|
terrain = [[0] * width for _ in range(width)]
|
|
terrain[width // 2][width // 2] = height
|
|
apply_gravity(terrain)
|
|
if show:
|
|
show_terrain(terrain)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main(int(sys.argv[1]))
|