-
Notifications
You must be signed in to change notification settings - Fork 3.7k
/
Copy pathmissionaries_and_cannibals.py
82 lines (74 loc) · 5.53 KB
/
missionaries_and_cannibals.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
# -*- coding: utf-8 -*-
"""Missionaries_and_cannibals.ipynb
Automatically generated by Colaboratory.
Original file is located at
https://colab.research.google.com/drive/18FiKma_HxV25I73fzJk6HItVVk8Yyfqu
"""
def get_boat_at_left_new_states(game_state): #generating further steps to be taken.
new_states = [] #A new list to generate all the future states.
for missionary in range(game_state[0] + 1): #traversing in loop for m+1 times and c+1 times
for cannibal in range(game_state[1] + 1):
if missionary + cannibal < 1 or missionary + cannibal > 2: #at max, only two or min. 1 can travel on a boat. rest all cases to be eliminated.
continue
new_state = (game_state[0] - missionary, game_state[1] - cannibal,'right') #If we have 1 or 2 people on the boat, we will consider them.
if 0 < new_state[0] < new_state[1]: #if Cannibals outnumber Missionaries on the left side, we skip.
print("Future State: " + str(new_state) + ": Missionaries Killed")
continue
if 0 < 3 - new_state[0] < 3 - new_state[1]: #if Cannibals outnumber Missionaries on the right side, we skip.
print("Future State: " + str(new_state) + ": Missionaries Killed")
continue
new_states.append(new_state) #else, we can consider them a valid case and append it the list of future states.
return new_states
def get_boat_at_right_new_states(game_state): #generating further steps to be taken.
new_states = []
for missionary in range(3 - game_state[0] + 1):
for cannibal in range(3 - game_state[1] + 1):
if missionary + cannibal < 1 or missionary + cannibal > 2:
continue
new_state = (game_state[0] + missionary, game_state[1] + cannibal,'left')
if 0 < new_state[0] < new_state[1]:
print("Future State: " + str(new_state) + ": Missionaries Killed")
continue
if 0 < 3 - new_state[0] < 3 - new_state[1]:
print("Future State: " + str(new_state) + ": Missionaries Killed")
continue
new_states.append(new_state)
return new_states
def get_future_states(game_state): #a function to generate future states.
if game_state[2] == 'left':
return get_boat_at_left_new_states(game_state)
else:
return get_boat_at_right_new_states(game_state)
def bfs():
state_stack = list() #maintaining a stack for the states.
visited_states = set() #maintaining a set for visited states. (allowing only unique states to consider)
initial_state = (3, 3, 'left') #initialising our initial state.
visited_states.add(initial_state) #visiting the initial state.
states = [initial_state] #maintaining a list of states in consideration at a time.
all_states = [states] #maintaining a list of all the states taken in consideration throughout the game.
print("Initial state: " + str(initial_state)) #initialising our initial state.
win = False
while not win: #looping over until we win
print("States: " + str(states)) #printing the current states in consideration.
new_states = []
for game_state in states: #for every state in the states taken in consideration, checking for goal test condition
print("Current State: " + str(game_state))
state_stack.append(game_state)
if game_state[0] == game_state[1] == 0:
print("Win! Last state: " + str(game_state))
win = True
break
future_states = get_future_states(game_state) #if goal not achieved, moving ahead and generating its future states.(children)
for future_state in future_states: #for every future state generated,
if future_state not in visited_states: #ensuring, we have not visited it before
new_states.append(future_state) #only then we will consider it as our next state.
visited_states.add(future_state) #visiting the state.
print("Future State: " + str(future_state))
else:
print("Future State: " + str(future_state))
print("We have visited " + str(future_state) + " state before. let's move back")
print()
if not win:
states = new_states
all_states.append(states)
bfs()