"""
CMSC 421 (Intro to AI) -- Dana Nau, Sept. 4, 2012
Eager tree search, with breadth-first and depth-first search strategies.

This file includes the problem definition for the Romanian Map problem.
Here are some things you can try:

ets.search('Arad', ets.neighbors, ets.is_bucharest)
ets.search('Arad', ets.neighbors, ets.is_bucharest, 'df')
ets.search('Arad', ets.neighbors, lambda x: x == 'Neamt', 'df')
ets.search('Arad', ets.neighbors, lambda x: x == 'Neamt', 'bf')
"""

class Node():
    """Class for nodes in the search tree"""
    def __init__(self,state,parent,cost):
        self.state = state
        self.parent = parent
        self.cost = cost
        self.children = []

def expand(x,successors):
    """Return a list of node x's children"""
    print('{:14} '.format(x.state),end='')
    # Python's sets have avg lookup time O(1) 
    path = set(getpath(x))
    for (state,cost) in successors(x.state):
        if state in path:
            print ("{0} x, 	".format(state), end='')
        else:
            y = Node(state, x, x.cost + cost)
            x.children.append(y)
            status = y.cost
            print ("{0} {1},	".format(state, status), end='')
    print('')
    return x.children

def getpath(y):
    """
    Return the path from y.state
    back to the initial state
    """
    path = [y.state]
    while y.parent != False:
        y = y.parent
        path.append(y.state)
    path.reverse()
    return path

def search(state, successors, goal, strategy='bf'):
    """
    Do a tree search starting at state.
    Look for a state x that satisfies goal(x).
    strategy may be either 'bf' (breadth-first) or 'df' (depth-first).
    """
    frontier = [Node(state,False,0)] # "False" means there's no parent
    print('\n{:14}  {}'.format('__Node__', '__Expansion__  . . .'))
    while frontier != []:
        if strategy == 'bf':
            x = frontier.pop(0)   # oldest node; this is inefficient
        elif strategy == 'df':
            x = frontier.pop()    # youngest node; does rightmost branch 1st
        else:
            raise RuntimeError("'" + strategy + "' is not a strategy")
        for y in expand(x,successors):
            if goal(y.state):
                print('');
                return getpath(y)
            frontier.append(y)
    return False


##################################################
# Problem definition for the Romanian map problem.
##################################################

map ={
    'Arad':          {'Sibiu':140,'Timisoara':118,'Zerind':75},
    'Bucharest':     {'Fagaras':211,'Giurgiu':90,'Pitesti':101,'Urziceni':85},
    'Craiova':       {'Dobreta':120,'Pitesti':138,'Rimnicu Vilcea':146},
    'Dobreta':       {'Craiova':120,'Mehadia':75},
    'Eforie':        {'Hirsova':86},
    'Fagaras':       {'Bucharest':211,'Sibiu':99},
    'Giurgiu':       {'Bucharest':90},
    'Hirsova':       {'Eforie':86,'Urziceni':98},
    'Iasi':          {'Neamt':87,'Vaslui':92},
    'Lugoj':         {'Mehadia':70,'Timisoara':111},
    'Mehadia':       {'Dobreta':75,'Lugoj':70},
    'Neamt':         {'Iasi':87},
    'Oradea':        {'Sibiu':151,'Zerind':71},
    'Pitesti':       {'Bucharest':101,'Craiova':138,'Rimnicu Vilcea':97},
    'Rimnicu Vilcea':{'Craiova':146,'Pitesti':97,'Sibiu':80},
    'Sibiu':         {'Arad':140,'Fagaras':99,'Oradea':151,'Rimnicu Vilcea':80},
    'Timisoara':     {'Arad':118,'Lugoj':111},
    'Urziceni':      {'Bucharest':85,'Hirsova':98,'Vaslui':142},
    'Vaslui':        {'Iasi':92,'Urziceni':142},
    'Zerind':        {'Arad':75,'Oradea':71}}

def neighbors(state):
    """
    Use this as the successors function. It returns state's
    neighbors on the map, as a sequence of (state,cost) pairs"""
    return map[state].items()

def is_bucharest(state):
    """
    Use this as the goal predicate.
    It returns True if state = Bucharest, else False
    """
    return state == 'Bucharest'