Day 20 - Python

Problem Statement: Lok Sabha Election Campaign

You are given a list of connections between constituencies in a country. Each connection indicates that there is a direct road between two constituencies. Additionally, you are given the starting and ending constituencies for a Lok Sabha election campaign.

Your task is to write a Python program to find the shortest route for the election campaign, starting from the specified starting constituency and ending at the specified ending constituency. You need to implement the shortest_route function which takes the following parameters:

connections: A list of tuples, where each tuple represents a connection between two constituencies.

start: The name of the starting constituency for the campaign.

end: The name of the ending constituency for the campaign.

The function should return a list of strings representing the shortest route for campaigning, starting from the start and ending at the end. If no route is possible between the specified constituencies, return an empty list.

Input Format:

The first line contains an integer N, the number of connections between constituencies.

The next N lines contain two space-separated strings each, representing a connection between two constituencies.

The next line contains a string start_constituency, representing the starting constituency for the campaign.

The next line contains a string end_constituency, representing the ending constituency for the campaign.

Constraints:

1 ≤ N ≤ 1000

Constituency names consist of uppercase English letters only.

Each constituency name consists of at most 20 characters.

The starting and ending constituencies will always be different.

There may be multiple connections between the same pair of constituencies, but each connection will be listed only once.

Output Format:

If a route is found between the starting and ending constituencies, print the shortest route as space-separated constituency names on a single line.

If no route is found, print "No route found."

Sample Input:

4

A B

A C

B D

C D

A

D

Sample Output:

A -> B -> D

Explanation:

Number of Connections:

The user inputs 4, indicating that there are four connections between constituencies.

Connections Between Constituencies:

The user then inputs the connections between constituencies:

A B: This means there is a connection between Constituency A and Constituency B.

A C: This indicates a connection between Constituency A and Constituency C.

B D: This shows a connection between Constituency B and Constituency D.

C D: This represents a connection between Constituency C and Constituency D.

Starting Constituency:

After specifying the connections, the user inputs A as the starting constituency for the campaign route.

Ending Constituency:

Finally, the user inputs D as the ending constituency for the campaign route, indicating where the campaign should end.

After gathering this input, the program computes the shortest route for campaigning from Constituency A to Constituency D, passing through the specified connections (A -> B -> D).

SOLUTION:

from collections import defaultdict, deque

class CampaignRoute:

    def __init__(self):

        self.graph = defaultdict(list)

    def add_edge(self, u, v):

        self.graph[u].append(v)

        self.graph[v].append(u)

    def shortest_route(self, start, end):

        if start not in self.graph or end not in self.graph:

            return None

        visited = set()

        queue = deque([(start, [start])])

        while queue:

            node, path = queue.popleft()

            if node == end:

                return path

            if node not in visited:

                visited.add(node)

                for neighbor in self.graph[node]:

                    queue.append((neighbor, path + [neighbor]))

        return None

def get_edges():

    edges = []

    num_connections = int(input())

    for _ in range(num_connections):

        edge = input().split()

        edges.append(edge)

    return edges

def get_start_end():

    start = input()

    end = input()

    return start, end

campaign = CampaignRoute()

edges = get_edges()

for i in edges:

    campaign.add_edge(i[0], i[1])

start, end = get_start_end()

shortest_route = campaign.shortest_route(start, end)

if shortest_route:

    print(" -> ".join(shortest_route))

else:

    print("No route found.")

Insights:

• The graph representing the connections between constituencies is implemented using a defaultdict of lists (defaultdict(list)). This data structure allows for efficient storage of the connections, where each constituency is a key, and its value is a list of neighboring constituencies.
• The add_edge method of the CampaignRoute class is responsible for adding edges between constituencies. It appends both constituencies to each other's adjacency list, representing the bi-directional nature of the connections.
• The shortest_route method implements the BFS algorithm to find the shortest route between two constituencies. It traverses the graph level by level, exploring all neighboring constituencies before moving to the next level.
• BFS uses a deque (deque) as a queue to explore neighboring constituencies in a first-in-first-out manner. This ensures that constituencies are visited in the order they were discovered, leading to the discovery of the shortest route.
• A set called visited is used to keep track of visited constituencies during BFS traversal. This prevents revisiting the same constituency, avoiding infinite loops in cyclic graphs and ensuring that each constituency is visited only once.
• The BFS algorithm initializes the queue with a tuple containing the starting constituency and a list containing only the starting constituency itself. This kickstarts the BFS traversal from the starting constituency, with its own name as the initial path.
• As BFS explores the graph, it constructs the path from the starting constituency to the current constituency being visited. The path is represented as a list of constituency names, updated at each step of the traversal.
• The BFS traversal continues until either the ending constituency is reached or all possible paths have been explored. When the ending constituency is reached, the algorithm returns the shortest path found so far.
• The shortest_route method checks if the starting and ending constituencies are present in the graph before initiating BFS traversal. If either the starting or ending constituency is missing, the method returns None, indicating that no route can be found.

Navigate the coding landscape inspired by the strategic campaigns of Lok Sabha elections, where visionary leaders pave the way for progress and change.

Under the guidance of national leaders, India strides confidently on the path of growth, propelled by innovation, resilience, and collective vision.

Bharat Mata Ki Jai!