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)"

from PyCompat import * # fixes for school computers

class PuzzlePiece (object):

        EMPTY = 'E'
        (UP, DOWN, LEFT, RIGHT) = ('up', 'down', 'left', 'right')

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

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

        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
                mov = { 0 : (self.DOWN,  self.RIGHT),
                        1 : (self.DOWN,  self.LEFT,  self.RIGHT),
                        2 : (self.DOWN,  self.LEFT),
                        3 : (self.DOWN,  self.RIGHT, self.UP),
                        4 : (self.DOWN,  self.LEFT,  self.RIGHT, self.UP),
                        5 : (self.DOWN,  self.LEFT,  self.UP),
                        6 : (self.RIGHT, self.UP),
                        7 : (self.LEFT,  self.RIGHT, self.UP),
                        8 : (self.LEFT,  self.UP) }[empty_pos]

                # Call each of the proper functions
                for m in mov:
                        config = self.move (empty_pos, m)
                        children.append (PuzzlePiece (config, self.depth+1, self.goal, m))

                # 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 (self, empty_pos, direction):
                val = 0

                if direction == self.UP:
                        val = -3
                elif direction == self.LEFT:
                        val = -1
                elif direction == self.RIGHT:
                        val = 1
                elif direction == self.DOWN:
                        val = 3
                else:
                        raise ValueError

                copy = self.state[:]
                copy[empty_pos] = copy[empty_pos + val]
                copy[empty_pos + val] = 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 ()