Rat in a Maze Problem in DSA Javascript - 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 Javascript

function isSafe(x, y, maze) {
  return (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] === [1]);
}

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

A1

B0

C-1

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of 1 to check for open path.

Not checking boundaries properly.

The rat can move only to cells with value 1, which are open paths.

2fill in blank

medium

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

DSA Javascript

function solveMazeUtil(maze, x, y, solution) {
  if (x === maze.length - 1 && y === maze[0].length - 1) {
    solution[x][y] = [1];
    return true;
  }
  if (isSafe(x, y, maze)) {
    solution[x][y] = 1;
    // further code
  }
  return false;
}

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

A1

B0

C-1

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Marking with 0 which means no path.

Not marking the destination cell.

Marking the cell with 1 indicates it is part of the path to the destination.

3fill in blank

hard

Fix the error in the recursive call to move down in the maze.

DSA Javascript

if (solveMazeUtil(maze, x [1] 1, y, solution)) {
  return true;
}

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

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using -1 which moves up.

Using * or / which are invalid here.

To move down, increase the x coordinate by 1 using the + operator.

4fill in blank

hard

Fill both blanks to move right and backtrack correctly in the maze.

DSA Javascript

if (solveMazeUtil(maze, x, y [1] 1, solution)) {
  return true;
}
solution[x][y] = [2];

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

A+

B-

C0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using -1 to move right which is incorrect.

Marking backtracked cell as 1 instead of 0.

Moving right means increasing y by 1. Backtracking means marking the cell as 0 (not part of path).

5fill in blank

hard

Fill all three blanks to complete the main function that initializes and starts the maze solving.

DSA Javascript

function solveMaze(maze) {
  const solution = Array(maze.length).fill().map(() => Array(maze[0].length).fill([1]));
  if (!solveMazeUtil(maze, [2], [3], solution)) {
    return false;
  }
  return solution;
}

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

A0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing solution with 1s which marks all cells as path.

Starting from wrong coordinates.

The solution matrix is initialized with 0s. The starting point is (0, 0).

Practice

1. What is the main goal of the Rat in a Maze problem in 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 objective

   The Rat in a Maze problem requires finding a path from the start cell to the destination cell in a maze grid.

2. Step 2: Identify the correct goal

   The goal is not counting walls, sorting cells, or shortest distance in a graph, but specifically finding a valid path through the maze.

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: Focus on pathfinding from start to end in the maze [OK]

Common Mistakes:

• Confusing pathfinding with counting or sorting
• Thinking it's about shortest path always
• Assuming maze cells need sorting

2. Which of the following is the correct way to check if a cell (x, y) is safe to move in a maze represented by a 2D array maze in JavaScript?

easy

A. if (x >= 0 && y >= 0 && x <= maze.length && y <= maze[0].length && maze[x][y] === 0)

B. if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] === 1)

C. if (x > 0 && y > 0 && x <= maze.length && y <= maze[0].length && maze[x][y] === 1)

D. if (x > 0 && y > 0 && x < maze.length && y < maze[0].length && maze[x][y] === 0)

Solution

1. Step 1: Check boundary conditions correctly

   Valid indices in JavaScript arrays start at 0 and go up to length - 1, so conditions must use >= 0 and < length.

2. Step 2: Check cell value for path

   In the Rat in a Maze problem, 1 usually means path is open, so maze[x][y] === 1 is correct.

3. Final Answer:

   if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] === 1) -> Option B

4. Quick Check:

   Boundary + path check = if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] === 1) [OK]

Hint: Use >= 0 and < length for array bounds, check for 1 as path [OK]

Common Mistakes:

• Using > 0 excludes index 0
• Using <= length causes out-of-bound errors
• Checking for 0 instead of 1 as path

3. What will be the output of the following JavaScript code snippet for the Rat in a Maze problem?

const maze = [
  [1, 0, 0, 0],
  [1, 1, 0, 1],
  [0, 1, 0, 0],
  [1, 1, 1, 1]
];

