Challenge - 5 Problems
Maze Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
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));Attempts:
2 left
💡 Hint
Trace the path by moving down first, then right, marking visited cells.
✗ Incorrect
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
intermediate1:00remaining
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?
Attempts:
2 left
💡 Hint
Check the common constraints in classic Rat in a Maze problems.
✗ Incorrect
The classic Rat in a Maze problem allows the rat to move only down or right to simplify the pathfinding and avoid cycles.
🔧 Debug
advanced2:00remaining
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));
Attempts:
2 left
💡 Hint
Check if the code marks visited cells to avoid revisiting.
✗ Incorrect
The code does not mark visited cells as blocked, so it revisits the same cells repeatedly causing infinite recursion and stack overflow.
🚀 Application
advanced1:30remaining
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?
Attempts:
2 left
💡 Hint
Count all possible routes avoiding blocked cells moving only down or right.
✗ Incorrect
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
expert2:30remaining
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));
Attempts:
2 left
💡 Hint
The code tries moving right first, then down.
✗ Incorrect
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).