Rat in a Maze Problem in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the rat can move to the next cell inside the maze boundaries.

DSA Go

func isSafe(x, y, n int, maze [][]int) bool {
    return x >= 0 && y >= 0 && x < [1] && y < n && maze[x][y] == 1
}

Drag options to blanks, or click blank then click option'

An

Bmaze

Clen(maze)

Dcap(maze)

Attempts:

3 left

💡 Hint

Common Mistakes

Using the variable n instead of len(maze) for boundary check.

The maze size is given by the length of the maze slice. So, to check boundaries, use len(maze).

2fill in blank

medium

Complete the code to mark the current cell as part of the solution path.

DSA Go

func solveMazeUtil(maze [][]int, x, y, n int, sol [][]int) bool {
    if x == n-1 && y == n-1 && maze[x][y] == 1 {
        sol[x][y] = [1]
        return true
    }
    if isSafe(x, y, n, maze) {
        sol[x][y] = 1
        // Move forward in x direction
        if solveMazeUtil(maze, x+1, y, n, sol) {
            return true
        }
        // Move down in y direction
        if solveMazeUtil(maze, x, y+1, n, sol) {
            return true
        }
        sol[x][y] = 0
        return false
    }
    return false
}

Drag options to blanks, or click blank then click option'

A-1

B1

C0

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Marking the cell as 0 which means not part of the path.

Marking the cell as 1 means it is part of the solution path.

3fill in blank

hard

Fix the error in the recursive calls to explore the maze directions.

DSA Go

if solveMazeUtil(maze, x+[1], y, n, sol) {
    return true
}
if solveMazeUtil(maze, x, y+[1], n, sol) {
    return true
}

Drag options to blanks, or click blank then click option'

A1

B-1

C0

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or negative numbers which do not move forward.

We move one step forward in x or y direction, so increment by 1.

4fill in blank

hard

Fill both blanks to initialize the solution matrix with zeros.

DSA Go

sol := make([][]int, n)
for i := 0; i < n; i++ {
    sol[i] = make([]int, [1])
    for j := 0; j < [2]; j++ {
        sol[i][j] = 0
    }
}

Drag options to blanks, or click blank then click option'

An

Blen(maze)

C0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or 1 which are incorrect sizes for the matrix.

The solution matrix is n x n, so both dimensions are n.

5fill in blank

hard

Fill all three blanks to print the solution path after solving the maze.

DSA Go

for i := 0; i < n; i++ {
    for j := 0; j < n; j++ {
        fmt.Print(sol[i][[1]], " ")
    }
    fmt.Println()
}

if solveMazeUtil(maze, 0, 0, n, sol) {
    fmt.Println("[2] found")
} else {
    fmt.Println("No [3] found")
}

Drag options to blanks, or click blank then click option'

Aj

Bsolution

Cpath

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using i instead of j for printing columns.

Wrong output messages.

Use j to print columns, and print 'path found' or 'No path found' messages.

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