Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
32-liner: deque solution in Clear category for Water Sort Game by przemyslaw.daniel
from itertools import permutations
from collections import deque
def pour(flasks: list, pos1: int, pos2: int) -> list:
""" Pour liquid from one flask to another """
result = flasks[:]
result[pos1] = flasks[pos1].lstrip(flasks[pos1][0])
amount = len(flasks[pos1]) - len(result[pos1])
result[pos2] = flasks[pos1][0] * amount + result[pos2]
return result
def water_sort(flasks: list[str]) -> int:
""" Find minimum number of steps for Water Sort Game """
queue, volume, visited = deque([(0, flasks)]), max(map(len, flasks)), set()
while queue:
step, flasks = queue.popleft()
if tuple(flasks) in visited:
continue
visited |= {tuple(flasks)}
if all(len(flask) == volume and len(set(flask)) == 1
for flask in flasks if flask):
return step
for a, b in permutations(range(len(flasks)), 2):
if flasks[a] and (not flasks[b] or flasks[a][0] == flasks[b][0]):
_flasks = pour(flasks, a, b)
if len(_flasks[b]) <= volume:
queue.append((step + 1, _flasks))
Jan. 8, 2024
