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

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!