Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
All pairs of cities, all flights of minimal prices, multiple Dijkstra solution in Clear category for Useless Flights by Phil15
"""
I know it's bruteforce...
I thought about using (Roy-)Floyd-Warshall or Johnson algorithms
instead of Dijkstra multiple times. I misunderstood the mission
at first and didn't want to start over.
"""
#### Code from Cheapest Flight mission (except import deque and lru_cache) ####
from collections import defaultdict, deque
from heapq import heappop, heappush
# We suppose there is at most one flight between each pair of cities.
# Otherwise, just delete all except the cheapest one.
from functools import lru_cache
@lru_cache() # Each one is computed only once.
def flight_graph(schedule: tuple):
""" General graph of flights schedule. """
graph = defaultdict(dict)
for A, B, price in schedule:
graph[A][B] = graph[B][A] = price
return graph
def cheapest_flight(schedule, start, end):
""" Some Dijkstra's implementation with priority queue. """
graph = flight_graph(schedule)
pqueue, price_so_far = [(0, start)], {start: 0}
while pqueue:
price, current = heappop(pqueue)
if current == end:
return price
for new, current_to_new_price in graph[current].items(): # neighbors
new_price = price_so_far[current] + current_to_new_price
if new_price < price_so_far.get(new, float('inf')):
price_so_far[new] = new_price
heappush(pqueue, (new_price, new))
#### New code ####
def all_flights(schedule, start, end, given_price):
""" BFS to generate all flights from start to end of given_price. """
graph = flight_graph(schedule)
paths = deque([(0, [start])])
while paths:
price, path = paths.popleft()
for new, go_to_new_price in graph[path[-1]].items(): # neighbors
new_price = price + go_to_new_price
if new_price <= given_price and new not in path:
new_path = path[:] + [new]
if new_price < given_price:
paths.append((new_price, new_path))
elif new == end:
yield new_path
from itertools import combinations
def useless_flight(schedule):
schedule = tuple(map(tuple, schedule)) # we need tuples for lru_cache.
cities = set.union(*({a, b} for a, b, _ in schedule))
# Dicts maintain insertion order so use_flights and flights have the same order.
use_flights = {tuple(sorted(c)): False for *c, _ in schedule}
for start, end in combinations(cities, 2):
# Which flights can I use when I go to end from start? (cheapest ones)
best_price = cheapest_flight(schedule, start, end)
if best_price: # Otherwise, no flight to consider.
for path in all_flights(schedule, start, end, best_price):
for A, B in map(sorted, zip(path, path[1:])):
use_flights[A, B] = True
if all(use_flights.values()):
return [] # Don't continue if all flights are useful.
return [i for i, use in enumerate(use_flights.values()) if not use]
Jan. 29, 2019
Comments:
