Advertisement
Guest User

Untitled

a guest
May 28th, 2015
229
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.49 KB | None | 0 0
  1. #! -*- coding: utf-8 -*-
  2.  
  3. import argparse
  4.  
  5.  
  6. def print_state(fn):
  7. def decorator(*args, **kwargs):
  8. ret = fn(*args, **kwargs)
  9.  
  10. for bucket in Bucket.instances:
  11. print '[%d/%d]' % (bucket.content, bucket.capacity),
  12.  
  13. print ''
  14.  
  15. return ret
  16.  
  17. return decorator
  18.  
  19.  
  20. class Bucket(object):
  21.  
  22. instances = []
  23.  
  24. @print_state
  25. def __init__(self, capacity):
  26. self.capacity = capacity
  27. self.content = 0
  28.  
  29. Bucket.instances.append(self)
  30.  
  31. @print_state
  32. def fill(self):
  33. self.content = self.capacity
  34. return self
  35.  
  36. def available(self):
  37. return self.capacity - self.content
  38.  
  39. @print_state
  40. def pour(self, other):
  41. to_pour = min(self.content, other.available())
  42.  
  43. self.content -= to_pour
  44. other.content += to_pour
  45.  
  46. return self
  47.  
  48. @print_state
  49. def empty(self):
  50. self.content = 0
  51. return self
  52.  
  53. def is_full(self):
  54. return self.available() == 0
  55.  
  56. def is_empty(self):
  57. return self.available() == self.capacity
  58.  
  59.  
  60.  
  61. def bezout(a, b):
  62. curr_s, prev_s = 0, 1
  63. curr_t, prev_t = 1, 0
  64.  
  65. while b != 0:
  66. (q, b), a = divmod(a, b), b
  67. prev_s, curr_s = curr_s, prev_s - q * curr_s
  68. prev_t, curr_t = curr_t, prev_t - q * curr_t
  69.  
  70. return a, prev_s, prev_t
  71.  
  72.  
  73. def mix(c1, c2, target):
  74. gcd, s, t = bezout(c1, c2)
  75.  
  76. if target % gcd or target > max(c1, c2):
  77. print 'Impossible'
  78. return False
  79.  
  80. s *= target / gcd
  81. t *= target / gcd
  82. main, aux = Bucket(c1), Bucket(c2)
  83.  
  84. if s < 0:
  85. s, t = t, s
  86. main, aux = aux, main
  87.  
  88. while s and t: # s > 0, t <= 0
  89. if main.is_empty():
  90. main.fill()
  91. s -= 1
  92.  
  93. main.pour(aux)
  94.  
  95. if aux.is_full(): # aux wasn't empty
  96. aux.empty()
  97. t += 1
  98.  
  99. if s:
  100. main.pour(aux) # result will be returned in aux (gte capacity)
  101.  
  102. while s:
  103. main.fill().pour(aux)
  104. s -= 1
  105. elif t:
  106. while t:
  107. main.pour(aux)
  108.  
  109. if aux.is_full(): # aux wasn't empty
  110. aux.empty()
  111. t += 1
  112.  
  113. return True
  114.  
  115.  
  116. def main():
  117. parser = argparse.ArgumentParser()
  118. parser.add_argument('capacity1', type=int)
  119. parser.add_argument('capacity2', type=int)
  120. parser.add_argument('target', type=int)
  121. args = parser.parse_args()
  122.  
  123. c1, c2 = args.capacity1, args.capacity2
  124. target = args.target
  125.  
  126. mix(c1, c2, target)
  127.  
  128.  
  129. if __name__ == '__main__':
  130. main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement