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

function ratInMaze(maze) {
  const n = maze.length;
  const path = [];
  function solve(x, y) {
    if (x === n - 1 && y === n - 1) {
      path.push([x, y]);
      return true;
    }
    if (x >= 0 && y >= 0 && x < n && y < n && maze[x][y] === 1) {
      path.push([x, y]);
      maze[x][y] = 0; // mark visited
      if (solve(x + 1, y)) return true;
      if (solve(x, y + 1)) return true;
      path.pop();
      maze[x][y] = 1; // backtrack
    }
    return false;
  }
  solve(0, 0);
  return path;
}

const maze = [
  [1, 0, 0, 0],
  [1, 1, 0, 1],
  [0, 1, 0, 0],
  [1, 1, 1, 1]
];
console.log(ratInMaze(maze));

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

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

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

D []

💡 Hint

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

The rat starts at (0,0). It moves down 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).

🧠 Conceptual

intermediate

Understanding Backtracking in Rat in a Maze

Which statement best describes the role of backtracking in the Rat in a Maze problem?

A Backtracking ensures the rat only moves right and down to reach the destination.

B Backtracking allows the rat to undo moves when it hits a dead end and try alternative paths.

C Backtracking is used to find the shortest path by exploring all possible routes simultaneously.

D Backtracking helps the rat remember all visited cells to avoid loops.

💡 Hint

Think about what happens when the rat cannot move forward.

Backtracking means the rat goes back one step when it cannot proceed further, trying other possible paths until it finds the exit.

🔧 Debug

advanced

Identify the Error in Maze Solver Code

What error will the following code produce when executed?

DSA Javascript

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

const maze = [
  [1, 0, 0],
  [1, 1, 0],
  [0, 1, 1]
];
console.log(ratInMaze(maze));

A Infinite recursion causing stack overflow

B TypeError: Cannot read property '0' of undefined

C Correct output: [[0,0],[1,0],[1,1],[2,1],[2,2]]

D ReferenceError: path is not defined

💡 Hint

Check if the visited cells are marked to prevent revisiting.

The code does not mark visited cells as blocked, so it revisits the same cells repeatedly, causing infinite recursion.

🚀 Application

advanced

Number of Paths in a Maze with Obstacles

Given a maze represented by a 2D grid where 1 is open and 0 is blocked, how many unique paths exist from top-left to bottom-right if the rat can only move right or down?

DSA Javascript

function countPaths(maze) {
  const n = maze.length;
  const m = maze[0].length;
  const dp = Array.from({ length: n }, () => Array(m).fill(0));
  if (maze[0][0] === 0) return 0;
  dp[0][0] = 1;
  for (let i = 1; i < n; i++) {
    dp[i][0] = maze[i][0] === 1 ? dp[i - 1][0] : 0;
  }
  for (let j = 1; j < m; j++) {
    dp[0][j] = maze[0][j] === 1 ? dp[0][j - 1] : 0;
  }
  for (let i = 1; i < n; i++) {
    for (let j = 1; j < m; j++) {
      if (maze[i][j] === 1) {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      } else {
        dp[i][j] = 0;
      }
    }
  }
  return dp[n - 1][m - 1];
}

const maze = [
  [1, 1, 0],
  [1, 1, 1],
  [0, 1, 1]
];
console.log(countPaths(maze));

A 2

B 1

C 4

D 3

💡 Hint

Use dynamic programming to count paths from top-left to bottom-right.

The rat can move right or down only. The code counts all unique paths avoiding blocked cells. The total paths are 3.

❓ Predict Output

expert

Output of Rat in Maze with Multiple Paths

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

DSA Javascript

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

const maze = [
  [1, 1, 1],
  [0, 1, 0],
  [1, 1, 1]
];
console.log(ratInMaze(maze));

A [[0,0],[0,1],[0,2],[1,2],[2,2]]

B [[0,0],[1,0],[2,0],[2,1],[2,2]]

C [[0,0],[0,1],[1,1],[2,1],[2,2]]

D [[0,0],[1,0],[1,1],[2,1],[2,2]]

💡 Hint

The rat tries moving right first, then down.

The rat moves right along the top row, then down at (0,1) to (1,1), then down to (2,1), and finally right to (2,2).

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