function solveMaze(x, y, maze, path) {
  if (x === maze.length - 1 && y === maze[0].length - 1) {
    path.push([x, y]);
    return true;
  }
  if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] === 1) {
    path.push([x, y]);
    maze[x][y] = 0;
    if (solveMaze(x + 1, y, maze, path)) return true;
    if (solveMaze(x, y + 1, maze, path)) return true;
    path.pop();
    return false;
  }
  return false;
}

const path = [];
solveMaze(0, 0, maze, path);
console.log(path);

medium

A. [[0,0],[0,1],[1,1],[2,1],[3,1],[3,2],[3,3]]

B. []

C. [[0,0],[1,0],[1,1],[1,2],[2,2],[3,2],[3,3]]

D. [[0,0],[1,0],[1,1],[2,1],[3,1],[3,2],[3,3]]

Solution

1. Step 1: Trace the recursive path from (0,0)

   Starting at (0,0), the function tries moving down (x+1,y) first, then right (x,y+1). It marks visited cells as 0 to avoid revisiting.

2. Step 2: Follow the path found

   The path found is (0,0) -> (1,0) -> (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3), which is a valid path to the destination.

3. Final Answer:

   [[0,0],[1,0],[1,1],[2,1],[3,1],[3,2],[3,3]] -> Option D

4. Quick Check:

   Path traced matches [[0,0],[1,0],[1,1],[2,1],[3,1],[3,2],[3,3]] [OK]

Hint: Follow down moves first, then right moves recursively [OK]

Common Mistakes:

• Assuming right moves tried before down
• Not marking visited cells causing infinite loops
• Misreading maze cell values

4. Identify the bug in the following JavaScript code snippet for the Rat in a Maze problem and select the fix.

function solveMaze(x, y, maze, path) {
  if (x === maze.length - 1 && y === maze[0].length - 1) {
    path.push([x, y]);
    return true;
  }
  if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] === 1) {
    path.push([x, y]);
    if (solveMaze(x + 1, y, maze, path)) return true;
    if (solveMaze(x, y + 1, maze, path)) return true;
    path.pop();
    return false;
  }
  return false;
}

medium

A. Mark visited cells as 0 after pushing to path to avoid revisiting

B. Remove path.pop() to keep all visited cells in path

C. Change base case to check if x > maze.length and y > maze[0].length

D. Add a check to move diagonally (x+1, y+1) in recursion

Solution

1. Step 1: Identify missing visited marking

   The code does not mark visited cells as 0, so it may revisit the same cell causing infinite recursion.

2. Step 2: Fix by marking visited cells

   After pushing a cell to path, mark maze[x][y] = 0 to avoid revisiting and infinite loops.

3. Final Answer:

   Mark visited cells as 0 after pushing to path to avoid revisiting -> Option A

4. Quick Check:

   Visited marking fixes infinite recursion [OK]

Hint: Mark visited cells to prevent infinite loops [OK]

Common Mistakes:

• Forgetting to mark visited cells
• Removing path.pop() causing wrong paths
• Changing base case incorrectly

5. Given a maze represented by a 2D array where 1 means open path and 0 means blocked, how would you modify the Rat in a Maze algorithm to find all possible paths from start (0,0) to destination (n-1,n-1)?

hard

A. Use backtracking to explore all directions and store each complete path in a list

B. Stop recursion after finding the first path and return it immediately

C. Use a queue to perform breadth-first search and return the shortest path only

D. Mark all visited cells permanently to avoid revisiting any cell

Solution

1. Step 1: Understand the requirement to find all paths

   Finding all paths means exploring every possible route from start to destination without stopping at the first success.

2. Step 2: Use backtracking to explore all paths

   Backtracking allows exploring all directions, storing each valid path, and backtracking to try other routes.

3. Final Answer:

   Use backtracking to explore all directions and store each complete path in a list -> Option A

4. Quick Check:

   All paths require full backtracking exploration [OK]

Hint: Backtrack fully and save each path to find all solutions [OK]

Common Mistakes:

• Stopping after first path found
• Using BFS only for shortest path
• Marking visited cells permanently blocking other paths