Subversion Repositories programming

#!/usr/bin/env python

__author__    = "Ira W. Snyder (devel@irasnyder.com)"
__copyright__ = "Copyright (c) 2006 Ira W. Snyder (devel@irasnyder.com)"
__license__   = "GNU GPL v2 (or, at your option, any later version)"

class PuzzlePiece (object):

        EMPTY = 'E'

        def __init__ (self, state, depth=0, goal=None):
                if len(state) != 9:
                        raise ValueError

                self.state = state
                self.depth = depth
                self.goal = goal

        def __eq__ (self, rhs):
                return self.state == rhs.state

        def __repr__(self):
                """Print yourself"""
                result = ''
                for i in xrange(3):
                        result += '%s %s %s' % (self.state[3*i], self.state[3*i+1], self.state[3*i+2])
                        if i<2:
                                result += '\n'

                return result

        def get_children (self):
                children = []
                empty_pos = self.find_position (self.EMPTY)

                # Get the correct moves for this position
                fn = {  0 : (self.move_down,  self.move_right),
                        1 : (self.move_down,  self.move_left,  self.move_right),
                        2 : (self.move_down,  self.move_left),
                        3 : (self.move_down,  self.move_right, self.move_up),
                        4 : (self.move_down,  self.move_left,  self.move_right, self.move_up),
                        5 : (self.move_down,  self.move_left,  self.move_up),
                        6 : (self.move_right, self.move_up),
                        7 : (self.move_left,  self.move_right, self.move_up),
                        8 : (self.move_left,  self.move_up) }[empty_pos]

                # Call each of the proper functions
                for f in fn:
                        children.append (PuzzlePiece (f (empty_pos), self.depth+1, self.goal))

                # Return the created list
                return children

        def find_position (self, value):
                for i in xrange (len (self.state)):
                        if self.state[i] == value:
                                return i

                raise ValueError

        def move_up (self, empty_pos):
                copy = self.state[:]
                copy[empty_pos] = copy[empty_pos - 3]
                copy[empty_pos - 3] = self.EMPTY
                return copy

        def move_left (self, empty_pos):
                copy = self.state[:]
                copy[empty_pos] = copy[empty_pos - 1]
                copy[empty_pos - 1] = self.EMPTY
                return copy

        def move_right (self, empty_pos):
                copy = self.state[:]
                copy[empty_pos] = copy[empty_pos + 1]
                copy[empty_pos + 1] = self.EMPTY
                return copy

        def move_down (self, empty_pos):
                copy = self.state[:]
                copy[empty_pos] = copy[empty_pos + 3]
                copy[empty_pos + 3] = self.EMPTY
                return copy

        def num_out_of_place (self):
                """Find the number of tiles that are out of place"""
                count = 0

                for i in xrange(len(self.state)):
                        if self.state[i] != self.goal.state[i]:
                                count += 1

                return count

        def total_distance_from_correct (self):
                """Find the total distance that every piece of myself is from
                the goal configuration given."""
                total = 0

                for e in self.state:
                        mypos = self.find_position (e)
                        goalpos = self.goal.find_position (e)

                        total += self.distance_from_correct (mypos, goalpos)

                return total


        def distance_from_correct (self, mypos, goalpos):
                """Find a single piece's distance from the correct position."""
                crmap={ 0 : (0, 0),
                        1 : (0, 1),
                        2 : (0, 2),
                        3 : (1, 0),
                        4 : (1, 1),
                        5 : (1, 2),
                        6 : (2, 0),
                        7 : (2, 1),
                        8 : (2, 2) }

                myrow, mycol = crmap[mypos]
                goalrow, goalcol = crmap[goalpos]

                return (abs(myrow - goalrow) + abs(mycol - goalcol))

def main ():
        initial = [1, 2, 3, 4, 5, 6, 7, 8, 'E']
        g = PuzzlePiece ([1, 7, 3, 4, 5, 6, 2, 8, 'E'])
        p = PuzzlePiece (initial, 0, g)

        print 'out of place:', p.num_out_of_place ()
        print 'dist:', p.total_distance_from_correct ()

if __name__ == '__main__':
        main ()