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