Crio Projects - Rat in a Maze | Crio.Do | Project-Based Learning Platform for Developers

Objective

Create a simple web application using React that implements a novel way to visualize the famous Rat in a Maze Problem which can be solved using backtracking.

Project Context

The Rat in a maze is a famous problem in which we have a N x N matrix (the maze) which consists of two types of cells - one the rat can pass through and the other that the rat cannot pass through.


The objective of this problem is that the rat will be at a particular cell and we have to find all the possible paths that the rat can take to reach the destination cell from the given source cell.


Now you will be building a simple react application that will visualize all the possible paths on the web page.


While building this simple react app you will learn ES6 Javascript techniques, how to create react components and apply the Data Structures' and Algorithms' concepts such as Recursion and Backtracking.

Project Stages

The project consists of the following stages:

ratinamaze_task_list

High-Level Approach

  • Install and Setup React on your machine
  • Create React Components such as Maze.js and Cell.js for the project. These components will be simple functional components
  • Implement an algorithm for the Rat in a Maze problem using Backtracking
  • Finally, run the application to visualise the Rat in a Maze problem.

Project demo -


Objective

Create a simple web application using React that implements a novel way to visualize the famous Rat in a Maze Problem which can be solved using backtracking.

Project Context

The Rat in a maze is a famous problem in which we have a N x N matrix (the maze) which consists of two types of cells - one the rat can pass through and the other that the rat cannot pass through.


The objective of this problem is that the rat will be at a particular cell and we have to find all the possible paths that the rat can take to reach the destination cell from the given source cell.


Now you will be building a simple react application that will visualize all the possible paths on the web page.


While building this simple react app you will learn ES6 Javascript techniques, how to create react components and apply the Data Structures' and Algorithms' concepts such as Recursion and Backtracking.

Project Stages

The project consists of the following stages:

ratinamaze_task_list

High-Level Approach

  • Install and Setup React on your machine
  • Create React Components such as Maze.js and Cell.js for the project. These components will be simple functional components
  • Implement an algorithm for the Rat in a Maze problem using Backtracking
  • Finally, run the application to visualise the Rat in a Maze problem.

Project demo -


Getting Started

First validate the idea by doing a low level implementation (Proof of Concept) of the components involved in the project.This helps you to -

  1. Get more clarity around the unknowns.
  2. Get a better understanding of the stages involved in the project.

Explore various aspects of the terms mentioned in the preceding sections and also understand the preference to use React over Angular or Vue, all possible ways to solve the Rat in a Maze problem and challenge yourself by implementing other algorithmic problems in a similar illustrative method.


This task includes the setup you may follow to get started with this project.

Requirements

  • Ideally, this is a React app. So start by creating one and keep only the relevant files needed for the project (all essential files are shown below).

folder_structure

  • Install necessary dependency packages (you may refer and use the ones recommended below) using npm (or yarn). Research what each of the following packages/libraries are responsible for.

dependencies

  • Search for React dev tools in Chrome extensions and add them for your own testing purpose.

  • Use react developer tools throughout the project to debug your code better. If new to it refer this to understand how to use it. Also check this out!

Tip

  • To run the react application simply type npm start in the terminal and you will get a live server started (on localhost). Explore about this here

Bring it On!

  • Challenge yourself by using yarn instead of npm

Create the site’s main layout

In this task the basic structure of the web application is built (excluding the core functionality) using mainly React alongside HTML, CSS (optional).

Requirements

  • Visualise how the maze can be made on a blank canvas. We will have the main maze as one part (that will have the logic) and its cells as the other part that needs to be organised to create the maze.
  • Create the two components of the app i.e. the maze and the cell.
  • Create a custom component called Maze (preferably) which will be used to render cells as containers.
function Maze() {
     return (
        <div >
        // Write here the logic to create a N*N grid (maze) UI
        // Hint : You can use Material UI Grid and Box Components
        </div>
  );
}
  • To render a cell within a maze another component must be used.
function Cell(props) {
      return (
        <div >
        //  Write here the logic to create a cell UI
        //  Hint : You can use Material UI Grid and Paper Components
        </div>
  );
}
 
export default Cell;
 

Note

  • The red cells (obstacles) are randomly generated i.e. you have full liberty of choosing which all blocks they should be from the N*N maze grid. However, for a particular case the obstacles should be fixed and only change in the next case run.
  • Use cell.js file to create components for the cells.
  • Use maze.js file to create the components for the maze and inside it itself implement the algorithm (else create another file and import the functions, which may cause unnecessary cluttering ).

Expected Outcome

The basic UI of the app should look like this -

home1

Implement the core functionalities

Implement the core functionality of the problem's solution into the app, i.e. basically finding the paths. Here the paths will be from top left to bottom right for a maze with obstacles.


The constraints of the problem are :

  1. Rat can't go outside the maze
  2. Rat can't pass through the red cell (obstacle)
  3. Rat can go only 1 step (up, down, right, left) at a time.

Requirements

  • We need a calculatePath function to calculate all the paths from top left to bottom right cell of the maze. This function is solely responsible for the computation of the paths.
  • We need a loadCells function to load all cells of the maze. This function will be responsible for assigning the cells' roles.
  • The main function to be exported from maze.js will be used for the visualisation. So inside this main function (say function Maze()) you should be assigning the obstacle cells it's boolean value (i.e. 0) so that computation of green cells (paths) can be done.
  • Inside this main function you should call the calculatePath function to get the computation done and return the visualisations using loadCells function.
 
/**
 * Calculate all possible Maze paths
 * @param  {Array} matrix - row * column grid(Maze)
 * @param  {int} i - source initial row index
 * @param  {int} j - source initial column index
 * @param  {int} rows - total number of rows in grid
 * @param  {int} columns - total number of columns in grid
 * @return {Array} path - total possible paths
 */
function calculatePaths(matrix, i, j, rows, columns) {
     let paths = [];
      
    // Write here the logic to calculate all possible paths from top left of a grid (maze) to bottom right 
    
    return paths;
}
 
/**
 * Create all cells for a given maze
 * @param  {Array} mat - row * column grid(Maze)
 * @param  {int} rows - total number of rows in grid
 * @param  {int} columns - total number of columns in grid
 * @param  {int} gindex - a unique value for each maze
 * @return {Array} path - a single valid path
 * @return {Array} cells - all the cell components for a given maze.
 */
function loadCells(mat, rows, columns, gindex, path) {
    let cells = [];
    
    // Write here the logic to push cell to a grid with type(red = to indicate obstacle ,green = to indicate a possible path ,while = to indicate a possible passage)
    
    return cells;    
}

Tip

  • Use React Grid Components (material UI) to effectively deal with the grid cells.
  • Make sure the starting point (source cell), the obstacles (red cells), ending point (destination cell) and the possible paths (green cells) are rightly attributed while writing the algorithm.
  • Start with a case of which you know the solution to. Then once the app is working right you can try out random cases.

Note

  • Refer to the following packages and see how you can use it in your code.
  "@material-ui/core": "^4.11.2",
  "@testing-library/jest-dom": "^5.11.6",
  "@testing-library/react": "^11.2.2",
  "@testing-library/user-event": "^12.6.0",
  "react": "^17.0.1",
  "react-dom": "^17.0.1",
  "react-scripts": "4.0.1",
  "web-vitals": "^0.2.4"

Bring it On!

  • Implement your own methods to solve this problem and implement the visualisation for that solution.

Expected Outcome

Now that the core functionalities are implemented the web app is ready. So the web app rendered should look something like this.

home2)

Publish your work to GitHub and host your website live

Finish your work in complete style.


Publish your work on GitHub with proper folder structure and a good README for people to get to know of your work. Make sure you add a .gitignore file and mention all dependency folders like node_modules in it.


Since this is a React application, go one step further by using a hosting service like Heroku, Firebase or Netlify to host your app and get a live URL.


Share this link among your peers and add this project (with the link and proper documentation) to your resume and voila, you have just boosted your resume.

Bring it on!

  • Try implementing this puzzle now. Explore all such famous algorithmic problems and develop visualisations for them.