Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Water Jars by Kurush
# migrated from python 2.7
from collections import deque
import copy
def checkio(first, second, goal):
search_queue = deque()
visited = set()
actions = ("12", "10", "01", "02", "20", "21")
path = []
search_queue.append([0, 0, path]);
while True:
if not search_queue: break
first_jar, second_jar, path = search_queue.popleft()
state = jars_to_string(first_jar, second_jar)
if (first_jar == goal) or (second_jar == goal):
return path
visited.add(state)
for action in actions:
from_s = int(action[0])
to_s = int(action[1])
if to_s == 0:
if from_s == 1:
new_first_jar = 0
new_second_jar = second_jar
if from_s == 2:
new_first_jar = first_jar
new_second_jar = 0
elif to_s == 1:
new_first_jar, new_second_jar = pour(from_s, first, second, first_jar, second_jar)
elif to_s == 2:
new_second_jar, new_first_jar = pour(from_s, second, first, second_jar, first_jar)
new_state = jars_to_string(new_first_jar, new_second_jar)
if (new_state not in visited):
new_path = copy.deepcopy(path)
new_path.append(action)
search_queue.append([new_first_jar, new_second_jar, new_path]);
return "Path is impossible"
def pour(from_s, first, second, first_jar, second_jar):
if from_s == 0:
new_first_jar = first
new_second_jar = second_jar
else:
residue = first - first_jar
if second_jar < residue:
new_first_jar = first_jar + second_jar
new_second_jar = 0
else:
new_first_jar = first
new_second_jar = second_jar - residue
return new_first_jar, new_second_jar
def jars_to_string(first_jar, second_jar):
return str(first_jar) + "-" + str(second_jar)
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 list(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"
June 27, 2014