-
Notifications
You must be signed in to change notification settings - Fork 0
/
C_M_Problem_Python.py
154 lines (131 loc) · 4.64 KB
/
C_M_Problem_Python.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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
class LeftBank:
def __init__(self):
self.mis = 3
self.can = 3
class RightBank:
def __init__(self):
self.mis = 0
self.can = 0
class Boat:
def __init__(self):
self.inLeft = True
self.mis = 0
self.can = 0
class State:
def __init__(self,m_state,c_state,b_state):
self.index = -1
self.children = []
self.m_state = m_state
self.c_state = c_state
self.boat_state = b_state
self.isVisited = False
self.tot_state = [self.m_state,self.c_state, self.boat_state]
initial_state,final_state = [[3,3,True],[0,0,True]],[[0,0,False],[3,3,False]]
queue = [initial_state]
data = []
state = State(initial_state[0][0], initial_state[0][1], initial_state[0][2])
state.index = 0
leftBank = LeftBank()
rightBank = RightBank()
boat = Boat()
root_state = state
parent_state = state
state_queue = [parent_state]
nodes = [parent_state]
def set_original_value(leftBank,rightBank,boat,m,c):
boat.inLeft = not boat.inLeft
if boat.inLeft == True:
leftBank.mis += m
leftBank.can += c
rightBank.mis -= m
rightBank.can -= c
else:
rightBank.mis += m
rightBank.can += c
leftBank.mis -= m
leftBank.can -= c
while True:
# print(queue)
current_state = queue.pop(0)
current_parent_state = state_queue.pop(0)
if (current_state[0][1] > current_state[0][0] and current_state[0][0] != 0) or (current_state[1][1] > current_state[1][0] and current_state[1][0] != 0):
# print("Invalid Condition")
continue
if (current_state == final_state):
print("Solution")
done = True
break
leftBank.mis,leftBank.can = current_state[0][0],current_state[0][1]
rightBank.mis, rightBank.can = current_state[1][0],current_state[1][1]
boat.inLeft = current_state[0][2]
mis_travel,can_travel = -1 ,-1
if (boat.inLeft == True):
mis_travel = (2 if leftBank.mis >2 else leftBank.mis)
can_travel = (2 if leftBank.can >2 else leftBank.can)
else:
mis_travel = (2 if rightBank.mis >2 else rightBank.mis)
can_travel = (2 if rightBank.can >2 else rightBank.can)
for m in range(mis_travel + 1):
for c in range(can_travel + 1):
if (m+c >2 or m+c == 0):
continue
boat.mis = m
boat.can = c
if boat.inLeft == True: # boat is in the left bank
leftBank.mis -= m
leftBank.can -= c
rightBank.mis += m
rightBank.can += c
else: # boat is in the right bank
leftBank.mis += m
leftBank.can += c
rightBank.mis -= m
rightBank.can -= c
boat.inLeft = not(boat.inLeft)
this_state = [[leftBank.mis, leftBank.can, boat.inLeft],[rightBank.mis, rightBank.can, boat.inLeft]]
# print (this_state)
if (this_state not in data):
if (this_state not in queue):
queue.append(this_state)
temp_state = State(this_state[0][0],this_state[0][1],this_state[0][2])
temp_state.index = current_parent_state.index + 1
current_parent_state.children.append(temp_state)
state_queue.append(temp_state)
nodes.append(temp_state)
set_original_value(leftBank,rightBank,boat,m,c)
data.append(current_state)
stack = []
current_node = root_state
current_node.isVisited = True
dfs_buffer = []
tab = 0
while True:
# print current_node
# if current_node in dfs_buffer:
# print 'hello there'
if ((current_node not in dfs_buffer) and tab >=0):
prefix = ' | '
suffix = ' |-------'
# print current_node
if tab == 0:
print str(current_node.tot_state)
if tab > 0:
print prefix * (tab-1) + suffix + str(current_node.tot_state)
# print
if (current_node != None):
if (x.isVisited == False for x in current_node.children) and len(current_node.children) > 0:
# print type(x)
next_node = next(x for x in current_node.children if x.isVisited == False)
# print str(next_node.tot_state)
dfs_buffer.append(current_node)
stack.append(current_node)
# print next_node == current_node
next_node.isVisited = True
current_node = next_node
# if current_node in dfs_buffer:
tab += 1
else:
current_node = stack.pop()
tab -= 1
else:
break