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

from Menu import Menu
from PuzzlePiece import PuzzlePiece
import PuzzleSearch
import sys

################################################################################
### Search Algorithms
################################################################################

DEFAULT_MAX_ITERATIONS=1000

def m_search_generic (name, start, goals, add_algorithm, MAX_ITERATIONS=DEFAULT_MAX_ITERATIONS):
        s = PuzzleSearch.PuzzleSearch (start, goals)

        # Run the search
        result = s.search (add_algorithm, MAX_ITERATIONS)
        result.set_search_name (name)
        print result
        print

        return result

def m_bfs (start_node, goal_node):
        return m_search_generic ('Breadth First Search', start_node,
                        (goal_node, ), PuzzleSearch.add_bfs)

def m_dfs (start_node, goal_node):
        return m_search_generic ('Depth First Search', start_node,
                        (goal_node, ), PuzzleSearch.add_dfs)

def m_bfs_h1 (start_node, goal_node):
        return m_search_generic ('Best First Search: Heuristic 1', start_node,
                        (goal_node, ), PuzzleSearch.bfs_oop)

def m_bfs_h2 (start_node, goal_node):
        return m_search_generic ('Best First Search: Heuristic 2', start_node,
                        (goal_node, ), PuzzleSearch.bfs_dfc)

def m_asearch_h1 (start_node, goal_node):
        return m_search_generic ('A*-Search: Heuristic 1', start_node,
                        (goal_node, ), PuzzleSearch.astar_oop)

def m_asearch_h2 (start_node, goal_node):
        return m_search_generic ('A*-Search: Heuristic 2', start_node,
                        (goal_node, ), PuzzleSearch.astar_dfc)

################################################################################

def m_render_graph (result):
        if have_yapgvb():
                import yapgvb

        if result.result_graph == None:
                print 'The search failed, therefore I cannot render the graph!'
                return

        from DrawGraph import DrawGraph

        # Always render stupid mode
        dg = DrawGraph (result.search_name, result.result_graph)
        dg.render_stupid ('generated_by')
        print

        # Try to render the graph, nicely
        if have_yapgvb():
                fname = raw_input('Enter filename (press ENTER for \'res.svg\'): ')
                print

                if fname == '':
                        fname = 'res.svg'

                # Actually draw the graph
                dg = DrawGraph (result.search_name, result.result_graph)
                dg.render_graphviz (fname, yapgvb.engines.dot)

def gen_start_state (goal_node):
        DEPTH=12
        result = PuzzleSearch.get_nth_child (goal_node, DEPTH)

        # "Fix" the node given back to us
        result.depth = 0
        result.goal = goal_node
        result.generated_by = 'root'
        return result

def getstr (prompt):
        return raw_input (prompt + ': ')

def input_start_state ():
        state = []
        valid_inputs = ('1', '2', '3', '4', '5', '6', '7', '8', 'E')

        print 'Input start state, one row at a time, space seperated:'
        state += getstr ('Row 1').split()
        state += getstr ('Row 2').split()
        state += getstr ('Row 3').split()

        # Check and make sure its ok
        if len(state) != 9:
                print 'Too many states, try again!\n'
                return input_start_state ()

        for el in state:
                if el not in valid_inputs:
                        print '"%s" is not valid, try again!' % el
                        return input_start_state ()

        return state


def main ():

        # Very important start state information
        goal_config = ['1', '2', '3', '8', 'E', '4', '7', '6', '5']
        goal_node = PuzzlePiece (goal_config)

        m = Menu ()
        m.add_entry ('1', 'Enter start state', input_start_state)
        m.add_entry ('2', 'Generate Reachable Start State', gen_start_state)
        m.add_entry ('q', 'Quit', sys.exit)
        (entry, callback) = m.run_menu ()

        # Must be from #1
        if entry == '1':
                start_node = PuzzlePiece (callback(), 0, goal_node, 'root')
        elif entry == '2':
                start_node = callback(goal_node)
        else:
                callback ()

        # Get set up for the next menu
        search_result = None

        # Set up the final menu
        m = Menu ()
        m.add_entry ('1', 'Breadth First Search', m_bfs)
        m.add_entry ('2', 'Depth First Search', m_dfs)
        m.add_entry ('3', 'Best First Search: Heuristic 1', m_bfs_h1)
        m.add_entry ('4', 'Best First Search: Heuristic 2', m_bfs_h2)
        m.add_entry ('5', 'A*-Search: Heuristic 1', m_asearch_h1)
        m.add_entry ('6', 'A*-Search: Heuristic 2', m_asearch_h2)
        m.add_entry ('7', 'Change Start State', input_start_state)
        m.add_entry ('8', 'Generate Reachable Start State', gen_start_state)
        m.add_entry ('9', 'Render Graph of last result', m_render_graph)
        m.add_entry ('q', 'Quit', sys.exit)
        m.hide_entry ('9')

        while True:
                # Add support for graph rendering
                m.hide_entry ('9')
                if search_result:
                        if search_result.completed:
                                m.unhide_entry ('9')

                (entry, callback) = m.run_menu ()

                # Check if we need to change the start node
                if entry == '7':
                        start_node = PuzzlePiece (callback(), 0, goal_node)
                elif entry == '8':
                        search_result = False
                        start_node = callback (goal_node)
                elif entry == '9':
                        callback (search_result)
                # Check if we need to quit
                elif entry == 'q':
                        callback ()
                else:
                        # Must be one of the search functions, so call them!
                        search_result = callback (start_node, goal_node)

if __name__ == '__main__':
        main ()