Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Recursion solution in Clear category for The Cheapest Flight by lisardo.erman
def cheapest_flight(routes, a, b, cost=0, costs=None):
if costs is None:
costs = []
for route in routes:
if a in route and b in route:
costs.append(cost+route[2])
if a in route and b not in route:
between = route[1-route.index(a)]
routes_left = [x for x in routes if x != route]
cheapest_flight(routes_left, between, b, cost+route[2], costs)
return min(costs, default=0)
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!")
Dec. 16, 2020
