Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #! -*- coding: utf-8 -*-
- import argparse
- def print_state(fn):
- def decorator(*args, **kwargs):
- ret = fn(*args, **kwargs)
- for bucket in Bucket.instances:
- print '[%d/%d]' % (bucket.content, bucket.capacity),
- print ''
- return ret
- return decorator
- class Bucket(object):
- instances = []
- @print_state
- def __init__(self, capacity):
- self.capacity = capacity
- self.content = 0
- Bucket.instances.append(self)
- @print_state
- def fill(self):
- self.content = self.capacity
- return self
- def available(self):
- return self.capacity - self.content
- @print_state
- def pour(self, other):
- to_pour = min(self.content, other.available())
- self.content -= to_pour
- other.content += to_pour
- return self
- @print_state
- def empty(self):
- self.content = 0
- return self
- def is_full(self):
- return self.available() == 0
- def is_empty(self):
- return self.available() == self.capacity
- def bezout(a, b):
- curr_s, prev_s = 0, 1
- curr_t, prev_t = 1, 0
- while b != 0:
- (q, b), a = divmod(a, b), b
- prev_s, curr_s = curr_s, prev_s - q * curr_s
- prev_t, curr_t = curr_t, prev_t - q * curr_t
- return a, prev_s, prev_t
- def mix(c1, c2, target):
- gcd, s, t = bezout(c1, c2)
- if target % gcd or target > max(c1, c2):
- print 'Impossible'
- return False
- s *= target / gcd
- t *= target / gcd
- main, aux = Bucket(c1), Bucket(c2)
- if s < 0:
- s, t = t, s
- main, aux = aux, main
- while s and t: # s > 0, t <= 0
- if main.is_empty():
- main.fill()
- s -= 1
- main.pour(aux)
- if aux.is_full(): # aux wasn't empty
- aux.empty()
- t += 1
- if s:
- main.pour(aux) # result will be returned in aux (gte capacity)
- while s:
- main.fill().pour(aux)
- s -= 1
- elif t:
- while t:
- main.pour(aux)
- if aux.is_full(): # aux wasn't empty
- aux.empty()
- t += 1
- return True
- def main():
- parser = argparse.ArgumentParser()
- parser.add_argument('capacity1', type=int)
- parser.add_argument('capacity2', type=int)
- parser.add_argument('target', type=int)
- args = parser.parse_args()
- c1, c2 = args.capacity1, args.capacity2
- target = args.target
- mix(c1, c2, target)
- if __name__ == '__main__':
- main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement