Rat in a Maze Problem in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Rat's Path in a Simple Maze

What is the output path of the rat in the maze after running the given code?

DSA Go

package main
import "fmt"

func solveMaze(maze [][]int, x, y int, path *[][]int) bool {
    n := len(maze)
    if x == n-1 && y == n-1 {
        *path = append(*path, []int{x, y})
        return true
    }
    if x >= 0 && y >= 0 && x < n && y < n && maze[x][y] == 1 {
        maze[x][y] = 0
        *path = append(*path, []int{x, y})
        if solveMaze(maze, x+1, y, path) {
            return true
        }
        if solveMaze(maze, x, y+1, path) {
            return true
        }
        *path = (*path)[:len(*path)-1]
        maze[x][y] = 1
    }
    return false
}

func main() {
    maze := [][]int{
        {1, 0, 0, 0},
        {1, 1, 0, 1},
        {0, 1, 0, 0},
        {1, 1, 1, 1},
    }
    path := [][]int{}
    if solveMaze(maze, 0, 0, &path) {
        fmt.Println(path)
    } else {
        fmt.Println("No path found")
    }
}

A [[0 0] [1 0] [1 1] [3 1] [3 2] [3 3]]

B [[0 0] [1 0] [1 1] [2 1] [3 1] [3 2] [3 3]]

C [[0 0] [0 1] [1 1] [2 1] [3 1] [3 2] [3 3]]

D No path found

💡 Hint

Trace the path by moving down first, then right, marking visited cells.

The rat moves down from (0,0) to (1,0), then right to (1,1), down to (2,1), then down to (3,1), right to (3,2), and finally right to (3,3). This is the valid path found by the recursive function.

🧠 Conceptual

intermediate

Understanding the Maze Representation

In the Rat in a Maze problem, what does the value '1' in the maze matrix represent?

A A cell that the rat can move into

B The destination cell only

C A blocked cell where the rat cannot move

D A cell that the rat has already visited

💡 Hint

Think about which cells allow movement.

In the maze matrix, '1' represents an open cell where the rat can move. '0' represents blocked cells.

🔧 Debug

advanced

Identify the Bug in Maze Solver

What error will occur if the line 'maze[x][y] = 0' is removed from the solveMaze function?

DSA Go

func solveMaze(maze [][]int, x, y int, path *[][]int) bool {
    n := len(maze)
    if x == n-1 && y == n-1 {
        *path = append(*path, []int{x, y})
        return true
    }
    if x >= 0 && y >= 0 && x < n && y < n && maze[x][y] == 1 {
        // maze[x][y] = 0 // This line is removed
        *path = append(*path, []int{x, y})
        if solveMaze(maze, x+1, y, path) {
            return true
        }
        if solveMaze(maze, x, y+1, path) {
            return true
        }
        *path = (*path)[:len(*path)-1]
        // maze[x][y] = 1
    }
    return false
}

A The function will enter infinite recursion causing a stack overflow

B The function will return false immediately

C The path will be empty

D The function will panic with index out of range error

💡 Hint

Consider what happens if the rat revisits the same cell repeatedly.

Without marking the current cell as visited (setting it to 0), the rat can keep revisiting the same cell causing infinite recursion.

🚀 Application

advanced

Number of Paths in a Maze

Given a 2x2 maze where all cells are open (value 1), how many unique paths exist from top-left to bottom-right if the rat can only move right or down?

DSA Go

maze := [][]int{
    {1, 1},
    {1, 1},
}

A 1

B 4

C 2

D 3

💡 Hint

Count all possible ways moving only right or down in a 2x2 grid.

The rat can move right then down, or down then right, so there are 2 unique paths.

❓ Predict Output

expert

Output of Maze Solver with No Possible Path

What is the output of the following code when the maze has no path from start to end?

DSA Go

package main
import "fmt"

