Sha256: f22841e5359b7d414f978631827e6d6baef27d8a5206d93d5bd47869949a6e08
Contents?: true
Size: 1.81 KB
Versions: 62
Compression:
Stored size: 1.81 KB
Contents
'''
This solution implements a breadth-first search of the graph
of possible valid states for the two buckets until it reaches a state
in which one of the two buckets contains the goal amount
'''
def two_bucket(bucket_one_cap, bucket_two_cap, desired_liters, first):
sizes = [bucket_one_cap, bucket_two_cap]
goal = desired_liters
goalIndex = 0 if first == 'one' else 1
def empty(buckets, i):
return [0, buckets[1]] if i == 0 else [buckets[0], 0]
def fill(buckets, i):
return [sizes[0], buckets[1]] if i == 0 else [buckets[0], sizes[1]]
def consolidate(buckets, i):
amount = min(buckets[1 - i], sizes[i] - buckets[i])
target = buckets[i] + amount
src = buckets[1 - i] - amount
return [target, src] if i == 0 else [src, target]
def bucket_str(buckets):
return '{},{}'.format(*buckets)
invalid = [0, 0]
invalid[1 - goalIndex] = sizes[1 - goalIndex]
invalidStr = bucket_str(invalid)
buckets = [0, 0]
buckets[goalIndex] = sizes[goalIndex]
toVisit = []
visited = set()
count = 1
while goal not in buckets:
key = bucket_str(buckets)
if key != invalidStr and key not in visited:
visited.add(key)
nc = count + 1
for i in range(2):
if buckets[i] != 0:
toVisit.append((empty(buckets, i), nc))
if buckets[i] != sizes[i]:
toVisit.append((fill(buckets, i), nc))
toVisit.append((consolidate(buckets, i), nc))
if not any(toVisit):
raise ValueError('No more moves!')
buckets, count = toVisit.pop(0)
goalIndex = buckets.index(goal)
goalBucket = ['one', 'two'][goalIndex]
otherBucket = buckets[1 - goalIndex]
return (count, goalBucket, otherBucket)
Version data entries
62 entries across 62 versions & 1 rubygems