from queue import Queue
from collections import defaultdict
"""The following code solves the problem of finding the minimum number of flights from a city a to a city b
given N cities labeled from 1 to N and directed flights from each city i to 2*i and to i-1
The algorithm works by creating a graph data structure of N vertices where each vertex represents a city,
then adds directed edges to represent flights, it does so by adding from each vertex i, a directed edge
to the vertex 2*i and a directed edge to the vertex i-1. Once the graph is ready, it uses the
breadth-first search algorithm to find a way to go from a to b by using those directed edges, it uses
BFS because it's guaranteed to use as few edges as possible, hence minimizing the number of flights
Example:
input: N=10, a=3, b=9
output: 4
explanation: to go from 3 to 9 we can go 3 -> 6 -> 5 -> 10 -> 9, this path needs 4 flights in total"""
def min_flights(N, a, b):
graph = defaultdict(lambda: []) # graph creation as an adjacency list
for i in range(1, N+1): # vertices go from 1 to n inclusive, one for each city
if 2*i <= N: # adding a directed edge from i to 2*i if it exists
graph[i].append(2*i)
if i-1 >= 0: # adding a directed edge from i to i-1 if it exists
graph[i].append(i-1)
queue = Queue() # creating a queue for the bfs process and adding start vertex a to it
queue.put((a, 0))
visited = {a} # creating a visited set to avoid traversing the same vertex twice
while not queue.empty(): # we use bfs because it guarantees using as less as flights as possible
u, level = queue.get() # we extract a vertex and its level, how many flights we did from a to reach it
if u == b: # if we arrived at the destination b, we return its level, the number of flights we did
return level
for v in graph[u]: # traversing unvisited neighbors of the current vertex
if v not in visited:
visited.add(v)
queue.put((v, level+1))
return -1 # no way to go from a to b, return -1
N, a, b = 10, 3, 9
print(min_flights(N, a, b))