#!/usr/bin/env python

from __future__ import print_function

import os
import sys
import copy
from Queue import Queue

def printPath(path):
    print('\n ->'.join(path))

if __name__ == '__main__':
    if not (len(sys.argv) in (3,4)):
        print('Usage: '+sys.argv[0]+' startState goalState [top of states directory]', file=sys.stderr)
        sys.exit(1)

    startState = sys.argv[1]
    goalState = sys.argv[2]
    stateDir = "."
    if len(sys.argv) == 4:
        stateDir = sys.argv[3]

    if startState == goalState:
        printPath([startState])
        sys.exit(0)
    
    q = Queue()
    q.put((startState, [startState]))
    visited = {startState: None}
    while not q.empty():
        currState, currPath = q.get()
        transitDir = os.path.join(stateDir,currState,'transit')
        if not os.path.isdir(transitDir):
            continue
        for nextState in os.listdir(transitDir):
            if not visited.has_key(nextState):
                visited[nextState] = None
                newPath = copy.deepcopy(currPath)
                newPath.append(nextState)
                if nextState == goalState:
                    printPath(newPath)
                    sys.exit(0)
                q.put((nextState, newPath))

    print("No path exists from "+startState+" to "+goalState)
    sys.exit(0)

# vim: set ts=4 sw=4 expandtab smarttab: