__author__ = 'padraic'
# 6.00.2x Problem Set 5
# Graph optimization
# Finding shortest paths through MIT buildings
#

import string

# 6.00.2x Problem Set 5
# Graph optimization
#
# A set of data structures to represent graphs
#

class Node(object):
    def __init__(self, name):
        self.name = str(name)
    def getName(self):
        return self.name
    def __str__(self):
        return self.name
    def __repr__(self):
        return (self.name)
    def __eq__(self, other):
        return self.name == other.name
    def __ne__(self, other):
        return not self.__eq__(other)
    def __hash__(self):
        # Override the default hash method
        # Think: Why would we want to do this?
        return self.name.__hash__()

class Edge(object):
    def __init__(self, src, dest):
        self.src = src
        self.dest = dest
    def getSource(self):
        return self.src
    def getDestination(self):
        return self.dest
    def __str__(self):
        return '{0}->{1}'.format(self.src, self.dest)

class Digraph(object):
    """
    A directed graph
    """
    def __init__(self):
        # A Python Set is basically a list that doesn't allow duplicates.
        # Entries into a set must be hashable (where have we seen this before?)
        # Because it is backed by a hashtable, lookups are O(1) as opposed to the O(n) of a list (nifty!)
        # See http://docs.python.org/2/library/stdtypes.html#set-types-set-frozenset
        self.nodes = set([])
        self.edges = {}
    def addNode(self, node):
        #print node
        if node in self.nodes:
            # Even though self.nodes is a Set, we want to do this to make sure we
            # don't add a duplicate entry for the same node in the self.edges list.
            raise ValueError('Duplicate node')
        else:
            self.nodes.add(node)
            self.edges[node] = []
    def addEdge(self, edge):
        src = edge.getSource()
        dest = edge.getDestination()
        if not(src in self.nodes and dest in self.nodes):
            raise ValueError('Node not in graph')
        self.edges[src].append(dest)
    def childrenOf(self, node):
        return self.edges[node]
    def hasNode(self, node):
        return node in self.nodes
    def __str__(self):
        res = ''
        for k in self.edges:
            for d in self.edges[str(k)]:
                res = '{0}{1}->{2}\n'.format(res, k, d)
        return res[:-1]




class WeightedEdge(Edge):
    def __init__(self,src,dest,total_distance,outside_distance):
        Edge.__init__(self,src,dest)
        self.node_1 = src
        self.node_2 =  dest
        self.total_distance = total_distance
        self.outside_distance= outside_distance

    def getTotalDistance(self):
        return (self.total_distance)

    def getOutdoorDistance(self):
        return (self.outside_distance)

    def __str__(self):
        return '{0}->{1} {2}'.format(self.node_1, self.node_2,self.total_distance, self.outside_distance)


class WeightedDigraph(Digraph):
    def __init__(self):
        Digraph.__init__(self)
    def addEdge(self, weighted_edge):
        if not(weighted_edge.node_1 in self.nodes and weighted_edge.node_2 in self.nodes):
            raise ValueError('Node not in graph')
        self.edges[weighted_edge.getSource()].append(weighted_edge)
    def childrenOf(self, node):
        return self.edges[node]
    def __str__(self):
        res = ''
        for k in self.edges:
            for d in self.edges[k]:
                res = '{0}{1}->{2} ({3}, {4})''\n'.format(res, k, (d.dest),float(d.total_distance),float(d.outside_distance))
        return res


def load_map(mapFilename):
    """
    Parses the map file and constructs a directed graph

    Parameters:
        mapFilename : name of the map file

    Assumes:
        Each entry in the map file consists of the following four positive
        integers, separated by a blank space:
            From To TotalDistance DistanceOutdoors
        e.g.
            32 76 54 23
        This entry would become an edge from 32 to 76.

    Returns:
        a directed graph representing the map
    """
    digraph = WeightedDigraph()
    with open(mapFilename, "r") as mit:
        for line in mit:
            (start_loc,
                 end_loc,
                 tot_dist,
                 out_dist) = line.split()
            n_1,n_2=Node(start_loc),Node(end_loc)

            if not digraph.hasNode(n_1):
                digraph.addNode(n_1)#

            if not digraph.hasNode(n_2):
                digraph.addNode(n_2)

            edge = WeightedEdge(n_1,n_2,tot_dist,out_dist)
            digraph.addEdge(edge)

        return  digraph


import time
def timeit(func):
    def _timeit(*args, **kwargs):
        start = time.time()
        try:
            result = func(*args, **kwargs)
        except ValueError:
            raise
        else:
            return result
        finally:
            duration = time.time() - start
            print '{0} ran for: {1:0.5f} secs.'.format(func.__name__, duration)
    return _timeit


