fork download
copy 
  1. from collections import deque
  2.  
  3. class State:
  4.     def __init__(self, left_bank, right_bank, boat):
  5.         self.left_bank = left_bank
  6.         self.right_bank = right_bank
  7.         self.boat = boat
  8.  
  9.     def __eq__(self, other):
  10.         return self.left_bank == other.left_bank and \
  11.                self.right_bank == other.right_bank and \
  12.                self.boat == other.boat
  13.  
  14.     def __hash__(self):
  15.         return hash((tuple(self.left_bank), tuple(self.right_bank), self.boat))
  16.  
  17.     def __str__(self):
  18.         return f'Left Bank: {self.left_bank}, Right Bank: {self.right_bank}, Boat: {"Left" if self.boat == 1 else "Right"}'
  19.  
  20. def is_valid(state):
  21.     left_bank, right_bank, boat = state.left_bank, state.right_bank, state.boat
  22.     if boat == 1:
  23.         return len(left_bank) >= 1
  24.     else:
  25.         return len(right_bank) >= 1
  26.  
  27. def get_next_states(state):
  28.     next_states = []
  29.     left_bank, right_bank, boat = state.left_bank, state.right_bank, state.boat
  30.     if boat == 1:  # If boat is on the left bank
  31.         for i in range(len(left_bank)):
  32.             for j in range(i+1, len(left_bank)+1):
  33.                 passengers = left_bank[i:j]
  34.                 new_left_bank = [x for x in left_bank if x not in passengers]
  35.                 new_right_bank = right_bank + passengers
  36.                 next_states.append(State(new_left_bank, new_right_bank, 0))
  37.     else:  # If boat is on the right bank
  38.         for i in range(len(right_bank)):
  39.             for j in range(i+1, len(right_bank)+1):
  40.                 passengers = right_bank[i:j]
  41.                 new_right_bank = [x for x in right_bank if x not in passengers]
  42.                 new_left_bank = left_bank + passengers
  43.                 next_states.append(State(new_left_bank, new_right_bank, 1))
  44.     return next_states
  45.  
  46. def bfs(initial_state, goal_state):
  47.     visited = set()
  48.     queue = deque([[initial_state]])
  49.     while queue:
  50.         path = queue.popleft()
  51.         current_state = path[-1]
  52.         if current_state == goal_state:
  53.             return path
  54.         if current_state not in visited:
  55.             for next_state in get_next_states(current_state):
  56.                 if is_valid(next_state):
  57.                     new_path = list(path)
  58.                     new_path.append(next_state)
  59.                     queue.append(new_path)
  60.             visited.add(current_state)
  61.     return None
  62.  
  63. # Example Usage:
  64. initial_state = State(['A', 'B', 'C'], [], 1)  # Initial state with all items on the left bank and boat on the left bank
  65. goal_state = State([], ['A', 'B', 'C'], 0)  # Goal state with all items on the right bank and boat on the right bank
  66. solution = bfs(initial_state, goal_state)
  67. if solution:
  68.     print("Solution Found:")
  69.     for state in solution:
  70.         print(state)
  71. else:
  72.     print("No solution exists!")
Success #stdin #stdout 0.04s 9592KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Solution Found:
Left Bank: ['A', 'B', 'C'], Right Bank: [], Boat: Left
Left Bank: [], Right Bank: ['A', 'B', 'C'], Boat: Right
https://ideone.com/wtsZEg
language:
Python 3 (python  3.9.5)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!