func solveMaze(maze [][]int, x, y int, path *[][]int) bool {
    n := len(maze)
    if x == n-1 && y == n-1 {
        *path = append(*path, []int{x, y})
        return true
    }
    if x >= 0 && y >= 0 && x < n && y < n && maze[x][y] == 1 {
        maze[x][y] = 0
        *path = append(*path, []int{x, y})
        if solveMaze(maze, x+1, y, path) {
            return true
        }
        if solveMaze(maze, x, y+1, path) {
            return true
        }
        *path = (*path)[:len(*path)-1]
        maze[x][y] = 1
    }
    return false
}

func main() {
    maze := [][]int{
        {1, 0},
        {0, 1},
    }
    path := [][]int{}
    if solveMaze(maze, 0, 0, &path) {
        fmt.Println(path)
    } else {
        fmt.Println("No path found")
    }
}

A [[0 0] [1 1]]

B []

C [[0 0] [0 1] [1 1]]

D No path found

💡 Hint

Check if the rat can move to any adjacent cell from the start.

The maze blocks all paths from start to end, so the function returns false and prints 'No path found'.

Practice

1. What is the main goal of the Rat in a Maze Problem in Data Structures & Algorithms?

easy

A. Calculate the shortest distance between two points in a graph

B. Count the number of walls in the maze

C. Find a path from the start to the destination in a maze

D. Sort the maze cells in ascending order

Solution

1. Step 1: Understand the problem context

   The Rat in a Maze problem involves navigating through a maze represented by a grid to find a path from the start cell to the destination cell.

2. Step 2: Identify the goal

   The goal is to find any valid path that the rat can take to reach the destination without crossing walls or blocked cells.

3. Final Answer:

   Find a path from the start to the destination in a maze -> Option C

4. Quick Check:

   Goal = Find path [OK]

Hint: Remember: Rat must find a path, not count or sort [OK]

Common Mistakes:

• Confusing path finding with counting walls
• Thinking the problem is about shortest path always
• Assuming sorting cells is required

2. Which of the following Go function signatures correctly represents a recursive function to solve the Rat in a Maze problem?

easy

A. func solveMaze(maze [][]int, x, y int) bool

B. func solveMaze(maze []int, x int) int

C. func solveMaze(maze [][]int) string

D. func solveMaze(x, y int) [][]int

Solution

1. Step 1: Analyze function parameters for maze solving

   The function should accept the maze as a 2D slice and current coordinates (x, y) to explore recursively.

2. Step 2: Check return type for success indication

   The function returns a boolean indicating if a path exists from current position to destination.

3. Final Answer:

   func solveMaze(maze [][]int, x, y int) bool -> Option A

4. Quick Check:

   Correct signature = func solveMaze(maze [][]int, x, y int) bool [OK]

Hint: Look for 2D maze and bool return for path found [OK]

Common Mistakes:

• Using 1D slice instead of 2D for maze
• Wrong return type like int or string
• Missing current position parameters

3. What will be the output of the following Go code snippet for a 2x2 maze where all cells are open (1)?

package main
import "fmt"

func solveMaze(maze [][]int, x, y int, path *[][]int) bool {
    n := len(maze)
    if x == n-1 && y == n-1 {
        (*path)[x][y] = 1
        return true
    }
    if x >= 0 && y >= 0 && x < n && y < n && maze[x][y] == 1 {
        (*path)[x][y] = 1
        if solveMaze(maze, x+1, y, path) {
            return true
        }
        if solveMaze(maze, x, y+1, path) {
            return true
        }
        (*path)[x][y] = 0
        return false
    }
    return false
}

func main() {
    maze := [][]int{{1,1},{1,1}}
    path := [][]int{{0,0},{0,0}}
    if solveMaze(maze, 0, 0, &path) {
        fmt.Println(path)
    } else {
        fmt.Println("No path found")
    }
}

medium

A. [[1 0] [1 1]]

B. [[1 1] [0 1]]

C. [[1 1] [1 1]]

D. No path found

Solution

1. Step 1: Trace the recursive calls on 2x2 maze

   Starting at (0,0), mark path[0][0]=1, try moving down (1,0), mark path[1][0]=1, then try moving right (1,1), mark path[1][1]=1 and reach destination.

2. Step 2: Backtrack if needed and finalize path matrix

   Right move from (0,0) to (0,1) is also possible but the code tries down first. The final path marks (0,0), (1,0), and (1,1) as 1, and (0,1) as 0.

3. Final Answer:

   [[1 0] [1 1]] -> Option A

4. Quick Check:

   Path matrix = [[1 0] [1 1]] [OK]

Hint: Follow recursion order: down first, then right [OK]

Common Mistakes:

• Assuming path includes (0,1) first
• Confusing path matrix with maze matrix
• Ignoring backtracking step

4. Identify the bug in this Go code snippet for the Rat in a Maze problem:

func solveMaze(maze [][]int, x, y int, path *[][]int) bool {
    n := len(maze)
    if x == n-1 && y == n-1 {
        (*path)[x][y] = 1
        return true
    }
    if x < 0 || y < 0 || x >= n || y >= n || maze[x][y] == 0 {
        return false
    }
    (*path)[x][y] = 1
    if solveMaze(maze, x+1, y, path) || solveMaze(maze, x, y+1, path) {
        return true
    }
    (*path)[x][y] = 0
    return false
}

medium

A. Using pointer for path is unnecessary

B. Missing backtracking step to reset path[x][y] to 0

C. Wrong maze boundary checks

D. Incorrect base case for destination cell

Solution

1. Step 1: Review path marking and backtracking logic

   The code marks path[x][y] = 1 when visiting but never resets it to 0 if path fails, causing incorrect path recording.

2. Step 2: Identify missing backtracking step

   Backtracking requires resetting path[x][y] = 0 before returning false to allow other paths to be explored correctly.

3. Final Answer:

   Missing backtracking step to reset path[x][y] to 0 -> Option B

4. Quick Check:

   Backtracking reset missing = Missing backtracking step to reset path[x][y] to 0 [OK]

Hint: Always reset path on failure to backtrack [OK]

Common Mistakes:

• Forgetting to reset path cell on dead end
• Misplacing base case condition
• Ignoring boundary checks

5. Given a 4x4 maze represented as:

maze := [][]int{
  {1, 0, 0, 0},
  {1, 1, 0, 1},
  {0, 1, 0, 0},
  {1, 1, 1, 1},
}

Which path matrix will correctly represent a valid path from top-left (0,0) to bottom-right (3,3) using the Rat in a Maze algorithm?

hard

A. [[1 0 0 0] [1 1 0 0] [0 0 0 0] [0 1 1 1]]

B. [[1 0 0 0] [0 1 0 0] [0 1 0 0] [0 1 1 1]]

C. [[1 0 0 0] [1 0 0 0] [0 1 0 0] [1 1 1 1]]

D. [[1 0 0 0] [1 1 0 0] [0 1 0 0] [0 1 1 1]]

Solution

1. Step 1: Trace the valid path through the maze

   Start at (0,0), move down to (1,0), right to (1,1), down to (2,1), down to (3,1), right to (3,2), and right to (3,3).

2. Step 2: Mark path cells as 1 and others as 0

   Mark these cells in the path matrix as 1, others remain 0. This matches [[1 0 0 0] [1 1 0 0] [0 1 0 0] [0 1 1 1]] exactly.

3. Final Answer:

   [[1 0 0 0] [1 1 0 0] [0 1 0 0] [0 1 1 1]] -> Option D

4. Quick Check:

   Valid path marked = [[1 0 0 0] [1 1 0 0] [0 1 0 0] [0 1 1 1]] [OK]

Hint: Follow open cells from start to end marking path [OK]

Common Mistakes:

• Marking blocked cells as path
• Skipping valid moves down or right
• Confusing path matrix with maze layout