Sydney Navigator

"""Sydney Navigator - your file.Fourteen jobs. Every one of them is something you have already built:  week 4   dict, a dict inside a dict, reading a text file  week 5   a graph, a frontier, BFS  week 6   flood fill, separate pieces, a distance map, several starts at once  week 7   weights, Dijkstra, heapq, going via a stopRun  python3 check_router.py  after each job. It tells you exactly whichone is not finished yet. When all fourteen pass, run  python3 serve.pyand open http://localhost:8000 to drive your own routing engine."""from heapq import heappush, heappopPERIODS = ["free", "am_peak", "pm_peak", "weekend"]def load_map(path):    # TODO 1  -  read sydney_map.txt into Python (week 4)    # Return five things, in this order:    #   nodes     dict: id -> {"id", "lat", "lng", "name"}    #   roads     list of {"from", "to", "minutes", "kind", "oneway"}    #   ferries   list of the same shape, with kind "ferry" and oneway False    #   traffic   dict: period -> {road kind -> multiplier}    #   incidents list of {"from", "to", "reason"}    #    # Ignore blank lines and anything after a '#'.    # A NODE line is:  NODE  id  lat  lng  the display name, which may have spaces    return {}, [], [], {}, []def is_closed(road, incidents):    # TODO 2    # Return True when this road matches an incident, in EITHER direction.    return Falsedef travel_time(road, traffic, period):    # TODO 3  -  this is where the traffic happens (week 7)    # Return the road's minutes multiplied by the right traffic number.    # A motorway at am_peak is 2.6 times its free-flow time.    return 0def build_graph(nodes, links, traffic, period, incidents):    # TODO 4  -  turn the map into a graph (weeks 5 and 7)    # Return a dict: node id -> list of (neighbour, minutes, kind)    #   - every node needs a key, even one with no roads    #   - skip any closed road    #   - a normal road goes in BOTH directions, a ONEWAY only one (week 7)    return {}def reachable(graph, start):    # TODO 5  -  flood fill (week 6)    # Return a sorted list of every node you can drive to from start.    return []def separate_areas(graph):    # TODO 6  -  how many pieces is the map in? (week 6)    # Return a list of areas. Each area is the list reachable() gave back.    # Walk the node ids in sorted order and skip any already claimed.    return []def fewest_changes(graph, start, goal):    # TODO 7  -  BFS (week 5)    # Return the route that passes through the FEWEST suburbs,    # ignoring how long each road takes. [] if there is no way through.    return []def time_map(graph, sources):    # TODO 8  -  Dijkstra with heapq, and no goal (weeks 6 and 7)    # Input: sources is a LIST. Every source starts at 0 minutes.    # Return: (best, came_from)    #   best      dict: node -> quickest minutes to reach it    #   came_from dict: node -> the node you arrived from    return {}, {}def rebuild(came_from, goal):    # TODO 9  -  walk backwards (weeks 5 to 7)    # Return the route from the start to goal, or [] if goal is not in there.    return []def quickest_route(graph, start, goal):    # TODO 10    # Return (route, minutes), or ([], None) when there is no way through.    # Use time_map. Do not write another search.    return [], Nonedef route_via(graph, start, via, goal):    # TODO 11  -  pick someone up on the way (week 7)    # Return (whole route, total minutes), or ([], None).    # Call quickest_route twice. Do not list the via stop twice.    return [], Nonedef within_minutes(times, budget):    # TODO 12  -  what can I reach before my meeting? (week 7)    # Input: times is the dict time_map() returned.    # Return: a sorted list of every node reachable in budget minutes or less.    return []def nearest_of(graph, start, targets):    # TODO 13  -  which hospital is closest? (weeks 6 and 7)    # Return (winner, route to it, minutes), or (None, [], None).    # If two are equally quick, pick the smaller id so the answer is stable.    return None, [], Noneclass Navigator:    """TODO 14  -  the system itself (weeks 2 and 3).    Load the map ONCE in __init__, then answer many questions about it.    Building the graph is slow, so keep the ones you have already built    in self._cache and hand them back next time.    """    def __init__(self, path):        # TODO 14a: load the map into self.nodes, self.roads, self.ferries,        #           self.traffic, self.incidents, and start an empty cache.        pass    def graph(self, period, include_ferries=False):        # TODO 14b: build the graph for this period, or return the cached one.        # With include_ferries, the links are self.roads + self.ferries.        return {}    def route(self, start, goal, period, via=None, include_ferries=False):        # TODO 14c: return {"path": [...], "minutes": number or None,        #                   "legs": self.describe(...)}        # Round the minutes to one decimal place.        # Use route_via when via is given, otherwise quickest_route.        return {"path": [], "minutes": None, "legs": []}    def describe(self, path, period, include_ferries=False):        # TODO 14d: turn a route into a list of legs, one per hop:        #   {"from", "to", "minutes", "kind"}        # Look each hop up in the graph to find how long it took and what        # kind of road it was.        return []