@timeit
def bruteForceSearch(digraph, start, end, maxTotalDist, maxDistOutdoors):

    """
    Finds the shortest path from start to end using brute-force approach.
    The total distance travelled on the path must not exceed maxTotalDist, and
    the distance spent outdoor on this path must not exceed maxDisOutdoors.

    Parameters:
        digraph: instance of class Digraph or its subclass
        start, end: start & end building numbers (strings)
        maxTotalDist : maximum total distance on a path (integer)
        maxDistOutdoors: maximum distance spent outdoors on a path (integer)

    Assumes:
        start and end are numbers for existing buildings in graph

    Returns:
        The shortest-path from start to end, represented by
        a list of building numbers (in strings), [n_1, n_2, ..., n_k],
        where there exists an edge from n_i to n_(i+1) in digraph,
        for all 1 <= i < k.

        If there exists no path that satisfies maxTotalDist and
        maxDistOutdoors constraints, then raises a ValueError.
    """
    stack = [[edge] for edge in digraph.childrenOf(Node(start))]
    valid_paths = []
    end=Node(end)
    while stack:
        path = stack.pop()
        current_end=path[-1].dest
        # if end is reached and within max outdoor distance
        if current_end == end and sum(int(edge.outside_distance) for edge in path) <= maxDistOutdoors:
            valid_paths.append(path)
            continue
        for edge in digraph.childrenOf(current_end):
            # make sure not already in path
            if edge.dest not in  [x.src for x in path]: # loops
                new_path = path + [edge]
                 # find all paths under the max distance outdoors constraint first
                if sum(int(edge.outside_distance) for edge in path) <= maxDistOutdoors:
                    stack.append(new_path)
    shortest, min_distance = None, maxTotalDist
    for path in valid_paths:
        sum_p=sum(int(edge.total_distance) for edge in path)
        # sum total distance for each path, set shortest to path with lowest cost
        if sum_p <= min_distance:
            shortest, min_distance = path, sum_p
    if shortest is None:
        raise ValueError()
    return  [str(x.src) for x in shortest] +[str(end)]



from heapq import *
import  pdb

@timeit
def directedDFS(digraph, start, end, maxTotalDist, maxDistOutdoors):
    """
    Finds the shortest path from start to end using directed depth-first.
    search approach. The total distance travelled on the path must not
    exceed maxTotalDist, and the distance spent outdoor on this path must
    not exceed maxDistOutdoors.

    Parameters:
    digraph: instance of class Digraph or its subclass
    start, end: start & end building numbers (strings)
    maxTotalDist : maximum total distance on a path (integer)
    maxDistOutdoors: maximum distance spent outdoors on a path (integer)

    Assumes:
    start and end are numbers for existing buildings in graph

    Returns:
    The shortest-path from start to end, represented by
    a list of building numbers (in strings), [n_1, n_2, ..., n_k],
    where there exists an edge from n_i to n_(i+1) in digraph,
    for all 1 <= i < k.

    If there exists no path that satisfies maxTotalDist and
    maxDistOutdoors constraints, then raises a ValueError.
    """
    stack = [[edge] for edge in digraph.childrenOf(Node(start))]
    end=Node(end)
    best = None
    best_path = None
    while stack:
        path =  heappop(stack)
        current_end = path[-1].dest
        # if end is reached and within max outdoor distance
        sum_out_p =sum(int(edge.outside_distance) for edge in path)
        sum_tot_p=sum(int(edge.total_distance) for edge in path)
        if current_end == end  and sum_out_p <= maxDistOutdoors and sum_tot_p  <= maxTotalDist:
            # if we find a shorter path  make best_path that path and best the new best distance
             if best == None or sum_tot_p < best:
                best = sum_tot_p
                best_path = path
             continue
        for edge in digraph.childrenOf(current_end):
            # make sure not already in path
            if edge.dest not in  [x.src for x in path]: # avoid loops
                new_path = path + [edge]
                # if  new_path under both the max distance constraints
                sum_out_p = sum(int(edge.outside_distance) for edge in new_path)
                sum_tot_p= sum(int(edge.total_distance) for edge in new_path)
               # pdb.set_trace()
                if sum_out_p <= maxDistOutdoors and \
                        sum_tot_p <=maxTotalDist and sum_tot_p:
                    # check if total so far is still less than best path total and add it to the stack
                    if best == None or sum_tot_p < best:
                        heappush(stack,new_path)
                    # if not continue
                    continue
     # if we found a path
    if best_path:
        return [str(x.src) for x in best_path]+[str(end)]
    # no appropriate path found
    raise ValueError("No path found")
#
# Uncomment below when ready to test
#### NOTE! These tests may take a few minutes to run!! ####
if __name__ == '__main__':
#     Test cases

    mitMap = load_map("mit_map.txt")
    print isinstance(mitMap, Digraph)
    print isinstance(mitMap, WeightedDigraph)
    print 'nodes', mitMap.nodes
    print 'edges', mitMap.edges

#    print mitMap.__str__()

#
    LARGE_DIST = 10000
#
#    # Test case 1
    print "---------------"
    print "Test case 1:"
    print "Find the shortest-path from Building 32 to 56"
    expectedPath1 = ['32', '56']
    brutePath1 =bruteForceSearch(mitMap, '32', '56', LARGE_DIST, LARGE_DIST)
    dfsPath1 = directedDFS(mitMap, '32', '56', 100,100 )
    print "Expected: ", expectedPath1
    print "Brute-force: ", brutePath1
    print "DFS: ", dfsPath1
    print "Correct? BFS: {0}; DFS: {1}".format(expectedPath1 == brutePath1, expectedPath1 == dfsPath1)


    # #
