Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Combinations + priority queue solution in Clear category for River Crossing by ogoro
from itertools import combinations
import heapq
def print_history(history):
for i, line in enumerate(history):
print('{:2} {:20} {:10} - {:10} - {:10}'.format(i+1, *line))
def river_crossing(wolves, goats, cabbages, payload):
print('Analysing:', [wolves, goats, cabbages, payload])
priority = 0
id = 0
level = 0
state = 'Unloaded to left'
left = 'W' * wolves + 'G' * goats + 'C' * cabbages
boat = ''
right = ''
history = [[state, left, boat, right]]
heap = [[priority, id, level, state, left, boat, right, history]]
# main loop
while heap:
priority, _, level, state, left, boat, right, history = heapq.heappop(heap)
# print(f' {priority} {level} {state:17}: {left} _ {boat} _ {right}')
if level > 50 or id > 100000: break
if state == 'Unloaded to left':
# loading left to boat
for new_left_to_boat_count in range(0, payload+1 - len(boat)):
for new_left_to_boat in set(combinations(left, new_left_to_boat_count)):
new_left = left
new_boat = boat + ''.join(new_left_to_boat)
new_right = right
for passenger in new_left_to_boat:
new_left = new_left.replace(passenger, '', 1)
state = 'Loaded from left'
if 'G' in new_left and ('W' in new_left or 'C' in new_left):
continue
if [new_left, new_boat, new_right, state] in history:
continue
id += 1
priority = len(new_left)
heapq.heappush(heap, [priority, id, level + 1, state,
new_left, new_boat, new_right,
history + [[state, new_left, new_boat, new_right]]])
elif state == 'Loaded from left':
# unloading boat to right
for new_boat_to_right_count in range(0, len(boat)+1):
for new_boat_to_right in set(combinations(boat, new_boat_to_right_count)):
new_left = left
new_boat = boat
new_right = right + ''.join(new_boat_to_right)
for passenger in new_boat_to_right:
new_boat = new_boat.replace(passenger, '', 1)
# victory condition
if new_left == '' and new_boat == '':
path_len = int(len(history) / 2)
print('Path found:\n Length:', path_len, '\n Iterations:', id)
print_history(history)
print()
return path_len
state = 'Unloaded to right'
if [new_left, new_boat, new_right, state] in history:
continue
id += 1
priority = len(new_boat)
heapq.heappush(heap, [priority, id, level + 1, state,
new_left, new_boat, new_right,
history + [[state, new_left, new_boat, new_right]]])
elif state == 'Unloaded to right':
# loading right to boat
for new_right_to_boat_count in range(0, payload+1 - len(boat)):
for new_right_to_boat in set(combinations(right, new_right_to_boat_count)):
new_left = left
new_boat = boat + ''.join(new_right_to_boat)
new_right = right
for passenger in new_right_to_boat:
new_right = new_right.replace(passenger, '', 1)
state = 'Loaded from right'
if 'G' in new_right and ('W' in new_right or 'C' in new_right):
continue
if [new_left, new_boat, new_right, state] in history:
continue
id += 1
priority = len(new_boat)
heapq.heappush(heap, [priority, id, level + 1, state,
new_left, new_boat, new_right,
history + [[state, new_left, new_boat, new_right]]])
elif state == 'Loaded from right':
# unloading boat to left
for new_boat_to_left_count in range(0, len(boat)+1):
for new_boat_to_left in set(combinations(boat, new_boat_to_left_count)):
new_left = left + ''.join(new_boat_to_left)
new_boat = boat
new_right = right
for passenger in new_boat_to_left:
new_boat = new_boat.replace(passenger, '', 1)
state = 'Unloaded to left'
if [new_left, new_boat, new_right, state] in history:
continue
id += 1
priority = len(new_boat)
heapq.heappush(heap, [priority, id, level + 1, state,
new_left, new_boat, new_right,
history + [[state, new_left, new_boat, new_right]]])
# no pathes found
print('Unfortunately, no pathes found')
print(' Iterations:', id)
print()
return None
if __name__ == '__main__':
# 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'
assert river_crossing(3, 0, 3, 3) == 3, '3-3'
assert river_crossing(4, 0, 4, 3) == 5, '4-3'
assert river_crossing(5, 0, 5, 4) == 5, '5-4'
assert river_crossing(5, 0, 5, 3) == 7, '5-3'
assert river_crossing(0, 9, 1, 2) == 17, 'Final'
assert river_crossing(4, 3, 3, 3) is None, 'Timeout'
print("Coding complete? Click 'Check' to earn cool rewards!")
Dec. 1, 2020
Comments:
