Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
GITHUB - "The Cheapest Flight" solution in Clear category for The Cheapest Flight by jsg-inet
from typing import List
def cheapest_flight(costs: List, a: str, b: str) -> int:
# RECURSIVE FUNCTION "routes_costs"
# This function returns the costs list for all possible routes ("costs_routes")
# from "city_1" to "city_2" for a list of flights costs list ("flights") given
def routes_costs(flights: List, city_1:str, city_2: str) -> List:
# "flights_temp" is a copy of the given flights list
# in order to remove items (see later) and not alter the original
# flights list "flights"
flights_temp=flights.copy()
# "costs_routes" is the list to return. At the start it si empty.
costs_routes=[]
# All "flights" list is looped
for flight in flights:
# Case of direct flight for the given cities.
if city_1 in flight and city_2 in flight:
# Costs of the current looped flight is added to the list to return
costs_routes.append(flight[2])
# Current looped flight is deleted from the "flights_temp" list
# (this flight is no more useful for sending to recursive cases)
flights_temp.remove(flight)
# If only "city_1" is in current looped "flight",
# it is a case for recursive search.
elif city_1 in flight:
# Destination intermediate city is obtained (city_temp)
# It could be "flight[0]" or "flight[1]"
if city_1==flight[0]:
city_temp = flight[1]
else:
city_temp = flight[0]
# Current looped flight is deleted from the "flights_temp" list
# (this flight is no more useful for sending to recursive)
flights_temp.remove(flight)
# Recursive call to "routes_costs"
costs_temp = routes_costs(flights_temp,city_temp,city_2)
# The returned list of costs is updated adding the costs
# of the current looped flight and it is append to the
# list "costs_routes" that will be returned from the function
costs_routes+=[flight[2]+cost_route for cost_route in costs_temp]
# Finally, if city_1 is not in the current looped flight
else:
# If also city_2 is not in the current looped flight,
# "flight" is removed from the "flights_temp".
# It is important only remove it in this case (no "city_2" present)
# beacuse this flight could be necessary in a future recursive case.
if not city_2 in flight:
flights_temp.remove(flight)
# Finally, the whole costs list "costs_routes" is returned
return costs_routes
# MAIN CODE FOR "cheapest_flight" FUNCTION
# "try-except" is used to manage the case of empty list returned from
# recursive function "routes_costs"
try:
cheapest_value= min(routes_costs(costs, a, b))
# Calculating the minimum from the list of possible routes costs
# returned by "routes_costs", the cheapest flight value is obtained.
except:
# If "try" fails, list form "routes_costs" is empty and 0 is the value to return.
cheapest_value=0
# Finally, the cheapest flight value ("cheapest_value" is returned)
return cheapest_value
if __name__ == '__main__':
print("Example:")
print(cheapest_flight([['A', 'C', 100],
['A', 'B', 20],
['B', 'C', 50]],
'A',
'C'))
# These "asserts" are used for self-checking and not for an auto-testing
assert cheapest_flight([['A', 'C', 100],
['A', 'B', 20],
['B', 'C', 50]],
'A',
'C') == 70
assert cheapest_flight([['A', 'C', 100],
['A', 'B', 20],
['B', 'C', 50]],
'C',
'A') == 70
assert cheapest_flight([['A', 'C', 40],
['A', 'B', 20],
['A', 'D', 20],
['B', 'C', 50],
['D', 'C', 70]],
'D',
'C') == 60
assert cheapest_flight([['A', 'C', 100],
['A', 'B', 20],
['D', 'F', 900]],
'A',
'F') == 0
assert cheapest_flight([['A', 'B', 10],
['A', 'C', 15],
['B', 'D', 15],
['C', 'D', 10]],
'A',
'D') == 25
print("Coding complete? Click 'Check' to earn cool rewards!")
Aug. 9, 2021
Comments:
