Week 5 - Assignment 1 - CS103 - Swayam

Week 5 - Assignment 1

Problem Statement

You are lost in a maze. After exploring the maze for multiple hours, you have mapped out the entire structure of the maze on paper. However, you are still unable to find the path to the exit.

Given the map of the maze, find the best path to exit the maze as quickly as possible. When exploring multiple paths from a junction, always explore the path to the node with the lower index first.

Output the concatenation of the indices of the junction nodes that lie on the path from the start to the end, in that order.

Terminologies

Junction

A junction point in a maze is a point where you have more than one way to go and have to make a decision on which way to go to. It is represented as a node Ni. The following images are examples of junctions in mazes.

Image from Swayam
Figure: Image Taken from Swayam MOOC Course 'Getting Started with Competitive Programming'. All copyrights reserved with Swayam
Edge

An edge is a path from one junction node to another junction node. Formally, an edge e ∈ E is a set of two nodes Ni and Nj, such that i ≠ j and it is physically possible for you to travel from the junction node Ni to Nj or vice-versa without having to make any decisions in between.

{Ni, Nj} ∈ E ⟹ {Nj, Ni} ∈ E

Input Format

The first line of input contains a single integer t, which is the number of test cases. t test cases follow.

Each test case has multiple lines of input:

Constraints

Output Format

For each test case, output a single line of space-separated integers representing the junction numbers on the shortest path from the start to the exit. Assume that 1 is the start node, and n is the exit node. If two paths are the shortest path, print the one that chooses the lower index node at the first point of mismatch. If no path exists from start to exit, print -1.

Sample Input

2 6 8
1 2
1 4
2 3
2 4
3 4
3 5
4 6
5 6
7 8
1 2
1 4
2 3
2 4
3 4
3 5
4 6
5 6

Sample Output

1 4 6 -1

Explanation

1 4 6 3 5 2

Solution

# Import necessary modules
from collections import deque, defaultdict

# Function to find the shortest path from node 1 to node n using BFS
def bfs_shortest_path(n, graph):
    # Initialize visited list to keep track of visited nodes (1-indexed)
    visited = [False] * (n + 1)
    
    # Initialize prev list to reconstruct the path, set all to -1 initially
    prev = [-1] * (n + 1)
    
    # Initialize the queue with the starting node (node 1)
    queue = deque([1])
    
    # Mark the starting node as visited
    visited[1] = True
    
    # BFS loop to explore the graph level by level
    while queue:
        # Pop the node from the front of the queue
        node = queue.popleft()
        
        # If the target node `n` is reached, reconstruct the path from `n` to `1`
        if node == n:
            path = []
            while node != -1:
                path.append(node)  # Append the current node to the path
                node = prev[node]  # Move to the previous node in the path
            return path[::-1]  # Return the path in the correct order (1 to n)
        
        # Explore all neighbors of the current node, sorted to ensure lexicographically smallest path
        for neighbor in sorted(graph[node]):
            # If the neighbor has not been visited, process it
            if not visited[neighbor]:
                visited[neighbor] = True  # Mark the neighbor as visited
                prev[neighbor] = node  # Set the current node as the predecessor of the neighbor
                queue.append(neighbor)  # Add the neighbor to the queue for further exploration
    
    # If there's no path from node 1 to node n, return [-1] indicating no path found
    return [-1]

# Function to handle multiple test cases and provide results
def solve(test_cases):
    # Initialize a list to store results for each test case
    results = []
    
    # Loop through each test case
    for t in test_cases:
        n, a, edges = t  # Unpack the number of nodes, number of edges, and the edges list
        
        # Create a graph representation using a dictionary of lists
        graph = defaultdict(list)
        
        # Populate the graph with bidirectional edges
        for x, y in edges:
            graph[x].append(y)  # Add edge from x to y
            graph[y].append(x)  # Add edge from y to x (undirected graph)
        
        # Find the shortest path from node 1 to node n
        path = bfs_shortest_path(n, graph)
        
        # If no valid path is found, append "-1" to results
        if path == [-1]:
            results.append("-1")
        else:
            # If a valid path is found, convert it to a space-separated string and append to results
            results.append(" ".join(map(str, path)))
    
    # Print all results, each on a new line
    print("\n".join(results))

# Input handling
t = int(input().strip())  # Read number of test cases
test_cases = []  # Initialize list to store all test cases

# Loop to read each test case
for _ in range(t):
    n, a = map(int, input().strip().split())  # Read the number of nodes and edges
    edges = [tuple(map(int, input().strip().split())) for _ in range(a)]  # Read all edges
    test_cases.append((n, a, edges))  # Store the test case in the list

# Call the solve function with all test cases
solve(test_cases)

Sample Solution Provided by Instructor

from collections import defaultdict

def bfs(n, adList):
    # Initialize the open list with a tuple (node, parent). Start with node 1 and a parent of 0.
    open = [(1, 0)]
    
    # Dictionary to track parents of each node visited in the BFS.
    parents = {0: 0}  # Start with a dummy parent for 0, which doesn't exist.
    
    while open:
        # Dequeue the first element in the open list (FIFO for BFS).
        node, parent = open.pop(0)
        
        # If the node has already been visited, skip it.
        if node in parents:
            continue
        
        # Record the parent of the current node.
        parents[node] = parent
        
        # Check if we have reached the target node 'n'.
        if node == n:
            # Reconstruct the path from node 'n' back to the root node '1'.
            path = []
            while node:
                path.append(node)
                node, parent = parent, parents[parent]
            # Return the path from root to target node, reversing the order.
            return path[::-1]
        
        # Add all unvisited children of the current node to the open list.
        for child in sorted(adList[node]):
            if child not in parents:
                open.append((child, node))
    
    # If the loop exits without finding the target node, return [-1].
    return [-1]

# Read the number of test cases.
t = int(input())

# Loop through each test case.
for _ in range(t):
    n, a = map(int, input().split())  # Read the target node and the number of edges.
    
    # Initialize the adjacency list using defaultdict of lists.
    adList = defaultdict(list)
    
    # Read the edges and populate the adjacency list.
    for _ in range(a):
        x, y = map(int, input().split())
        adList[x].append(y)
        adList[y].append(x)  # Because the graph is undirected, add both directions.
    
    # Call the bfs function to find the path from node 1 to node 'n'.
    path = bfs(n, adList)
    
    # Print the path (or -1 if no path was found).
    print(*path)