Subversion Repositories programming

Rev

Rev 385 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 385 Rev 393
Line 6... Line 6...
6 
 
 6 
 
7 
class PuzzlePiece (object):
 7 
class PuzzlePiece (object):
8 
 
 8 
 
9 
	EMPTY = 'E'
 9 
	EMPTY = 'E'
10 
 
 10 
 
11 
	def __init__ (self, state):
 11 
	def __init__ (self, state, depth=0, goal=None):
- 
 
 12 
		if len(state) != 9:
- 
 
 13 
			raise ValueError
- 
 
 14 
 
12 
		self.state = state
 15 
		self.state = state
- 
 
 16 
		self.depth = depth
- 
 
 17 
		self.goal = goal
13 
 
 18 
 
14 
	def __eq__ (self, rhs):
 19 
	def __eq__ (self, rhs):
15 
		return self.state == rhs.state
 20 
		return self.state == rhs.state
16 
 
 21 
 
17 
	def __repr__(self):
 22 
	def __repr__(self):
Line 24... Line 29...
24 
 
 29 
 
25 
		return result
 30 
		return result
26 
 
 31 
 
27 
	def get_children (self):
 32 
	def get_children (self):
28 
		children = []
 33 
		children = []
29 
		empty_pos = self.find_empty_pos ()
 34 
		empty_pos = self.find_position (self.EMPTY)
30 
 
 35 
 
31 
		# Get the correct moves for this position
 36 
		# Get the correct moves for this position
32 
		fn = {	0 : (self.move_down,  self.move_right),
 37 
		fn = {	0 : (self.move_down,  self.move_right),
33 
			1 : (self.move_down,  self.move_left,  self.move_right),
 38 
			1 : (self.move_down,  self.move_left,  self.move_right),
34 
			2 : (self.move_down,  self.move_left),
 39 
			2 : (self.move_down,  self.move_left),
Line 39... Line 44...
39 
			7 : (self.move_left,  self.move_right, self.move_up),
 44 
			7 : (self.move_left,  self.move_right, self.move_up),
40 
			8 : (self.move_left,  self.move_up) }[empty_pos]
 45 
			8 : (self.move_left,  self.move_up) }[empty_pos]
41 
 
 46 
 
42 
		# Call each of the proper functions
 47 
		# Call each of the proper functions
43 
		for f in fn:
 48 
		for f in fn:
44 
			children.append (PuzzlePiece (f (empty_pos)))
 49 
			children.append (PuzzlePiece (f (empty_pos), self.depth+1, self.goal))
45 
 
 50 
 
46 
		# Return the created list
 51 
		# Return the created list
47 
		return children
 52 
		return children
48 
 
 53 
 
49 
	def find_empty_pos (self):
 54 
	def find_position (self, value):
50 
		for i in xrange (len (self.state)):
 55 
		for i in xrange (len (self.state)):
51 
			if self.state[i] == self.EMPTY:
 56 
			if self.state[i] == value:
52 
				return i
 57 
				return i
53 
 
 58 
 
54 
		raise ValueError
 59 
		raise ValueError
55 
 
 60 
 
56 
	def move_up (self, empty_pos):
 61 
	def move_up (self, empty_pos):
Line 75... Line 80...
75 
		copy = self.state[:]
 80 
		copy = self.state[:]
76 
		copy[empty_pos] = copy[empty_pos + 3]
 81 
		copy[empty_pos] = copy[empty_pos + 3]
77 
		copy[empty_pos + 3] = self.EMPTY
 82 
		copy[empty_pos + 3] = self.EMPTY
78 
		return copy
 83 
		return copy
79 
 
 84 
 
- 
 
 85 
	def num_out_of_place (self):
- 
 
 86 
		"""Find the number of tiles that are out of place"""
- 
 
 87 
		count = 0
- 
 
 88 
 
- 
 
 89 
		for i in xrange(len(self.state)):
- 
 
 90 
			if self.state[i] != self.goal.state[i]:
- 
 
 91 
				count += 1
- 
 
 92 
 
- 
 
 93 
		return count
- 
 
 94 
 
- 
 
 95 
	def total_distance_from_correct (self):
- 
 
 96 
		"""Find the total distance that every piece of myself is from
- 
 
 97 
		the goal configuration given."""
- 
 
 98 
		total = 0
- 
 
 99 
 
- 
 
 100 
		for e in self.state:
- 
 
 101 
			mypos = self.find_position (e)
- 
 
 102 
			goalpos = self.goal.find_position (e)
- 
 
 103 
 
- 
 
 104 
			total += self.distance_from_correct (mypos, goalpos)
- 
 
 105 
 
- 
 
 106 
		return total
- 
 
 107 
 
- 
 
 108 
 
- 
 
 109 
	def distance_from_correct (self, mypos, goalpos):
- 
 
 110 
		"""Find a single piece's distance from the correct position."""
- 
 
 111 
		crmap={	0 : (0, 0),
- 
 
 112 
			1 : (0, 1),
- 
 
 113 
			2 : (0, 2),
- 
 
 114 
			3 : (1, 0),
- 
 
 115 
			4 : (1, 1),
- 
 
 116 
			5 : (1, 2),
- 
 
 117 
			6 : (2, 0),
- 
 
 118 
			7 : (2, 1),
- 
 
 119 
			8 : (2, 2) }
- 
 
 120 
 
- 
 
 121 
		myrow, mycol = crmap[mypos]
- 
 
 122 
		goalrow, goalcol = crmap[goalpos]
- 
 
 123 
 
- 
 
 124 
		return (abs(myrow - goalrow) + abs(mycol - goalcol))
- 
 
 125 
 
- 
 
 126 
def main ():
- 
 
 127 
	initial = [1, 2, 3, 4, 5, 6, 7, 8, 'E']
- 
 
 128 
	g = PuzzlePiece ([1, 7, 3, 4, 5, 6, 2, 8, 'E'])
- 
 
 129 
	p = PuzzlePiece (initial, 0, g)
80 
 
 130 
 
- 
 
 131 
	print 'out of place:', p.num_out_of_place ()
- 
 
 132 
	print 'dist:', p.total_distance_from_correct ()
81 
 
 133 
 
- 
 
 134 
if __name__ == '__main__':
- 
 
 135 
	main ()
82 
 
 136