Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Water Jars by papaeye
import collections
import itertools
import math
LAKE = 0
FIRST = 1
SECOND = 2
INF = float('inf')
class Jar(collections.namedtuple('Jar', ('mark', 'volume', 'max_volume'))):
__slots__ = ()
@property
def space(self):
if math.isinf(self.max_volume):
return self.max_volume
else:
return self.max_volume - self.volume
def directions(current):
for jar1, jar2 in itertools.combinations(current, 2):
if jar1.volume > 0 and jar2.space > 0:
yield jar1.mark, jar2.mark, min(jar2.space, jar1.volume)
if jar2.volume > 0 and jar1.space > 0:
yield jar2.mark, jar1.mark, min(jar1.space, jar2.volume)
def pour_water(current, src, dst, volume):
neighbor = list(current)
neighbor[src] -= volume
neighbor[dst] += volume
return tuple(neighbor)
def checkio(first, second, goal):
marks = (LAKE, FIRST, SECOND)
start = (INF, 0, 0)
max_volumes = (INF, first, second)
routes = {start: []}
queue = collections.deque([start])
while queue:
current = queue.popleft()
if goal in current:
return [''.join(map(str, x)) for x in routes[current]]
for src, dst, volume in directions(itertools.starmap(
Jar, zip(marks, current, max_volumes))):
neighbor = pour_water(current, src, dst, volume)
if neighbor not in routes:
routes[neighbor] = routes[current] + [(src, dst)]
queue.append(neighbor)
return []
if __name__ == '__main__':
#This part is using only for self-checking and not necessary for auto-testing
def check_solution(func, initial_data, max_steps):
first_volume, second_volume, goal = initial_data
actions = {
"01": lambda f, s: (first_volume, s),
"02": lambda f, s: (f, second_volume),
"12": lambda f, s: (
f - (second_volume - s if f > second_volume - s else f),
second_volume if f > second_volume - s else s + f),
"21": lambda f, s: (
first_volume if s > first_volume - f else s + f,
s - (first_volume - f if s > first_volume - f else s),
),
"10": lambda f, s: (0, s),
"20": lambda f, s: (f, 0)
}
first, second = 0, 0
result = func(*initial_data)
if len(result) > max_steps:
print("You answer contains too many steps. It can be shorter.")
return False
for act in result:
if act not in actions.keys():
print("I don't know this action {0}".format(act))
return False
first, second = actions[act](first, second)
if goal == first or goal == second:
return True
print("You did not reach the goal.")
return False
assert check_solution(checkio, (5, 7, 6), 10), "Example"
assert check_solution(checkio, (3, 4, 1), 2), "One and two"
March 9, 2014