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

function ratInMaze(maze: number[][], n: number): string[] {
  const path: string[] = [];
  function solve(x: number, y: number): boolean {
    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) {
      maze[x][y] = 0; // mark visited
      path.push(`${x},${y}`);
      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, 4));

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

B ["0,0","1,0","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 ["0,0","0,1","1,1","2,1","3,1","3,2","3,3"]

💡 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), down to (3,1), right to (3,2), and finally right to (3,3). This is the only valid path through cells with value 1.

🧠 Conceptual

intermediate

Understanding Rat in a Maze Movement Constraints

In the Rat in a Maze problem, which movement directions are typically allowed for the rat to find a path?

A Diagonal moves only

B Up, Down, Left, Right

C Down and Right only

D Up and Left only

💡 Hint

Check the common constraints in classic Rat in a Maze problems.

The classic Rat in a Maze problem allows the rat to move only down or right to simplify the pathfinding and avoid cycles.

🔧 Debug

advanced

Identify the Bug in Maze Pathfinding Code

What error will the following TypeScript code produce when run, and why? function ratInMaze(maze: number[][], n: number): string[] { const path: string[] = []; function solve(x: number, y: number): boolean { 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, 1], [1, 1] ]; console.log(ratInMaze(maze, 2));

A Runtime error: Cannot read property of undefined

B Correct output: ["0,0","1,0","1,1"]

C Empty path returned []

D Stack overflow due to infinite recursion

💡 Hint

Check if the code marks visited cells to avoid revisiting.

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

🚀 Application

advanced

Number of Paths in a Maze with Obstacles

Given a 3x3 maze represented as a grid where 1 is open and 0 is blocked: [[1,1,0], [1,1,1], [0,1,1]] How many unique paths exist from top-left (0,0) to bottom-right (2,2) moving only down or right?

A 3

B 2

C 4

D 1

💡 Hint

Count all possible routes avoiding blocked cells moving only down or right.

The paths are: 1) (0,0)->(1,0)->(1,1)->(1,2)->(2,2) 2) (0,0)->(0,1)->(1,1)->(1,2)->(2,2) 3) (0,0)->(0,1)->(1,1)->(2,1)->(2,2) Total 3 paths.

❓ Predict Output

expert

Output of Rat in Maze with Backtracking and Multiple Paths

What is the output of the following TypeScript code that finds one path in a 4x4 maze with multiple possible routes? function ratInMaze(maze: number[][], n: number): string[] { const path: string[] = []; function solve(x: number, y: number): boolean { 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) { maze[x][y] = 0; // mark visited path.push(`${x},${y}`); if (solve(x, y + 1)) return true; if (solve(x + 1, y)) return true; path.pop(); maze[x][y] = 1; // backtrack } return false; } solve(0, 0); return path; } const maze = [ [1, 1, 0, 0], [0, 1, 1, 0], [0, 0, 1, 1], [0, 0, 0, 1] ]; console.log(ratInMaze(maze, 4));

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

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

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

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

💡 Hint

The code tries moving right first, then down.

The rat moves right first from (0,0) to (0,1), then down to (1,1), right to (1,2), down to (2,2), right to (2,3), and finally down to (3,3).