# # #     Test case 2
    print "---------------"
    print "Test case 2:"
    print "Find the shortest-path from Building 32 to 56 without going outdoors"
    expectedPath2 = ['32', '36', '26', '16', '56']
    brutePath2 = bruteForceSearch(mitMap, '32', '56', LARGE_DIST, 0)
    dfsPath2 = directedDFS(mitMap, '32', '56', LARGE_DIST, 0)
    print "Expected: ", expectedPath2
    print "Brute-force: ", brutePath2
    print "DFS: ", dfsPath2
    print "Correct? BFS: {0}; DFS: {1}".format(expectedPath2 == brutePath2, expectedPath2 == dfsPath2)
    #
    # # Test case 3
    print "---------------"
    print "Test case 3:"
    print "Find the shortest-path from Building 2 to 9"
    expectedPath3 = ['2', '3', '7', '9']
    brutePath3 = bruteForceSearch(mitMap, '2', '9', LARGE_DIST, LARGE_DIST)
    dfsPath3 = directedDFS(mitMap, '2', '9', LARGE_DIST, LARGE_DIST)
    print "Expected: ", expectedPath3
    print "Brute-force: ", brutePath3
    print "DFS: ", dfsPath3
    print "Correct? BFS: {0}; DFS: {1}".format(expectedPath3 == brutePath3, expectedPath3 == dfsPath3)
#
#   ##  Test case 4
    print "---------------"
    print "Test case 4:"
    print "Find the shortest-path from Building 2 to 9 without going outdoors"
    expectedPath4 = ['2', '4', '10', '13', '9']
    brutePath4 = bruteForceSearch(mitMap, '2', '9', LARGE_DIST, 0)
    dfsPath4 = directedDFS(mitMap, '2', '9', LARGE_DIST, 0)
    print "Expected: ", expectedPath4
    print "Brute-force: ", brutePath4
    print "DFS: ", dfsPath4
    print "Correct? BFS: {0}; DFS: {1}".format(expectedPath4 == brutePath4, expectedPath4 == dfsPath4)

    ###Test case 5.
    print "---------------"
    print "Test case 5:"
    print "Find the shortest-path from Building 1 to 32"
    expectedPath5 = ['1', '4', '12', '32']
    brutePath5 = bruteForceSearch(mitMap, '1', '32', LARGE_DIST, LARGE_DIST)
    dfsPath5 = directedDFS(mitMap, '1', '32', LARGE_DIST, LARGE_DIST)
    print "Expected: ", expectedPath5
    print "Brute-force: ", brutePath5
    print "DFS: ", dfsPath5
    print "Correct? BFS: {0}; DFS: {1}".format(expectedPath5 == brutePath5, expectedPath5 == dfsPath5)

    ###Test case 6
    print "---------------"
    print "Test case 6:"
    print "Find the shortest-path from Building 1 to 32 without going outdoors"
    expectedPath6 = ['1', '3', '10', '4', '12', '24', '34', '36', '32']
    brutePath6 = bruteForceSearch(mitMap, '1', '32', LARGE_DIST, 0)
    dfsPath6 = directedDFS(mitMap, '1', '32', LARGE_DIST, 0)
    print "Expected: ", expectedPath6
    print "Brute-force: ", brutePath6
    print "DFS: ", dfsPath6
    print "Correct? BFS: {0}; DFS: {1}".format(expectedPath6 == brutePath6, expectedPath6 == dfsPath6)


    ###Test case 7
    print "---------------"
    print "Test case 7:"
    print "Find the shortest-path from Building 8 to 50 without going outdoors"
    bruteRaisedErr = 'No'
    dfsRaisedErr = 'No'
    try:
        bruteForceSearch(mitMap, '8', '50', LARGE_DIST, 0)
    except ValueError:
        bruteRaisedErr = 'Yes'

    try:
        directedDFS(mitMap, '8', '50', LARGE_DIST, 0)
    except ValueError:
        dfsRaisedErr = 'Yes'

    print "Expected: No such path! Should throw a value error."
    print "Did brute force search raise an error?", bruteRaisedErr
    print "Did DFS search raise an error?", dfsRaisedErr

    #####Test case 8
    print "---------------"
    print "Test case 8:"
    print "Find the shortest-path from Building 10 to 32 without walking"
    print "more than 100 meters in total"
    bruteRaisedErr = 'No'
    dfsRaisedErr = 'No'
    try:
        bruteForceSearch(mitMap, '10', '32', 100, LARGE_DIST)
    except ValueError:
        bruteRaisedErr = 'Yes'

    try:
        directedDFS(mitMap, '10', '32', 100, LARGE_DIST)
    except ValueError:
        dfsRaisedErr = 'Yes'

    print "Expected: No such path! Should throw a value error."
    print "Did brute force search raise an error?", bruteRaisedErr
    print "Did DFS search raise an error?", dfsRaisedErr