Subversion Repositories programming

Rev

Go to most recent revision | Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
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