Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
BFS solution in Clear category for River Crossing by pokosasa
from collections import deque
def river_crossing(wolves, goats, cabbages, payload):
W,G,C=0,1,2
banks=[(wolves,goats,cabbages),(0,0,0)]
res=None
used=set()
que=deque([(0,banks)])
while que:
cnt,banks=que.popleft()
side=cnt%2
if (side,banks[0]) in used:
continue
used.add((side,banks[0]))
if sum(banks[0])==0 and side==1:
res=cnt
break
if banks[1-side][W]*banks[1-side][G] or banks[1-side][G]*banks[1-side][C]:
continue
for w in range(min(banks[side][W],payload)+1):
for g in range(min(banks[side][G],payload-w)+1):
for c in range(min(banks[side][C],payload-w-g)+1):
n_banks=[None]*2
n_banks[side]=tuple(v1-v2 for v1,v2 in zip(banks[side],[w,g,c]))
n_banks[1-side]=tuple(v1+v2 for v1,v2 in zip(banks[1-side],[w,g,c]))
que.append((cnt+1,n_banks))
return res
if __name__ == '__main__':
print("Example:")
print (river_crossing(1, 1, 1, 1))
# These "asserts" are used for self-checking and not for an auto-testing
assert river_crossing(1, 1, 1, 1) == 7, 'original'
assert river_crossing(1, 1, 1, 2) == 3, 'payload +1'
assert river_crossing(2, 1, 1, 2) == 5, 'payload +1, wolf +1'
assert river_crossing(1, 2, 1, 1) is None, 'impossible'
print("Coding complete? Click 'Check' to earn cool rewards!")
July 1, 2020