from collections import deque
class State:
def __init__(self, left_bank, right_bank, boat):
self.left_bank = left_bank
self.right_bank = right_bank
self.boat = boat
def __eq__(self, other):
return self.left_bank == other.left_bank and \
self.right_bank == other.right_bank and \
self.boat == other.boat
def __hash__(self):
return hash((tuple(self.left_bank), tuple(self.right_bank), self.boat))
def __str__(self):
return f'Left Bank: {self.left_bank}, Right Bank: {self.right_bank}, Boat: {"Left" if self.boat == 1 else "Right"}'
def is_valid(state):
left_bank, right_bank, boat = state.left_bank, state.right_bank, state.boat
if boat == 1:
return len(left_bank) >= 1
else:
return len(right_bank) >= 1
def get_next_states(state):
next_states = []
left_bank, right_bank, boat = state.left_bank, state.right_bank, state.boat
if boat == 1: # If boat is on the left bank
for i in range(len(left_bank)):
for j in range(i+1, len(left_bank)+1):
passengers = left_bank[i:j]
new_left_bank = [x for x in left_bank if x not in passengers]
new_right_bank = right_bank + passengers
next_states.append(State(new_left_bank, new_right_bank, 0))
else: # If boat is on the right bank
for i in range(len(right_bank)):
for j in range(i+1, len(right_bank)+1):
passengers = right_bank[i:j]
new_right_bank = [x for x in right_bank if x not in passengers]
new_left_bank = left_bank + passengers
next_states.append(State(new_left_bank, new_right_bank, 1))
return next_states
def bfs(initial_state, goal_state):
visited = set()
queue = deque([[initial_state]])
while queue:
path = queue.popleft()
current_state = path[-1]
if current_state == goal_state:
return path
if current_state not in visited:
for next_state in get_next_states(current_state):
if is_valid(next_state):
new_path = list(path)
new_path.append(next_state)
queue.append(new_path)
visited.add(current_state)
return None
# Example Usage:
initial_state = State(['A', 'B', 'C'], [], 1) # Initial state with all items on the left bank and boat on the left bank
goal_state = State([], ['A', 'B', 'C'], 0) # Goal state with all items on the right bank and boat on the right bank
solution = bfs(initial_state, goal_state)
if solution:
print("Solution Found:")
for state in solution:
print(state)
else:
print("No solution exists!")
ZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgZGVxdWUKCmNsYXNzIFN0YXRlOgogICAgZGVmIF9faW5pdF9fKHNlbGYsIGxlZnRfYmFuaywgcmlnaHRfYmFuaywgYm9hdCk6CiAgICAgICAgc2VsZi5sZWZ0X2JhbmsgPSBsZWZ0X2JhbmsKICAgICAgICBzZWxmLnJpZ2h0X2JhbmsgPSByaWdodF9iYW5rCiAgICAgICAgc2VsZi5ib2F0ID0gYm9hdAoKICAgIGRlZiBfX2VxX18oc2VsZiwgb3RoZXIpOgogICAgICAgIHJldHVybiBzZWxmLmxlZnRfYmFuayA9PSBvdGhlci5sZWZ0X2JhbmsgYW5kIFwKICAgICAgICAgICAgICAgc2VsZi5yaWdodF9iYW5rID09IG90aGVyLnJpZ2h0X2JhbmsgYW5kIFwKICAgICAgICAgICAgICAgc2VsZi5ib2F0ID09IG90aGVyLmJvYXQKCiAgICBkZWYgX19oYXNoX18oc2VsZik6CiAgICAgICAgcmV0dXJuIGhhc2goKHR1cGxlKHNlbGYubGVmdF9iYW5rKSwgdHVwbGUoc2VsZi5yaWdodF9iYW5rKSwgc2VsZi5ib2F0KSkKCiAgICBkZWYgX19zdHJfXyhzZWxmKToKICAgICAgICByZXR1cm4gZidMZWZ0IEJhbms6IHtzZWxmLmxlZnRfYmFua30sIFJpZ2h0IEJhbms6IHtzZWxmLnJpZ2h0X2Jhbmt9LCBCb2F0OiB7IkxlZnQiIGlmIHNlbGYuYm9hdCA9PSAxIGVsc2UgIlJpZ2h0In0nCgpkZWYgaXNfdmFsaWQoc3RhdGUpOgogICAgbGVmdF9iYW5rLCByaWdodF9iYW5rLCBib2F0ID0gc3RhdGUubGVmdF9iYW5rLCBzdGF0ZS5yaWdodF9iYW5rLCBzdGF0ZS5ib2F0CiAgICBpZiBib2F0ID09IDE6CiAgICAgICAgcmV0dXJuIGxlbihsZWZ0X2JhbmspID49IDEKICAgIGVsc2U6CiAgICAgICAgcmV0dXJuIGxlbihyaWdodF9iYW5rKSA+PSAxCgpkZWYgZ2V0X25leHRfc3RhdGVzKHN0YXRlKToKICAgIG5leHRfc3RhdGVzID0gW10KICAgIGxlZnRfYmFuaywgcmlnaHRfYmFuaywgYm9hdCA9IHN0YXRlLmxlZnRfYmFuaywgc3RhdGUucmlnaHRfYmFuaywgc3RhdGUuYm9hdAogICAgaWYgYm9hdCA9PSAxOiAgIyBJZiBib2F0IGlzIG9uIHRoZSBsZWZ0IGJhbmsKICAgICAgICBmb3IgaSBpbiByYW5nZShsZW4obGVmdF9iYW5rKSk6CiAgICAgICAgICAgIGZvciBqIGluIHJhbmdlKGkrMSwgbGVuKGxlZnRfYmFuaykrMSk6CiAgICAgICAgICAgICAgICBwYXNzZW5nZXJzID0gbGVmdF9iYW5rW2k6al0KICAgICAgICAgICAgICAgIG5ld19sZWZ0X2JhbmsgPSBbeCBmb3IgeCBpbiBsZWZ0X2JhbmsgaWYgeCBub3QgaW4gcGFzc2VuZ2Vyc10KICAgICAgICAgICAgICAgIG5ld19yaWdodF9iYW5rID0gcmlnaHRfYmFuayArIHBhc3NlbmdlcnMKICAgICAgICAgICAgICAgIG5leHRfc3RhdGVzLmFwcGVuZChTdGF0ZShuZXdfbGVmdF9iYW5rLCBuZXdfcmlnaHRfYmFuaywgMCkpCiAgICBlbHNlOiAgIyBJZiBib2F0IGlzIG9uIHRoZSByaWdodCBiYW5rCiAgICAgICAgZm9yIGkgaW4gcmFuZ2UobGVuKHJpZ2h0X2JhbmspKToKICAgICAgICAgICAgZm9yIGogaW4gcmFuZ2UoaSsxLCBsZW4ocmlnaHRfYmFuaykrMSk6CiAgICAgICAgICAgICAgICBwYXNzZW5nZXJzID0gcmlnaHRfYmFua1tpOmpdCiAgICAgICAgICAgICAgICBuZXdfcmlnaHRfYmFuayA9IFt4IGZvciB4IGluIHJpZ2h0X2JhbmsgaWYgeCBub3QgaW4gcGFzc2VuZ2Vyc10KICAgICAgICAgICAgICAgIG5ld19sZWZ0X2JhbmsgPSBsZWZ0X2JhbmsgKyBwYXNzZW5nZXJzCiAgICAgICAgICAgICAgICBuZXh0X3N0YXRlcy5hcHBlbmQoU3RhdGUobmV3X2xlZnRfYmFuaywgbmV3X3JpZ2h0X2JhbmssIDEpKQogICAgcmV0dXJuIG5leHRfc3RhdGVzCgpkZWYgYmZzKGluaXRpYWxfc3RhdGUsIGdvYWxfc3RhdGUpOgogICAgdmlzaXRlZCA9IHNldCgpCiAgICBxdWV1ZSA9IGRlcXVlKFtbaW5pdGlhbF9zdGF0ZV1dKQogICAgd2hpbGUgcXVldWU6CiAgICAgICAgcGF0aCA9IHF1ZXVlLnBvcGxlZnQoKQogICAgICAgIGN1cnJlbnRfc3RhdGUgPSBwYXRoWy0xXQogICAgICAgIGlmIGN1cnJlbnRfc3RhdGUgPT0gZ29hbF9zdGF0ZToKICAgICAgICAgICAgcmV0dXJuIHBhdGgKICAgICAgICBpZiBjdXJyZW50X3N0YXRlIG5vdCBpbiB2aXNpdGVkOgogICAgICAgICAgICBmb3IgbmV4dF9zdGF0ZSBpbiBnZXRfbmV4dF9zdGF0ZXMoY3VycmVudF9zdGF0ZSk6CiAgICAgICAgICAgICAgICBpZiBpc192YWxpZChuZXh0X3N0YXRlKToKICAgICAgICAgICAgICAgICAgICBuZXdfcGF0aCA9IGxpc3QocGF0aCkKICAgICAgICAgICAgICAgICAgICBuZXdfcGF0aC5hcHBlbmQobmV4dF9zdGF0ZSkKICAgICAgICAgICAgICAgICAgICBxdWV1ZS5hcHBlbmQobmV3X3BhdGgpCiAgICAgICAgICAgIHZpc2l0ZWQuYWRkKGN1cnJlbnRfc3RhdGUpCiAgICByZXR1cm4gTm9uZQoKIyBFeGFtcGxlIFVzYWdlOgppbml0aWFsX3N0YXRlID0gU3RhdGUoWydBJywgJ0InLCAnQyddLCBbXSwgMSkgICMgSW5pdGlhbCBzdGF0ZSB3aXRoIGFsbCBpdGVtcyBvbiB0aGUgbGVmdCBiYW5rIGFuZCBib2F0IG9uIHRoZSBsZWZ0IGJhbmsKZ29hbF9zdGF0ZSA9IFN0YXRlKFtdLCBbJ0EnLCAnQicsICdDJ10sIDApICAjIEdvYWwgc3RhdGUgd2l0aCBhbGwgaXRlbXMgb24gdGhlIHJpZ2h0IGJhbmsgYW5kIGJvYXQgb24gdGhlIHJpZ2h0IGJhbmsKc29sdXRpb24gPSBiZnMoaW5pdGlhbF9zdGF0ZSwgZ29hbF9zdGF0ZSkKaWYgc29sdXRpb246CiAgICBwcmludCgiU29sdXRpb24gRm91bmQ6IikKICAgIGZvciBzdGF0ZSBpbiBzb2x1dGlvbjoKICAgICAgICBwcmludChzdGF0ZSkKZWxzZToKICAgIHByaW50KCJObyBzb2x1dGlvbiBleGlzdHMhIik=