-
Notifications
You must be signed in to change notification settings - Fork 11
/
State.py
91 lines (71 loc) · 2.68 KB
/
State.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
from Constants import Direction
MAX_M = 30
MAX_C = 30
CAP_BOAT = 20
CNST = None
class State(object):
def __init__(self, missionaries, cannibals, dir, missionariesPassed, cannibalsPassed, level, CONSTS,moves):
self.missionaries = missionaries
self.cannibals = cannibals
self.dir = dir
self.action = ""
self.level = level
self.missionariesPassed = missionariesPassed
self.cannibalsPassed = cannibalsPassed
self.CONSTANTS = CONSTS
self.moves = moves
global MAX_M
global MAX_C
global CAP_BOAT
global CNST
if not CONSTS is None:
CNST = CONSTS
MAX_M = CONSTS.MAX_M
MAX_C = CONSTS.MAX_C
CAP_BOAT = CONSTS.CAP_BOAT
# pass True to count forward
def successors(self):
listChild = []
if not self.isValid() or self.isGoalState():
return listChild
if self.dir == Direction.OLD_TO_NEW:
sgn = -1
direction = "from the original shore to the new shore"
else:
sgn = 1
direction = "back from the new shore to the original shore"
for i in self.moves:
(m, c) = i
self.addValidSuccessors(listChild, m, c, sgn, direction)
return listChild
def addValidSuccessors(self, listChild, m, c, sgn, direction):
newState = State(self.missionaries + sgn * m, self.cannibals + sgn * c, self.dir + sgn * 1,
self.missionariesPassed - sgn * m, self.cannibalsPassed - sgn * c, self.level + 1,
self.CONSTANTS,self.moves)
if newState.isValid():
newState.action = " take %d missionaries and %d cannibals %s." % (m, c, direction)
listChild.append(newState)
def isValid(self):
# obvious
if self.missionaries < 0 or self.cannibals < 0 or self.missionaries > MAX_M or self.cannibals > MAX_C or (
self.dir != 0 and self.dir != 1):
return False
# then check whether missionaries outnumbered by cannibals in any shore
if (self.cannibals > self.missionaries > 0) or (
self.cannibalsPassed > self.missionariesPassed > 0): # more cannibals then missionaries on original shore
return False
return True
def isGoalState(self):
return self.cannibals == 0 and self.missionaries == 0 and self.dir == Direction.NEW_TO_OLD
def __repr__(self):
return "\n%s\n\n< @Depth:%d State (%d, %d, %d, %d, %d) >" % (
self.action, self.level, self.missionaries, self.cannibals, self.dir, self.missionariesPassed,
self.cannibalsPassed)
def __eq__(self, other):
return self.missionaries == other.missionaries and self.cannibals == other.cannibals and self.dir == other.dir
def __hash__(self):
return hash((self.missionaries, self.cannibals, self.dir))
def __ne__(self, other):
return not (self == other)
TERMINAL_STATE = State(-1, -1, Direction.NEW_TO_OLD, -1, -1, 0, CNST,None)
# INITIAL_STATE = State(MAX_M, MAX_C, Direction.OLD_TO_NEW, 0, 0, 0, CNST)