fork download
copy 
  1. # -*- coding: utf-8 -*-
  2. from collections import defaultdict
  3. from itertools import product
  4. from PIL import Image, ImageFont, ImageDraw
  5.  
  6. FALL = '|'
  7. RIVER = '~'
  8. POOL = 'N'
  9.  
  10. SOURCE = 'x'
  11. SOURCE_AND_FALL = '*'
  12. SOURCE_AND_RIVER = 'X'
  13. SOURCE_AND_POOL = '%'
  14.  
  15. BLOCK = '#'
  16. LRAMP = '/'
  17. RRAMP = '\\'
  18. SPACE = ' '
  19.  
  20. LRAMP_AND_FALL = 'd'
  21. RRAMP_AND_FALL = 'b'
  22. LRAMP_AND_RIVER = '}'
  23. RRAMP_AND_RIVER = '{'
  24. LRAMP_AND_POOL = ']'
  25. RRAMP_AND_POOL = '['
  26.  
  27. HERE = (0,0)
  28. DOWN = (1,0)
  29. LEFT = (0,-1)
  30. RIGHT = (0,1)
  31. UP = (-1,0)
  32. ORDINALS = [DOWN,LEFT,RIGHT,UP]
  33.  
  34. gridStr = """\
  35. #x#
  36. # #
  37. # #
  38. # #
  39. # #
  40. ###"""
  41. gridStr = """\
  42. # x #
  43. #   #
  44. #   #
  45. #   #
  46. #   #
  47. #####"""
  48. gridStr = """\
  49.  x #  
  50. #  # #
  51. #  # #
  52. #  # #
  53. #  # #
  54. #  # #
  55. #  # #
  56. #  # #
  57. #  # #
  58. #  # #
  59. #    #
  60. ######"""
  61. gridStr = """\
  62.   x  
  63. #  / 
  64. #####"""
  65. gridStr = """\
  66.  x #  
  67. #  # #
  68. #  # #
  69. #  # #
  70. #    #
  71. ######"""
  72. gridStr = """\
  73.                     x  
  74.  
  75.  
  76. #                   # #
  77. #                   # #
  78. #                   # #
  79. #                   # #
  80. #                   # #
  81. #######################"""
  82. gridStr = """\
  83.   x   
  84. #   / 
  85. ##### 
  86. #   # 
  87. # #  /
  88. ###\/#"""
  89. gridStr = """\
  90.    x      
  91. #        #
  92. #        #
  93. #        #
  94. #### #####
  95. #### #####
  96. #### #####
  97. ##########"""
  98.  
  99. FRAMES = 100
  100.  
  101. # The capacity of a ramp cell.
  102. HALF_CAPACITY = 50
  103. # The capacity of an empty cell.
  104. MAX_CAPACITY = 2*HALF_CAPACITY
  105. # The rate of flow in from a source.
  106. SOURCE_RATE = HALF_CAPACITY
  107. # The maximum rate of flow between two cells.
  108. MAX_FLOW = MAX_CAPACITY
  109. # The ratio extra a cell can hold if the cell above is full (assuming both have same capacity)
  110. COMPRESSABILITY = 0.25
  111.  
  112. SPACE_THRESHHOLD = HALF_CAPACITY / 2
  113. RIVER_THRESHHOLD = HALF_CAPACITY + HALF_CAPACITY / 2
  114.  
  115. def isSource(cell):
  116.     return cell in [SOURCE, SOURCE_AND_FALL, SOURCE_AND_RIVER, SOURCE_AND_POOL]
  117.  
  118. def isLRamp(cell):
  119.     return cell in [LRAMP, LRAMP_AND_FALL, LRAMP_AND_RIVER, LRAMP_AND_POOL]
  120. def isRRamp(cell):
  121.     return cell in [RRAMP, RRAMP_AND_FALL, RRAMP_AND_RIVER, RRAMP_AND_POOL]
  122. def isRamp(cell):
  123.     return isLRamp(cell) or isRRamp(cell)
  124.  
  125. def findBackground(cell):
  126.     if cell in [SPACE, FALL, RIVER, POOL, SOURCE]:
  127.         return SPACE
  128.     elif cell in [BLOCK]:
  129.         return BLOCK
  130.     elif isLRamp(cell):
  131.         return LRAMP
  132.     elif isRRamp(cell):
  133.         return RRAMP
  134.     raise Exception
  135.  
  136. class WaterType:
  137.     FALL = 1
  138.     SETTLED = 2
  139.  
  140. class Cell:
  141.     def __init__(self, background, isSource):
  142.         self.background = background
  143.         self.isSource = isSource
  144.         self.water = 0
  145.         self.waterType = WaterType.FALL
  146.     def getCapacity(self):
  147.         return (0 if self.background == BLOCK else (HALF_CAPACITY if isRamp(self.background) else MAX_CAPACITY))
  148.     def copyCell(self, cell):
  149.         self.background = cell.background
  150.         self.isSource = cell.isSource
  151.         # Include any water already here
  152.         self.water += cell.water
  153.         self.waterType = cell.waterType
  154.     def updateType(self, cellBelow):
  155.         if self.water == 0:
  156.             self.waterType = WaterType.SETTLED
  157.         elif self.water == self.getCapacity():
  158.             # If a completely saturated block of water is falling it should still look full.
  159.             self.waterType = WaterType.SETTLED
  160.         elif cellBelow.water < cellBelow.getCapacity() * 0.9:
  161.             self.waterType = WaterType.FALL
  162.         else:
  163.             self.waterType = WaterType.SETTLED
  164.     def __str__(self):
  165.         if self.background == SPACE and not self.isSource and self.water <= SPACE_THRESHHOLD:
  166.             return SPACE
  167.         elif self.background == SPACE and not self.isSource and self.waterType == WaterType.FALL:
  168.             return FALL
  169.         elif self.background == SPACE and not self.isSource and self.water <= RIVER_THRESHHOLD:
  170.             return RIVER
  171.         elif self.background == SPACE and not self.isSource:
  172.             return POOL
  173.         elif self.background == SPACE and self.water <= SPACE_THRESHHOLD:
  174.             return SOURCE
  175.         elif self.background == SPACE and self.waterType == WaterType.FALL:
  176.             return SOURCE_AND_FALL
  177.         elif self.background == SPACE and self.water <= RIVER_THRESHHOLD:
  178.             return SOURCE_AND_RIVER
  179.         elif self.background == SPACE:
  180.             return SOURCE_AND_POOL
  181.         elif self.background == BLOCK:
  182.             return BLOCK
  183.         elif isRamp(self.background) and self.isSource:
  184.             raise Exception
  185.         elif self.background == LRAMP and self.water <= SPACE_THRESHHOLD / 2:
  186.             return LRAMP
  187.         elif self.background == LRAMP and self.waterType == WaterType.FALL:
  188.             return LRAMP_AND_FALL
  189.         elif self.background == LRAMP and self.water <= RIVER_THRESHHOLD / 2:
  190.             return LRAMP_AND_RIVER
  191.         elif self.background == LRAMP:
  192.             return LRAMP_AND_POOL
  193.         elif self.water <= SPACE_THRESHHOLD / 2:
  194.             return RRAMP
  195.         elif self.waterType == WaterType.FALL:
  196.             return RRAMP_AND_FALL
  197.         elif self.water <= RIVER_THRESHHOLD / 2:
  198.             return RRAMP_AND_RIVER
  199.         else:
  200.             return RRAMP_AND_POOL
  201.  
  202. gridCells = map(lambda x: list(x), gridStr.split('\n'))
  203. height = len(gridCells)
  204. width = len(gridCells[0])
  205. grid = defaultdict(lambda : Cell(SPACE, False))
  206. for i in range(height):
  207.     for j in range(width):
  208.         grid[i,j] = Cell(findBackground(gridCells[i][j]), isSource(gridCells[i][j]))
  209.  
  210. def p(coords, offset):
  211.     """Add two tuples together.
  212.  
  213.     >>> p((2, 3), (-1, 0))
  214.     (1, 3)
  215.     """
  216.     return tuple(map(sum, zip(coords, offset)))
  217.  
  218. def adjacent(i,j,includeUp):
  219.     ret = []
  220.     for offset in (ORDINALS if includeUp else ORDINALS[:-1]):
  221.         ret.append(p((i,j), offset))
  222.     return ret
  223.  
  224. CONNECTION_TO_SHAPES = {DOWN: [SPACE, LRAMP, RRAMP], LEFT: [SPACE, RRAMP], RIGHT: [SPACE, LRAMP], UP: [SPACE]}
  225.  
  226. def adjoint(grid, i, j, includeUp, includeDown):
  227.     """Find all cells connected to this one (if this is a block then nothing connects to it).
  228.  
  229.     >>> grid = defaultdict(lambda : Cell(SPACE, False))
  230.     >>> adjoint(grid, 10, 1, True, True)
  231.     {(0, 1): (10, 2), (0, -1): (10, 0), (1, 0): (11, 1), (-1, 0): (9, 1)}
  232.  
  233.     >>> adjoint(grid, 10, 1, False, True)
  234.     {(0, 1): (10, 2), (0, -1): (10, 0), (1, 0): (11, 1)}
  235.  
  236.     >>> adjoint(grid, 10, 1, False, False)
  237.     {(0, 1): (10, 2), (0, -1): (10, 0)}
  238.  
  239.     >>> grid[10, 1].background = LRAMP
  240.     >>> adjoint(grid, 10, 1, True, True)
  241.     {(0, -1): (10, 0), (-1, 0): (9, 1)}
  242.  
  243.     >>> grid[10, 0].background = LRAMP
  244.     >>> grid[9, 1].background = RRAMP
  245.     >>> adjoint(grid, 10, 1, True, True)
  246.     {}
  247.     """
  248.     ret = {}
  249.     cell = grid[i, j]
  250.     if cell.background == BLOCK:
  251.         adj = []
  252.     elif cell.background == LRAMP:
  253.         adj = [LEFT, UP]
  254.     elif cell.background == RRAMP:
  255.         adj = [RIGHT, UP]
  256.     elif cell.background == SPACE:
  257.         adj = list(ORDINALS)
  258.     if not includeUp and UP in adj:
  259.         adj.remove(UP)
  260.     if not includeDown and DOWN in adj:
  261.         adj.remove(DOWN)
  262.     for offset in adj:
  263.         neighbourCoords = p((i,j), offset)
  264.         neighbour = grid[neighbourCoords]
  265.         if neighbour.background in CONNECTION_TO_SHAPES[offset]:
  266.             ret[offset] = neighbourCoords
  267.     return ret
  268.  
  269. def makeFrame(textLines, t):
  270.     img = Image.new('RGB', (200, 200))
  271.     draw = ImageDraw.Draw(img)
  272.     font = ImageFont.truetype('FreeMono.ttf', 14, encoding='unic')
  273.     y = 0
  274.     for line in textLines:
  275.         draw.text((0, y), line, (255,255,255), font=font)
  276.         y += 20
  277.     img.save('frame_%04d.png'%t)
  278.  
  279. def displayGrid(grid, t):
  280.     print
  281.     textLines = []
  282.     for i in range(height):
  283.         row = ''
  284.         for j in range(width):
  285.             grid[i,j].updateType(grid[i+1,j])
  286.             row += str(grid[i,j])
  287.         row += ' '
  288.         for j in range(width):
  289.             row += ('%x'%(grid[i,j].water / 10) if grid[i,j].water < 160 else '+')
  290.         textLines.append(row)
  291.     text = '\n'.join(textLines)
  292.     print text
  293.     makeFrame(textLines, t)
  294.  
  295. def constrain(n, minN, maxN):
  296.     if n < minN:
  297.         return minN
  298.     elif n > maxN:
  299.         return maxN
  300.     return n
  301.  
  302. def updateFlowDown(flow, contents, capacities):
  303.     flowDown = constrain(capacities[DOWN] - contents[DOWN], 0, contents[HERE])
  304.     flow[DOWN] += flowDown
  305.     contents[HERE] -= flowDown
  306.  
  307. def updateFlowAcross(flow, contents, capacities):
  308.     """Update flow across and a bit down to simulate pressure at this level."""
  309.     relevantCapacity = {}
  310.     for ordinal in [LEFT, HERE, RIGHT]:
  311.         relevantCapacity[ordinal] = capacities[ordinal]
  312.     relevantCapacity[DOWN] = capacities[DOWN] * COMPRESSABILITY
  313.     relevantContents = {}
  314.     for ordinal in [LEFT, HERE, RIGHT]:
  315.         relevantContents[ordinal] = constrain(contents[ordinal], 0, capacities[ordinal])
  316.     relevantContents[DOWN] = max(contents[DOWN] - capacities[DOWN], 0)
  317.  
  318.     idealFlowOut = 0
  319.     for ordinal in [LEFT, RIGHT, DOWN]:
  320.         idealFlowOut += relevantCapacity[ordinal] - relevantContents[ordinal]
  321.  
  322.     if idealFlowOut <= contents[HERE]:
  323.         for ordinal in [LEFT, RIGHT, DOWN]:
  324.             amount = max(relevantCapacity[ordinal] - relevantContents[ordinal], 0)
  325.             flow[ordinal] += amount
  326.             contents[HERE] -= amount
  327.     else:
  328.         # Add in flow to HERE before splitting between destinations
  329.         idealFlowOut += relevantCapacity[HERE] - relevantContents[HERE]
  330.         for ordinal in [LEFT, RIGHT, DOWN]:
  331.             amount = max(relevantCapacity[ordinal] - relevantContents[ordinal], 0) * relevantContents[HERE] / idealFlowOut
  332.             flow[ordinal] += amount
  333.             contents[HERE] -= amount
  334.  
  335. def updateFlowHere(flow, contents, capacities):
  336.     """Create a 'flow' to the current cell. Any remaining can be pushed upwards."""
  337.     constrained = constrain(contents[HERE], 0, capacities[HERE])
  338.     # The water will not actually leave the cell, so no need to add an explicit flow
  339.     #flow[HERE] += constrained
  340.     contents[HERE] -= constrained
  341.  
  342. def updateFlowUp(flow, contents, capacities):
  343.     """Update flow up and a bit across and down to simulate pressure at the level above."""
  344.     relevantCapacity = {}
  345.     # Magic constant here: 1.4 seems to work best!
  346.     relevantCapacity[UP] = capacities[UP] * 1.4
  347.     for ordinal in [LEFT, HERE, RIGHT]:
  348.         relevantCapacity[ordinal] = capacities[ordinal] * COMPRESSABILITY
  349.     relevantCapacity[DOWN] = capacities[DOWN] * COMPRESSABILITY * (1 + COMPRESSABILITY)
  350.     relevantContents = {}
  351.     relevantContents[UP] = contents[UP]
  352.     relevantContents[HERE] = contents[HERE]
  353.     for ordinal in [LEFT, RIGHT]:
  354.         relevantContents[ordinal] = max(contents[ordinal] - capacities[ordinal], 0)
  355.     relevantContents[DOWN] = max(contents[DOWN] - capacities[DOWN] * (1 + COMPRESSABILITY), 0)
  356.  
  357.     idealFlowOut = 0
  358.     for ordinal in [UP, LEFT, RIGHT, DOWN]:
  359.         idealFlowOut += relevantCapacity[ordinal] - relevantContents[ordinal]
  360.  
  361.     if idealFlowOut <= contents[HERE]:
  362.         for ordinal in [UP, LEFT, RIGHT, DOWN]:
  363.             amount = max(relevantCapacity[ordinal] - relevantContents[ordinal], 0)
  364.             flow[ordinal] += amount
  365.             contents[HERE] -= amount
  366.     else:
  367.         # Add in flow to HERE before splitting between destinations
  368.         idealFlowOut += relevantCapacity[HERE] - relevantContents[HERE]
  369.         for ordinal in [UP, LEFT, RIGHT, DOWN]:
  370.             amount = max(relevantCapacity[ordinal] - relevantContents[ordinal], 0) * relevantContents[HERE] / idealFlowOut
  371.             flow[ordinal] += amount
  372.             contents[HERE] -= amount
  373.  
  374. def main(grid):
  375.     t = 0
  376.     while t < FRAMES:
  377.         displayGrid(grid, t)
  378.         newGrid = defaultdict(lambda : Cell(SPACE, False))
  379.         for i, j in product(range(height), range(width)):
  380.             cell = grid[i,j]
  381.             if cell.isSource:
  382.                 cell.water += SOURCE_RATE
  383.             newCell = newGrid[i,j]
  384.             newCell.copyCell(cell)
  385.             flow = defaultdict(int)
  386.  
  387.             if cell.water <= 0:
  388.                 continue
  389.  
  390.             neighbourhood = adjoint(grid, i, j, True, True)
  391.  
  392.             capacities = {HERE: cell.getCapacity()}
  393.             contents = {HERE: cell.water}
  394.             for ordinal in ORDINALS:
  395.                 if ordinal in neighbourhood.keys():
  396.                     capacities[ordinal] = grid[neighbourhood[ordinal]].getCapacity()
  397.                     contents[ordinal] = grid[neighbourhood[ordinal]].water
  398.                 else:
  399.                     capacities[ordinal] = 0
  400.                     contents[ordinal] = 0
  401.  
  402.             # Down
  403.             updateFlowDown(flow, contents, capacities)
  404.             if contents[HERE] > 0:
  405.                 # Left and Right
  406.                 updateFlowAcross(flow, contents, capacities)
  407.                 if contents[HERE] > 0:
  408.                     # Here
  409.                     updateFlowHere(flow, contents, capacities)
  410.                     if contents[HERE] > 0:
  411.                         # Up
  412.                         #print 'Before %f'%contents[HERE]
  413.                         updateFlowUp(flow, contents, capacities)
  414.                         #print 'Up from %d %d: %s'%(i, j, flow)
  415.                         #print 'After %f'%contents[HERE]
  416.             for ordinal, amount in flow.items():
  417.                 if amount == 0:
  418.                     continue
  419.                 if ordinal not in neighbourhood.keys():
  420.                     print '%s not in %s when trying to move %f'%(ordinal, neighbourhood.keys(), amount)
  421.                     continue
  422.                 # Smooth the movement by only flowing half the amount left and right
  423.                 if ordinal in [LEFT, RIGHT]:
  424.                     amount = int(amount / 2)
  425.                 newGrid[neighbourhood[ordinal]].water += amount
  426.                 newCell.water -= amount
  427.  
  428.         grid = newGrid
  429.  
  430.         t += 1
  431.  
  432. if __name__ == '__main__':
  433.     import doctest
  434.     # Doesn't test inner functions!
  435.     failures, passes = doctest.testmod(raise_on_error=False)
  436.     if failures == 0:
  437.         main(grid)
  438.     else:
  439.         print 'Stopping with %d failures'%failures
  440.  
  441.  
  442.  
  443.  
  444.  
  445.  
  446.  
  447.  
  448.  
  449.  
  450.  
  451.  
  452.  
  453.  
  454.  
Runtime error #stdin #stdout #stderr 0.08s 16288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
   x       0000000000
#        # 0000000000
#        # 0000000000
#        # 0000000000
#### ##### 0000000000
#### ##### 0000000000
#### ##### 0000000000
########## 0000000000
stderr
copy 
Traceback (most recent call last):
  File "prog.py", line 437, in <module>
  File "prog.py", line 377, in main
  File "prog.py", line 293, in displayGrid
  File "prog.py", line 272, in makeFrame
  File "/usr/lib/python2.7/dist-packages/PIL/ImageFont.py", line 262, in truetype
    return FreeTypeFont(font, size, index, encoding)
  File "/usr/lib/python2.7/dist-packages/PIL/ImageFont.py", line 142, in __init__
    self.font = core.getfont(font, size, index, encoding)
IOError: cannot open resource
https://ideone.com/iPJJL1
language:
Python (cpython 2.7.16)
created:
8 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!