-
Notifications
You must be signed in to change notification settings - Fork 0
/
FWCG-Problem.py
124 lines (100 loc) · 4.79 KB
/
FWCG-Problem.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
### Import library
import heapq
print("Problem Description: Farmer, Wolf, Goat and Cabbage Problem. A farmer has a wolf, a goat, and a cabbage on the east side of a river.")
print("He wants to move them to the west side of the river. He has a boat in which he and only one other thing may fit.The wolf will eat the goat if they are left together unattended.")
print("The goat will eat the cabbage if they are left together unattended. Generate a plan for the farmer to safely move all items including himself to the west side of the river.")
### Defines State class to represent states of the problem
class State:
id_counter = 0
def __init__(self, farmer, wolf, goat, cabbage):
self.state = (farmer, wolf, goat, cabbage) ### Stores the state as a tuple
self.safe = (wolf != goat or farmer == goat) and (goat != cabbage or farmer == cabbage) ### Checks if the state is safe
self.id = State.id_counter
State.id_counter += 1
### Defines a method to check if the state is the goal state (all items on the west side)
def is_goal(self):
return all(not x for x in self.state)
### Defines a method to convert the state into a readable string format
def __str__(self):
f, w, g, c = self.state
positions = {0: "On East Side", 1: "On West Side"}
return f"Farmer: {positions[f]}, Wolf: {positions[w]}, Goat: {positions[g]}, Cabbage: {positions[c]}"
def __repr__(self):
return self.__str__()
### Check if two State objects are equal by comparing their state tuples
def __eq__(self, other):
return self.state == other.state
### This method returns a hash value for the State object. It uses the built-in hash function on the state tuple to return a unique value.
def __hash__(self):
return hash(self.state)
### This method calculates and returns the list of next possible States that can be reached from the current State.
### It loops through all the possible actions, which include all combinations of the farmer and one of the items.
### It creates a new State object for each possible action and checks if it is safe.
### If the new State is safe, it is added to the list of new States that can be reached from the current State.
def next_states(self):
f, w, g, c = self.state
new_states = []
for action in [(1 - f, w, g, c), (1 - f, 1 - w, g, c), (1 - f, w, 1 - g, c), (1 - f, w, g, 1 - c)]:
new_state = State(*action)
if new_state.safe:
new_states.append(new_state)
return new_states
def heuristic(state):
# Rule 1: Don't let the wolf eat the goat
# Rule 2: Don't let the goat eat the cabbage
# Rule 3: Move the farmer with each item, so that the farmer doesn't have to come back
f, w, g, c = state.state
return (w != g) + (g != c) + (f == w) + (f == g) + (f == c)
def depth_first_search(initial_state):
visited, stack = set(), [(initial_state, [])]
while stack:
state, path = stack.pop()
if state.is_goal():
return path + [state]
visited.add(state)
for new_state in state.next_states():
if new_state not in visited:
stack.append((new_state, path + [state]))
return None
def a_star_search(initial_state):
visited, queue = set(), [(heuristic(initial_state), initial_state.id, initial_state, [])]
while queue:
_, _, state, path = heapq.heappop(queue)
if state.is_goal():
return path + [state]
visited.add(state)
for new_state in state.next_states():
if new_state not in visited:
heapq.heappush(queue, (heuristic(new_state) + len(path) + 1, new_state.id, new_state, path + [state]))
return None
def display_state_space():
print("\nState Space")
print("Showing all possible states, including invalid ones:")
for farmer in [0, 1]:
for wolf in [0, 1]:
for goat in [0, 1]:
for cabbage in [0, 1]:
state = State(farmer, wolf, goat, cabbage)
print(state)
print()
### Define the initial state space
initial_state = State(1, 1, 1, 1)
### Display the state space
display_state_space()
###Display the solution for the DFS algorithm or return a failure message if it cannot be reached
dfs_solution = depth_first_search(initial_state)
if dfs_solution:
print("Depth-First Search Solution:")
for state in dfs_solution:
print(state)
else:
print("Depth-First Search failed to find a solution.")
print()
###Display the solution for the A* algorithm or return a failure message if it cannot be reached
astar_solution = a_star_search(initial_state)
if astar_solution:
print("A* Search Solution:")
for state in astar_solution:
print(state)
else:
print("A* Search failed to find a solution.")