PacMan – DFS Problem on HackerRank solved in Python 3

Artificial Intelligence in gaming often involves search algorithms to navigate through various scenarios. In this HackerRank problem, PacMan must find its way to the food using Depth-First Search (DFS) in a grid. Let’s break down the solution in Python 3.

The solution using Depth-first search Algorithm (in iterative form)

def dfs(r, c, pacman_r, pacman_c, food_r, food_c, grid ):    
    stack = []
    visited = []
    path = []
    dirs = [(-1,0), (0,-1), (0,1), (1,0)]
    dfs_nodes = []

    stack.append((int(pacman_r), int(pacman_c), path))
    visited.append((int(pacman_r), int(pacman_c)))

    while stack:
        row, col, path = stack.pop()
        if (row, col) not in dfs_nodes:
            dfs_nodes.append((row,col))
            path.append((row,col))

            if row == int(food_r) and col == int(food_c):
                return path, dfs_nodes

            for direction in dirs:
                next_row = row + direction[0]
                next_col = col + direction[1]
                    
                if (0 <= next_row <= int(r) and 0 <= next_col <= int(c) and (next_row, next_col) not in visited and grid[next_row][next_col]!= "%"):
                    stack.append((next_row, next_col, path.copy()))
                    visited.append((next_row, next_col))

    return None, None

pacman = input()
pacman_r, pacman_c = pacman.split()

food = input()
food_r, food_c = food.split()

dim = input()
r, c = dim.split()

grid = []
for i in range(int(r)):
    grid.append(input())

path, nodes = dfs(r, c, pacman_r, pacman_c, food_r, food_c, grid)

if path is not None and nodes is not None:
    print(len(nodes))
    for node in nodes:
        print(node[0], node[1])

    print(len(path)-1)
    for node in path:
        print(node[0], node[1])

Explanation:

• DFS Function: The dfs function takes grid dimensions, PacMan and food positions, and the grid as input. It uses a stack to perform DFS. The stack contains tuples of the form (row, col, path) where path is the current path from PacMan to the current position (row, col).
• DFS Nodes: dfs_nodes keeps track of nodes visited during DFS to ensure we don’t revisit the same node.
• Grid Exploration: The function explores adjacent cells based on valid directions (UP, LEFT, RIGHT, DOWN). The visited list ensures we don’t revisit cells, and walls are avoided. If the food is found, the function returns the path and nodes explored.
• Main Section: Takes input for PacMan’s position, food position, grid dimensions, and the grid itself. Calls the dfs function and prints the output in the specified format.

This solution adheres to the rules of DFS and follows the specified order of pushing nodes to the stack. It efficiently explores the grid until it finds the food, printing the nodes and path encountered during the process.

The test case in PacMan – DFS Problem on HackerRank

The sample input and output below attests to the precision of our algorithm:

3 9  
5 1  
7 20  
%%%%%%%%%%%%%%%%%%%%
%--------------%---%  
%-%%-%%-%%-%%-%%-%-%  
%--------P-------%-%  
%%%%%%%%%%%%%%%%%%-%  
%.-----------------%  
%%%%%%%%%%%%%%%%%%%%  

The output of the test case in PacMan – DFS Problem on HackerRank is as follows: first number (33) is the amount of nodes Explored, followed by all the nodes explored, then we need to print the distance (32) between Pacman and his food, followed by all the nodes in its way.

33
3 9
3 10
3 11
3 12
3 13
3 14
3 15
3 16
2 16
1 16
1 17
1 18
2 18
3 18
4 18
5 18
5 17
5 16
5 15
5 14
5 13
5 12
5 11
5 10
5 9
5 8
5 7
5 6
5 5
5 4
5 3
5 2
5 1
32
3 9
3 10
3 11
3 12
3 13
3 14
3 15
3 16
2 16
1 16
1 17
1 18
2 18
3 18
4 18
5 18
5 17
5 16
5 15
5 14
5 13
5 12
5 11
5 10
5 9
5 8
5 7
5 6
5 5
5 4
5 3
5 2
5 1

The submission of the Pacman – DFS problem

As you can see, this code successfully solved the PacMan – DFS problem using Python 3. The solution passed the rigorous HackerRank submission criteria, demonstrating proficiency in AI search techniques. Check out the prior image showcasing the correctness and efficiency of the algorithm.

Finally, I invite you to share your thoughts on this exhilarating journey through the PacMan – DFS problem. Have you faced similar challenges, or do you have alternative solutions to explore? Drop your comments below and let’s ignite a vibrant discussion! This is because your insights and experiences not only contribute to the collective learning but also inspire others on their coding odyssey. So don’t be shy – join the conversation, celebrate victories, and let’s continue pushing the boundaries of AI and problem-solving together!