| 385 |
ira |
1 |
#!/usr/bin/env python
|
|
|
2 |
|
|
|
3 |
__author__ = "Ira W. Snyder (devel@irasnyder.com)"
|
|
|
4 |
__copyright__ = "Copyright (c) 2006 Ira W. Snyder (devel@irasnyder.com)"
|
|
|
5 |
__license__ = "GNU GPL v2 (or, at your option, any later version)"
|
|
|
6 |
|
| 395 |
ira |
7 |
# Fix for the lame version of python on the school's computers (v2.1)
|
|
|
8 |
try:
|
|
|
9 |
(True, False)
|
|
|
10 |
except NameError:
|
|
|
11 |
(True, False) = (1, 0)
|
| 385 |
ira |
12 |
|
| 395 |
ira |
13 |
class PuzzlePiece:
|
|
|
14 |
|
| 385 |
ira |
15 |
EMPTY = 'E'
|
|
|
16 |
|
| 395 |
ira |
17 |
(UP, DOWN, LEFT, RIGHT) = ('up', 'down', 'left', 'right')
|
|
|
18 |
|
|
|
19 |
def __init__ (self, state, depth=0, goal=None, generated_by='root'):
|
| 393 |
ira |
20 |
if len(state) != 9:
|
|
|
21 |
raise ValueError
|
|
|
22 |
|
| 385 |
ira |
23 |
self.state = state
|
| 393 |
ira |
24 |
self.depth = depth
|
|
|
25 |
self.goal = goal
|
| 395 |
ira |
26 |
self.generated_by = generated_by
|
| 385 |
ira |
27 |
|
|
|
28 |
def __eq__ (self, rhs):
|
|
|
29 |
return self.state == rhs.state
|
|
|
30 |
|
|
|
31 |
def __repr__(self):
|
|
|
32 |
"""Print yourself"""
|
|
|
33 |
result = ''
|
|
|
34 |
for i in xrange(3):
|
|
|
35 |
result += '%s %s %s' % (self.state[3*i], self.state[3*i+1], self.state[3*i+2])
|
|
|
36 |
if i<2:
|
|
|
37 |
result += '\n'
|
|
|
38 |
|
|
|
39 |
return result
|
|
|
40 |
|
|
|
41 |
def get_children (self):
|
|
|
42 |
children = []
|
| 393 |
ira |
43 |
empty_pos = self.find_position (self.EMPTY)
|
| 385 |
ira |
44 |
|
|
|
45 |
# Get the correct moves for this position
|
| 395 |
ira |
46 |
mov = { 0 : (self.DOWN, self.RIGHT),
|
|
|
47 |
1 : (self.DOWN, self.LEFT, self.RIGHT),
|
|
|
48 |
2 : (self.DOWN, self.LEFT),
|
|
|
49 |
3 : (self.DOWN, self.RIGHT, self.UP),
|
|
|
50 |
4 : (self.DOWN, self.LEFT, self.RIGHT, self.UP),
|
|
|
51 |
5 : (self.DOWN, self.LEFT, self.UP),
|
|
|
52 |
6 : (self.RIGHT, self.UP),
|
|
|
53 |
7 : (self.LEFT, self.RIGHT, self.UP),
|
|
|
54 |
8 : (self.LEFT, self.UP) }[empty_pos]
|
| 385 |
ira |
55 |
|
|
|
56 |
# Call each of the proper functions
|
| 395 |
ira |
57 |
for m in mov:
|
|
|
58 |
config = self.move (empty_pos, m)
|
|
|
59 |
children.append (PuzzlePiece (config, self.depth+1, self.goal, m))
|
| 385 |
ira |
60 |
|
|
|
61 |
# Return the created list
|
|
|
62 |
return children
|
|
|
63 |
|
| 393 |
ira |
64 |
def find_position (self, value):
|
| 385 |
ira |
65 |
for i in xrange (len (self.state)):
|
| 393 |
ira |
66 |
if self.state[i] == value:
|
| 385 |
ira |
67 |
return i
|
|
|
68 |
|
|
|
69 |
raise ValueError
|
|
|
70 |
|
| 395 |
ira |
71 |
def move (self, empty_pos, direction):
|
|
|
72 |
val = 0
|
| 385 |
ira |
73 |
|
| 395 |
ira |
74 |
if direction == self.UP:
|
|
|
75 |
val = -3
|
|
|
76 |
elif direction == self.LEFT:
|
|
|
77 |
val = -1
|
|
|
78 |
elif direction == self.RIGHT:
|
|
|
79 |
val = 1
|
|
|
80 |
elif direction == self.DOWN:
|
|
|
81 |
val = 3
|
|
|
82 |
else:
|
|
|
83 |
raise ValueError
|
| 385 |
ira |
84 |
|
|
|
85 |
copy = self.state[:]
|
| 395 |
ira |
86 |
copy[empty_pos] = copy[empty_pos + val]
|
|
|
87 |
copy[empty_pos + val] = self.EMPTY
|
| 385 |
ira |
88 |
return copy
|
|
|
89 |
|
| 393 |
ira |
90 |
def num_out_of_place (self):
|
|
|
91 |
"""Find the number of tiles that are out of place"""
|
|
|
92 |
count = 0
|
| 385 |
ira |
93 |
|
| 393 |
ira |
94 |
for i in xrange(len(self.state)):
|
|
|
95 |
if self.state[i] != self.goal.state[i]:
|
|
|
96 |
count += 1
|
| 385 |
ira |
97 |
|
| 393 |
ira |
98 |
return count
|
| 385 |
ira |
99 |
|
| 393 |
ira |
100 |
def total_distance_from_correct (self):
|
|
|
101 |
"""Find the total distance that every piece of myself is from
|
|
|
102 |
the goal configuration given."""
|
|
|
103 |
total = 0
|
|
|
104 |
|
|
|
105 |
for e in self.state:
|
|
|
106 |
mypos = self.find_position (e)
|
|
|
107 |
goalpos = self.goal.find_position (e)
|
|
|
108 |
|
|
|
109 |
total += self.distance_from_correct (mypos, goalpos)
|
|
|
110 |
|
|
|
111 |
return total
|
|
|
112 |
|
|
|
113 |
|
|
|
114 |
def distance_from_correct (self, mypos, goalpos):
|
|
|
115 |
"""Find a single piece's distance from the correct position."""
|
|
|
116 |
crmap={ 0 : (0, 0),
|
|
|
117 |
1 : (0, 1),
|
|
|
118 |
2 : (0, 2),
|
|
|
119 |
3 : (1, 0),
|
|
|
120 |
4 : (1, 1),
|
|
|
121 |
5 : (1, 2),
|
|
|
122 |
6 : (2, 0),
|
|
|
123 |
7 : (2, 1),
|
|
|
124 |
8 : (2, 2) }
|
|
|
125 |
|
|
|
126 |
myrow, mycol = crmap[mypos]
|
|
|
127 |
goalrow, goalcol = crmap[goalpos]
|
|
|
128 |
|
|
|
129 |
return (abs(myrow - goalrow) + abs(mycol - goalcol))
|
|
|
130 |
|
|
|
131 |
def main ():
|
|
|
132 |
initial = [1, 2, 3, 4, 5, 6, 7, 8, 'E']
|
|
|
133 |
g = PuzzlePiece ([1, 7, 3, 4, 5, 6, 2, 8, 'E'])
|
|
|
134 |
p = PuzzlePiece (initial, 0, g)
|
|
|
135 |
|
|
|
136 |
print 'out of place:', p.num_out_of_place ()
|
|
|
137 |
print 'dist:', p.total_distance_from_correct ()
|
|
|
138 |
|
|
|
139 |
if __name__ == '__main__':
|
|
|
140 |
main ()
|
|
|
141 |
|