Encryption involves converting plain, readable data into an incomprehensible form. It's also essential to have a way to convert the data back into a readable form – otherwise the whole process makes no sense and isn't useful.

There are various popular encryption algorithms, each with its strengths and weaknesses. Understanding how these algorithms work is essential for programmers, as they need to choose the most appropriate one for their applications.

In this article, we will be build an application where users can encrypt images, and also revert the process using HTML, CSS, and JavaScript.

You will learn about working with images and how to encrypt them. The approach we will be using involves hiding one image inside another one, which is called Steganography. You will also practice some basic web development skills. It will be fun for sure!

Here's what we'll cover:

• How images are represented on your computer
• How to create the encryption algorithm
• How to create the decryption algorithm
• Photo encryption app code

How Images Are Represented on Your Computer

Understanding the way images are stored is critical before diving into encrypting them.

Images are represented on computers using a combination of pixels. A pixel is the smallest unit of an image and serves as the building block for displaying visuals on digital screens.

In memory, an image is an array of pixels. But now you're probably wondering, what is a pixel?

A pixel is assigned a specific color value which determines its appearance. The color values are typically represented using a combination of three primary colors: red, green, and blue – commonly known as RGB.

Each color channel is represented by a number value, ranging from 0 to 255, which determines the intensity of that color in the pixel.

For example:

• (0, 0, 0) represents black (absence of all colors)
• (255, 255, 255) represents white (maximum intensity of all colors)
• (255, 0, 0) represents pure red (maximum intensity of red, absence of green and blue)
• (0, 255, 0) represents pure green (maximum intensity of green, absence of red and blue)
• (0, 0, 255) represents pure blue (maximum intensity of blue, absence of red and green)

By combining different intensities of red, green, and blue, we can represent a wide range of colors. This color information for each pixel is stored in memory, forming a digital image. For example to get yellow, we can combine red and green – (255, 255, 0) represents a yellow pixel.

How to Use the Encryption Algorithm

The key idea behind the algorithm we're going to use is that it uses 2 images: the image we want to encrypt and an image that will play the role of mask used to hide the image we want to encrypt. So we're going to combine these two images in a way that hides our main image and allows its extraction.

Since an image is made of pixels, what works for a single pixel works for an entire image. We will discuss how we will be combining 2 pixels in a way that hides one and allows reverting the process.

Now for the interesting part: if we look at numbers from 0 to 255, they all can be written as follows: a 16 + b. For example 241 can be written as 15 16 + 1. But why we are doing this?

We will be using this to divide each pixel into two parts: first the a * 16 part and second b. The first part holds way more information than the second, since when a color degree goes up its intensity goes up. For example a (245, 137, 200) pixel can be split into (240, 128, 192) and (5, 9, 8).

Image splitting

Now by comparing the high value pixel and the original one, you can see clearly that using the higher value pixel instead of the original one isn't going to change much of the information the original pixel holds.

Comparing a higher value pixel and an original pixel's values

Now we will be using two pixels – one we're going to encrypt (the target pixel), and one we're going to hide the target pixel within (the encryption pixel), which can be random as we will see later.

First we will get the high value pixel from our target and encryption pixels. Then for the pixel we're trying to encrypt, we'll divide each number degree by 16.

For example if the original target pixel was (245, 137, 200) then the high value pixel will be (240, 128, 192) which will become (15, 8, 12) after applying a division by 16.

Getting initial values and applying division

Now we have two new pixels: the high value pixel of the encryption pixel, and our target pixel high value pixel that got divided by 16.

Finally, to get an encrypted pixel, we'll sum up the values of these two pixels to get what we're looking for.

Take, for example, (26, 98, 234) and (245, 137, 200) as our encryption and target pixels, respectively. Let's first get the high value pixels. We will have (16, 96, 224) and (240, 128, 192), respectively.

Now divide the target pixel high value pixel by 16 and you'll have (15, 8, 12). Now add these two up and you'll be left with (31, 104, 236). And that's our encrypted pixel.

Encrypted image

Now you know how to encrypt a pixel. By applying this to all the pixels of an image we will get an encrypted image.

To make this clearer, we will be hiding an image of Quincy Larson playing guitar within the freeCodeCamp logo 😂.

Image showing how we were able to hide Quincy Larson image in the freeCodeCamp logo

So to make this work we need two images: the one we need to encrypt and a random image to use as the encryption image. Also the two images should have the same dimensions to get the same number of pixels.

The reason we're using a random image to hide our image is to make it look like a very random image that will make no one suspicious.

How to Use the Decryption Algorithm

Now we need a way to revert the process, so to extract the target pixel from an encrypted pixel. Then we will have accomplished our goal.

Like we did earlier by combining 2 pixels to get an encrypted pixel, we will split back the encrypted pixel to get our target.

Every pixel can be split into two parts – the high value part (a * 16) and the low value part (b). Now we care about the b part since it comes from our target pixel. So we need to extract the b part from an encrypted pixel.

We can do this easily by mapping each number with its corresponding remainder of division by 16. We can do this using the modulo operator % which is a mathematical operator to get the remainder of the division of a number by another. For example 241 % 16 is 1 since since 241 is equal to 15 * 16 + 1.

By taking (31, 104, 236) and applying the modulo, we will be left with (15, 8, 12). As discussed earlier an encrypted pixel is the sum of the high value pixel of our encryption pixel or the mask pixel and the high value pixel of our target divided by 16. After the modulo is applied, the left value is the high value pixel of our target divided by 16.

Now multiply each number by 16 and you'll get exactly (240, 128, 192) which is the high value pixel of our target pixel.

Decryption

Now as you can see, Steganography involves a small loss of each target pixel's information – but it's ok as you can see that it doesn't matter much in how the final image looks.

Photo Encryption App Code

And now since our toolkit is ready, let's code this image encryption application. All the code is available in this GitHub repo. The code itself is very straightforward.

First, create three files: an HTML file, a CSS file, and a JavaScript file.

For the HTML file we just need a canvas where we can see the resulting image. We also need two inputs of type file so we can upload our target and encryption images. And finally we need a button to save our encrypted image.

Also we will be using a small library to manage images created by Duke University, so we will have to include a script tag in the end of the body for this.

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Image encryption app</title>
    <link rel="stylesheet" href="index.css">
</head>
<body>
    <div class="container">
       <canvas></canvas>
    </div>
    <div class="input-container">
        <label for="Target">Upload target image</label>
        <input type="file" id="target" mltiple='false' accept='image/*'>
    </div>
    <div class="input-container">
        <label for="Encryption">Upload encryption image</label>
        <input type="file" id="encryption" multiple='false' accept='image/*'>
    </div>
    <button>Save image</button>
    <script src='https://www.dukelearntoprogram.com/course1/common/js/image/SimpleImage.js'></script>
    <script src="index.js" type="text/javascript"></script>
</body>
</html>

The CSS is simple too. We will give the div wrapping the canvas a width and height of 300px, the canvas a width and height of 100%, and it'll have a black border. Now the div tags wrapping our inputs will get a slight margin of 10px on the top, and that's it.

.container{
  width:300px;
  height: 300px;
}

canvas{
  width:100%;
  height:100%;
  border:1px solid black;
}

.input-container{
    margin-top: 10px;
}

Now for the JavaScript file. We will first select the two inputs, the canvas and the save button, and store them in four different variables. Then we will set the canvas width and height to 300px with JavaScript to avoid any future problems. And finally we'll set two variables, target and encryption, to store our encryption and target images.

const canvas = document.querySelector("canvas");
const targetInput = document.querySelector("#target");
const encryptionInput = document.querySelector("#encryption");
const saveButton = document.querySelector("button");
let target;
let encryption;

canvas.width = 300;
canvas.height = 300;

Now we need to store the encryption and target images on user upload in the two variables we created earlier. Also set the onClick event of our save button to a function called save that we will create next. Finally, we'll create a function that takes a number as an argument and returns its high value as discussed in the encryption algorithm section.

targetInput.onchange = (e) => {
  const img = new SimpleImage(targetInput);
  img.setSize(300, 300);
  target = img;
};

encryptionInput.onchange = (e) => {
  const img = new SimpleImage(encryptionInput);
  img.setSize(300, 300);
  encryption = img;
};

saveButton.onclick = save;

function getValue(x) {
  return x - (x % 16);
}

All that's left is to create the save function. First we will create a new image object with dimensions of 300 * 300. An image with these dimensions will have 90000 pixels. All of them have x and y coordinates from 0-299, since indexing starts from 0 in arrays. Looping from 0 to 300 twice will allow us to get all possible coordinates which means all pixels.

Now for each coordinate we will use the corresponding pixel of our encryption, target, and newly created image. Now we can set each pixel of our newly created image to the sum of the high value pixel of the encryption pixel and the high value pixel of our target divided by 16.

Now we will draw the newly created pixel on the canvas. And we'll need to get the URL of the image drawn into the canvas. We will be applying a small modification to the URL otherwise it will not work because we will get blocked by the browser for security reasons.

Finally, navigate to this URL by setting the window location to that URL. Then the encrypted image will be downloaded.

function save() {
  const img = new SimpleImage(300, 300);
  for (let i = 0; i < 300; i++) {
    for (let j = 0; j < 300; j++) {
      const targetPixel = target.getPixel(i, j);
      const encryptionPixel = encryption.getPixel(i, j);
      const pixel = img.getPixel(i, j);
      pixel.setRed(
        getValue(targetPixel.getRed()) / 16 + getValue(encryptionPixel.getRed())
      );
      pixel.setGreen(
        getValue(targetPixel.getGreen()) / 16 +
          getValue(encryptionPixel.getGreen())
      );
      pixel.setBlue(
        getValue(targetPixel.getBlue()) / 16 +
          getValue(encryptionPixel.getBlue())
      );
    }
  }
  img.drawTo(canvas);
  let url = canvas
    .toDataURL("image/png")
    .replace("image/png", "image/octet-stream");
  window.location.href = url;
}

And that's it for the code 😇.

Conclusion

In this article, we've learned a simple algorithm for image encryption. Modern algorithms are way more robust, as they use techniques like matrix multiplication to get solid hashing algorithms but they are very complex and require way more time and math knowledge than this one.

If you find this content enjoyable, follow me on LinkedIn as I post great content there 😉.

The problem is that many developers learn JavaScript in a very short period of time, without understanding some of the most essential features of the language.

In this article, we will cover JavaScript arrays, strings, and objects in depth so you can benefit from some of the most effective static and instance methods that the language offers.

Here's what we'll cover in this guide:

• Instance and class methods
• How to use strings in JavaScript
• How to use arrays in JavaScript
• How to use objects in JavaScript

Instance and Class Methods

JavaScript is heavily object-oriented. It follows a prototype-based model, but it also offers a class syntax to enable typical OOP paradigms.

In JavaScript, strings and arrays are objects, and every object in JavaScript is a template which has its methods and properties. Every object inherits methods and properties from its prototype. In JavaScript, every object has access to the Object prototype.

Static methods are methods that are available on the class level – for example the Object.freeze() method. Instance methods are available on the instance level – for example a created instance of an Array object has access to the instance methods such as .join(), but not the static methods.

How to Use Strings in JavaScript

Strings are used to hold data that can be represented in text form. To create a string you can use the String() constructor or a string literal. Here's an example of both ways:

 // Using a constructor

let string1 = String('String Creation');

 // Using a string literal

let string2 = 'String Creation';

Now let's learn more about instance methods. There are many instance methods, but here I'll discuss seven methods that I consider the most important.

The .charAt() method

A lot of the time when working with strings, we want to access a character at a certain index of the string. You can do this either with the charAt() method or with indexing, the same way we treat an array.

 // Let's say we want to access the first character of a given string

 let string = 'Hello World';

  // using indexing

 let first1 = string[0]; // output 'H' and remember that indexing starts at 0

  // using the charAt() method

 let first2 = string.charAt(0); // output 'H'

In JavaScript, the indexing system starts at 0 – for example the first character of a string has index of 0 and so on.

The .toUpperCase() and .toLowerCase() methods

Now let's say we want to uppercase or lowercase a string. You can do this using the toUpperCase() and the toLowerCase() instance methods.

 let string = 'Hello';

  // Let's lowercase a string

 let lowerCase = string.toLowerCase(); // output 'hello'

  // Let's upperCase a string

 let upperCase = string.toUpperCase(); // output 'HELLO'

You might use these to see if two strings hold the same word, for example 'Sam' and 'sam'. Actually 'sam' === 'Sam' evaluates to false, while 'sam'.toLowerCase() === 'Sam'.toLowerCase() evaluates to true.

The .concat() method

It is often necessary to join text strings together in a program to make a new text string. This is called concatenation.

Now for string concatenation we can use the concat() method. It looks like the following. An important note is that this method returns a new string without mutating the original one.

let string = 'Hello';

 // String concatenation using the concat method

let string1 = string.concat(' World'); // output 'Hello World'

The .indexOf() method

Now to find the index of a certain character or a set of characters of a string, we can use the indexOf() method. This will return the index of the first index where the passed character or set of characters occurs.

let string = 'Hello World';

 // Let's find the index where 'H' occurs for the first time

let firstH = string.indexOf('H'); // output 0

 // Let's find the first index where 'World' occurs for the first time

let firstWorld = string.indexOf('World'); // output 6

 // In case a character or a set of characters   
 // doesn't occur in the string this method returns -1

let notThere = string.indexOf('Z'); // output -1

The .slice() method

A substring is a subset or part of another string, or it is a contiguous sequence of characters within a string. For example, "Substring" is a substring of "Substring in JavaScript".

Now let's say we want to get a substring of a given string. We can use the slice() method. Slice is actually one of the most important string methods. You use it to get substrings and also to copy strings.

Slice takes two optional parameters: the first one is where we want to start slicing and the second one is where we want to finish the slicing operation.

Let's assume that we passed 1 and 10 as parameters for the slice method. The method will then return a substring starting at index 1 and ending at index 9.

This means that the substring never includes the character at the ending index. An important note is to never pass an ending index higher than the string length.

let string = 'Hello World';

 // to check the string length we can use the length instance property

let length = string.length; // output 11

 // slicing to get the substring from index 1 -> 9

let string1 = string.slice(1 , 10); // output 'ello Worl'

 // not passing any parameters will generate 
 // a copy of the ariginal string with no mutation

let copy = string.slice(); // output 'Hello World'

The .split() method

The last string method that we will cover is the split() method. This method takes a pattern as an argument and divides the string into multiple substrings. The pattern describes where the splits occurs. This method returns an array of these substrings.

You might find yourself using this method to parse a URL or certain strings.

let string = 'Hello World';

 // Divide a string into words
 // This can be done when the passed pattern is a space

let words = string.split(' '); // output ['Hello' , 'World']

 // When the passed parameter is an empty string, the output array
 // will carry each of the characters of the given string

let chars = string.split(''); 

 // output ["H","e","l","l","o"," ","W","o","r","l","d"]

There are many more methods you can learn about, but these are the ones that you will work with the most. You can learn more by reading through the official MDN web documents.

How to Use Arrays in JavaScript

Like other programming languages, JavaScript arrays let you store a collection of data under one variable. But unlike C or C++, arrays can be returned from function calls.

JavaScript arrays are dynamic, so you can add to or delete elements from an array. You can also have elements of multiple data types in a single array.

Let's talk about how to create arrays in JavaScript. You can easily create an array by assigning a variable to empty brackets [ ] or by using the Array() constructor.

 // Creating an array from constructor

let arr1 = Array();

 // Prefered method

let arr2 = [];

Now let's talk about seven array instance and class methods that I consider to be the most useful.

The .indexOf() method

To get the first index of a given array where an element occurs, we can use the indexOf() method. It'll look like this. If the argument passed to this method doesn't occur in the array, it will return -1.

let array = [1, 2, 3];

 // Let's find the index where 1 occurs for thwe first time

let first1 = array.indexOf(1); // output 0

 // Now let's try to find 4 in the array

let first4 = array.indexOf(4); // output -1

The .push() and .pop() methods

As I mentioned earlier, JavaScript arrays are dynamic. So we can add elements using the push() method and remove the last element using the pop() method. An important note is that both of those methods mutate the original array.

let array = [1, 2, 3];

 // let's add 4 to the array

array.push(4)

console.log(array) // output [1, 2, 3, 4]

 // let's now make the array the same as before

let removedElement = array.pop() // output 4

console.log(array) // output [1, 2, 3]

Now we'll discuss some more advanced methods – the ones introduced by the ES6 update.

The .map() method

First, let's say that you want to create an array using data from another existing array – for example if you have an array of objects representing employees.

Each employee object has a name property. And you want to create an array where each element is the value of the name property of the employee object at the same index of the array you have.

This is where the map() method comes in. It takes a callback function. Map creates a new array and never mutates the old one, and the callback expresses what you want to do with the data from the original array. It will look like this:

let arr= [{name : 'joe'} , {name : 'john'}];

 // It is preffered to use an arrow function

let namesArr = arr.map(elem => elem.name); // output ['joe' , 'john']

The .forEach() method

Are you tired of the usual for loops? They are kind of boring, I know. Luckily the forEach() method is here to help.

This method takes a callback as an argument and returns nothing. It iterates over the array and runs a certain task on every element of the array. The callback expresses the task. The code for this will look like this:

let arr= [1, 2, 3];

 // let's output each element on the console

arr.forEach(elem => console.log(elem));

 // output 
 // 1
 // 2
 // 3

The .filter() method

Now let's say that we have an array of numbers and that we want to create an array of only the numbers that pass a certain condition.

In this case we can use the filter() method which also takes a callback as an argument. The callback returns a Boolean – true if the element passes the test, otherwise false. Only elements that pass will be in the generated array and the callback expresses the test. Here's how it works:

let arr = [1, 2, 3, 4, 5];

 // Let's create an array of numbers bigger than 3

let filteredArray = arr.filter(elem => elem > 3); // output [4, 5]

The .some() method

Now let's say we have an array, and we want to check if there is at least one number that passes a certain test. Here comes the some() method.

This method takes a callback as an argument and returns a Boolean which is true if at least one element of the array passes the test, and otherwise is false. The callback expresses the test and it will look as follows:

let arr = [1, 2, 3, 4, 5];

 // Let's check if at least one element is bigger than 4

let bool = arr.some(elem => elem > 4); // output true

The .sort() method

Sorting is the process of arranging data into a meaningful order so that you can analyze it more effectively.

When talking about arrays we have to mention sorting. In JavaScript the sort() method sorts arrays in place and returns the reference to the same array. This method mutates the array and the default sorting order is ascending.

You can implement your own sorting logic by passing a callback which expresses a comparison between two elements and returns a number. If the returned number is positive then the first of the two compared elements will occur first in the sorted array.

let arr = [1, 2, 4, 3];

 // sorting in ascending order

arr.sort();

console.log(arr); // [1, 2, 3, 4]

 // using custom sort to sort in descending order

arr.sort((elem1 , elem2) => elem2 - elem1);

console.log(arr); // output [4, 3, 2, 1]

There are plenty of interesting string methods that I didn't mention and they are worth investing time in learning. If you want to do so, you can visit the MDN official documents.

How to Use Objects in JavaScript

If you want to be a good JavaScript developer, you should really have a decent understanding of objects and the way they work.

Almost every object you create in JavaScript inherits methods from the global Object prototype which is available globally for every object in JavaScript. An exception is null prototype objects which we're not going to talk about. All the methods I am going to talk about are mostly static.

First let's talk about how to create objects using a set of curly braces { } or the object constructor. Here's what that looks like:

 // Creating an object from an constructor

let obj1 = Object();

 // Creating an object using curly braces

let obj2 = {};

The .assign() method

Now let's say we want to copy an object. Here comes the assign() static method to help us do this. I will show you how this works and a better way to do it. I'll also discuss some common mistakes many devs make when trying to copy objects.

let obj = {age : 18};

 // Copying using the assign method

let new1 = {};

Object.assign(new1 , obj);

console.log(new1); // output {age : 18}

 // We can do the same with the spread operator

let new2 = {...obj}; // output {age : 18}

A common mistake is to assign a variable to an object directly. The problem with this is that objects are assigned by reference and not by value. So any changes will mutate the original object.

let obj = {age : 18};

let obj1 = obj;

obj1.age = 17;

console.log(obj); // output {age : 17}

The .freeze() and .isFrozen() methods

Let's now say that we want to make an object immutable. For this we can use the freeze() static method which makes it impossible to add properties, modify, or delete any of the frozen object's prototypes, methods, and properties.

To see if an object if frozen, we can use the isfrozen() static method.

let obj = {age : 18};

Object.freeze(obj);

 // Let's try to mutate this object

obj.age = 17; // Throws an error in strict mode

let isFrozen = Object.isFreezed(obj); // output true

The .keys() and .values() methods

Now to get a list of a certain object properties we can call the keys() static method. To get a list of the values corresponding to its properties, we can call the values() static method. An important note is that the list is an array.

let obj = {name : 'John Doe' ,age : 45};

let keys = Object.keys(obj); // output ['name', 'age']

let values = Object.values(obj); // output ['John Doe', 45]

You can check the MDN web documents to dive deeper into the topic.

Conclusion

In this tutorial, we talked about arrays, strings, and objects, along with the methods they offer. Hopefully you learned something new today.

In case you're interested in more great content like this, follow me on LinkedIn where I share a lot of great content.

In this tutorial we will learn about the Minimax algorithm. It is a backtracking algorithm that is used in decision making and game theory. It finds the optimal move for a player, assuming their opponent also plays optimally. It is widely used in two-player turn-based games.

You will learn how to create your own AI that plays any of the games mentioned above or any other similar games. Also, to make this as comprehensible as possible, I will be applying the algorithm to a Tic-Tac-Toe game.

We will not cover the whole process of creating the game, but only the part related to AI since this is our topic. If you're interested in the game-creating process, you can check out this Tic-Tac-Toe game that uses AI and its source code on GitHub. It's a project that I built long ago but it's still one of my favorites.

Table of contents

• How the minimax algorithm works
• Limitations of the minimax algorithm
• How to improve the time complexity of the algorithm
• Tic-Tac-Toe AI Code
• Conclusion

How the Minimax Algorithm Works

The minimax algorithm's methodology is quite simple. First, it checks all the possible combinations from a given position. Then it chooses the best possible move that maximizes the chances of winning, assuming that both players play perfectly.

To illustrate this, let’s consider a Tic-Tac-Toe game to make this more convincing. As you might know, in this game there are 2 players and 9 available slots. So we can represent a game by using an array of length 9.

Now let's take this board as an example: as you can see, a game board is an array of length 9 whose values can be either X, O, or an empty string. An empty string means this position is still available.

Board array to game board

Now it's X's turn. The minimax algorithm will try all the game combinations from this position. Then it'll try all the game combinations from the resulting child positions until reaching a position where the game ends by either X winning, O winning, or a draw (which occurs when the board is full and no one is winning).

This picture illustrates how this works:

All game combinations demo

We can achieve this using recursion. I will show the code at the end, but for now, let's focus on understanding how we can process the game combinations to get the optimal move. We will consider these cases:

• The board which has a winning position for X is valued by 1 point
• The board which has a winning position for O is valued by -1 point
• The board where the position is a draw has 0 points

If we're finding the optimal move for X, we should find the board with the most points. But what if a board isn't finished yet? Then we should choose a board depending on its child boards – but which do we choose?

I need you to focus on this part, as it's the most important part. When I introduced the algorithm I said that it finds all the game combinations assuming both players are playing optimally.

After the first generation of child boards, it will be O's turn. With the assumption that O is playing optimally, we should choose a board where O is doing his best that is one of the boards with the fewest points (since when O wins, the board returns -1).

Why are we choosing like this? Imagine if we pick the maximum value when it's O's turn, then we're letting X win. This makes the algorithm useless, since we need to assume O plays optimally.

For the 3rd generation, the player is X again and we will choose the board with the most points once more.

This alternating method of choosing the maximum and the minimum values is the reason why this algorithm is called the Minimax algorithm. Check out this visualization for further clarification:

Minimax mechanism

This is the same example given above. The 2 boards at the bottom are winning for X, so each will return a value of 1. Here, it’s X’s turn so we will pick the optimal value - it happens that both boards have a value of 1 here.

As I said earlier, if a board doesn't satisfy winning or drawing conditions, we will look at its child boards. That's why the parents of the boards with value 1 will have a value of 1.

Minimax algorithm mechanism

Here it's O's turn so we will pick the lowest possible value which happens to be 1. I've chosen this specific example to make things simple, but this works on all boards.

Minimax mechanism

Finally it's X's turn again and we will maximize the value of the chosen board. That’s why we can choose the child board on the left or the one on the right or the one in the middle – it doesn’t matter since their values are the same.

In the end, the optimal move for X to maximize its winning chances is in positions 7, 8 or 9. If you're still not convinced, take any board combination and draw the combination tree and you'll get a satisfying result - I strongly recommend drawing this on paper.

Limitations of the Minimax Algorithm

As you've seen, the algorithm is recursive and the number of executions may become huge.

For example, for a Tic-Tac-Toe game the number of executions is approximately “9!”(9 factorial). The reason why is for the first move there are 9 possibilities and then for each subsequent move there are 8 and so on.

That's not a problem for tic-tac-toe, but consider a chess game. If we were to write the number of combinations, the entire universe would not be enough. So the minimax is often used as part of an engine but it’s not enough to fulfill our needs.

How to Improve the Time Complexity of the Algorithm

You may have noticed that using this approach may result in some repetitive boards and that we need to compute their value multiple times. So why not store the value of every board when calculated?

So now, for every iteration, we will check if a position has already occurred. If so, we will use its stored value. Else, we can compute the value of the position and then store it.

For storing values, we will use a dictionary which allows searching in O(1). Using this approach we can reduce the time complexity – but still, it wouldn't be efficient in some cases.

I’ve built a Connect 4 game with this algorithm and it was horrible in terms of runtime. So, instead of looking for all the combinations, I stopped at a certain depth which led to an AI that can see n moves ahead.

If you're interested, check out this GitHub repository for the Connect 4 game code. I wrote it a long time ago but it's cool to see.

Tic-Tac-Toe AI Code

Now let's implement some helper functions first. We will first check if there are 3 horizontal, vertical, or diagonal non-empty string values in the board array.

// Board array
let xo=['','','',
        '','','',
        '','','']

// Writing this function we need to make sure the equal values are not empty strings

// Before this I will write a helper function to make sure 3 indexes have no empty strings

function helper(index1,index2,index3){
  return xo[index1] !='' && xo[index2] !='' && xo[index3]!=''
}



function checkwin(){

   return (xo[0]==xo[1] && xo[1] ==xo[2] && helper(0,1,2)) ||
          (xo[3]==xo[4] && xo[4] ==xo[5] && helper(3,4,5)) ||
          (xo[6]==xo[7] && xo[7] ==xo[8] && helper(6,7,8)) ||
          (xo[0]==xo[3] && xo[3] ==xo[6] && helper(0,3,6)) ||
          (xo[1]==xo[4] && xo[4] ==xo[7] && helper(1,4,7)) || 
          (xo[2]==xo[5] && xo[5] ==xo[8] && helper(2,5,8)) ||
          (xo[0]==xo[4] && xo[4] ==xo[8] && helper(0,4,8)) ||
          (xo[2]==xo[4] && xo[4] ==xo[6] && helper(2,4,6))

}

//And finally a function to check if there is a draw which will check if all board values are not empty strings. This only works after checking that there is no winning conditions first

function boardfull(){
  return xo.every((elem)=>{
   return elem !=''
  })
}

Now we have the function to check if a winning state is there and we can finally write the Minimax like this (I've added comments in the code to help explain it):

// As I said erlier, the algorithm will take the board, the ismax parameter to check if we want to maximize or minimize for a certain turn

function minimax(board,depth,ismax){

    // This is a recursive function, so we should set the bases cases first which will be getting a draw a win or reaching the depth

    // As you've seen in the visualizations, when there is a draw or winning conditions no more child boards are generated. So if a winning condition occured when it's X's turn. It got to be X who won that's why I returned 1, and the same logic applies for when Y won and I returned -1 when we were minimizing.

    if (checkwin()) return ismax ? 1 : -1
    if (boardfull()) return 0

    if(ismax){

        // When we're maximizing we will set a counter to -Infinity and whenever we encounter a board value higher than the counter, we will consider it as the best move

     let best=-Infinity
     board.forEach((elem,index)=>{

         //Now to check all resulting positions we will iterate over the board and whenever there is an avaible slot we will set it to X and run minimax on this position. Look how I incrimented the depth

     if(elem ==''){
       board[index]='X'
       let  localscores=minimax(test,depth+1,false)

       // Here I am reetting the board to the same position 

       board[index]=''
       best=max(best,localscores)
     }})
     return best
     }

 // This else here means we're minimizing

 else{

     // Here we will set our counter to + Infinity because we want to find the lowest possible value

    let best=Infinity
    board.forEach((elem,index)=>{
    if(elem ==''){
     board[index]=humanicon
     let localscores=minimax(test,depth+1,true)
     board[index]=''
     best=min(best,localscores)
    }})
    return best
  }
}

And now we're done!

Conclusion

In this article, we’ve learned about the minimax algorithm, its mechanism, limitations, and how to improve it. Now you can go and customize this to work on various games to create some cool game bots.

In the end, I hope you learned something new from this article.

If you found this useful and want to get more awesome content, follow me on LinkedIn. It will help a lot.

And these applications require a lot of computation. Imagine searching for a particular DNA sequence out of millions, or searching for a user in Google's database.

That's why we need an algorithm that runs very fast without consuming lots of memory. And that's what you'll learn about here.

In this tutorial, we will be diving deep into two famous search algorithms: Rabin-Karp's algorithm and the Knuth-Morris-Pratt algorithm. We'll also discuss their time and space complexity, which is equivalent to the time and space an algorithm consumes, depending on its input size. You will also learn about common data structures for searching.

A very basic knowledge of programming is required to follow along. We'll be using Python examples in this tutorial.

Table of Contents

• Data structures for bioinformatics and searching
• Naïve search algorithm
• Rabin-Karp's algorithm
• Knuth-Morris-Pratt algorithm
• Conclusion

Data Structures for Bioinformatics and Searching

Let's first discuss some data structures that you should know even if we weren't diving too deeply into the topic.

The Trie Data Structure

A trie is a tree-like data structure where each nodes stores a letter of an alphabet. You can structure the nodes in a certain way so that words and strings can be retrieved from the structure by traversing down a branch (path) of the tree.

Let's take the words ANA, AND, and BOT for example – their prefix tree or trie will look like this:

How a trie looks like

Tries are widely used for:

• Auto complete
• Spell Checkers
• Longest prefix matching
• Browser history

Suffix trees

Suffix trees are tree-based data structures, but instead of taking multiple words to build the tree we will be using the suffixes of a single world.

If we consider the string AABA, we will first add a $ sign to the end of the string. That $ will make string comparison easier. Now the string is AABA$.

We will consider all of it's suffixes and the tree will look like this:

A suffix tree

Burrows Wheeler transform

Now we will discuss the burrows wheeler transform which is very useful data structure fort string compression.

This data structure is widely used in bioinformatics for a very specific reason. I want you to imagine a string representing a genome. It maybe very long, like 20 million characters.

But there is actually a way to store genomes efficiently. Imagine the string AAAAABBBAAA. This string has many repeats and we can actually compress this string to be something like this: A5B3A3. This is very useful for genomes as well which have many repeated characters.

Now let's take the string BANANA. We will first add a $ sign to the start of the string then compute all the cyclic rotations of $BANANA. Then will sort the cyclic rotations – and here is the importance of the dollar sign: that value, when sorting, is less than all alphabet values, so it will make sorting way easier.

After we sort the cyclic rotations, the string formed by the last characters of the sorted cyclic rotations is the burrows wheeler transform. It will look like this:

Burrows wheeler transform

Now as you can see, the burrows wheeler transform tends to have lots of repeats. You might also ask how to reverse the operation. To do that, look at the first characters of the sorted cyclic rotations. They are the same as the characters in the burrows wheeler transform but in sorted order.

So by sorting the burrows wheeler transform, we will get the first and the last letters and compute the original string.

Naïve Search Algorithm

Now let's look at a brute force solution for finding a pattern in a string. This approach is not optimal, as it runs with O(n*m) time complexity (where m is the length of the pattern and n is the length of the string).

We will consider two pointers, I and J. First we'll initialize I and J to be 0. Then we will run a while loop that will keep running while I is less than the length of the string.

Every time the loop runs we will compare the characters at the index I+J in the string and the character at the index J in the pattern. If they are equal, we will increment J, but of mpt. we will increment I and reset J to be 0. If j ever exceeds the length of the pattern, then there's a match.

The code for this will look like this:

def Find_Match(pattern,string): 

  #initialise i and j
  i=0
  j=0

  while i<len(string):
   if string[i+j] == pattern[j]:
     j+=1
   if string[i] != pattern[j]:
     j=0  
     i+=1
   #Let's say j is equal to the length of the pattern. Then to reach the first match index we can go back a number of steps equal to the length of the pattern.
   if j==len(pattern):
    return i-j

  #Incase there is no match  
  return -1

Rabin-Karp's Algorithm

The problem with the naïve approach is that it runs in O(n**2) time complexity which is horrible when it comes to large inputs like genomes. This means we need something better.

Comparing two strings is linear time, because we need to compare each character for each index. But what if we don't need to do that – what if we transformed the strings into numbers?

Here is the main idea of this algorithm. Let's say there is a function that returns a number associated with each string in the alphabet. We will use the ASCII value of the strings for that.

And then to transform a string into a number we will compute the sum of the ASCII values of all its characters. This a simple hashing function:

def hash(string):
 count=0
 # in python ord return the ascii value of a character
 for i in string:
  count+=ord(i)

 return count

Now let's say we want to find an in banana. Then we will first compare hash(an) to hash(ba) then to hash(an) and so on till we reach the end of the string. When the hash values match, we can then compare the pattern and the substring because hash(na) and hash(an) are equal so we need an extra check.

You might be thinking this is silly – why do we need to do all of this? Computing the hash function needs to iterate over the string so we didn't achieve any better time complexity. And you're completely right.

But what if we can compute the hash value of a substring from its previous substring? The difference is in the starting and ending characters – and that's called a rolling hash. That's what makes this algorithm run at O(n*m) worst case and O(n+m) average case: because of collisions.

For example, hash(na) is equal to hash(an), so here we need to compare na and an. The hash function I showed you is a very simple one. The better the hash function, the fewer collisions we will have. But I don't want to make this too fancy, so I will be using this hash function.

rolling hash

def Rabin_Karp(string, pattern):
 #compute the hash value of the pattern
 hashed_pattern=hash(pattern)

 #compute the hash value of the first substring with length equal to the length of the pattern

 first_hash=hash(string[0:len(pattern)])

 for i in range(len(string)-len(pattern)+1):
  if i !=0:
   first_hash-= hash(string[i-1])
   first_hash+= hash(string[i+len(pattern)-1])

  if hashed_pattern == first_hash:
   #second check
   if pattern == string[i:len(pattern)]:
    return i

 #in case no matches are found 
 return -1

Knuth-Morris-Pratt Algorithm

Now we will discuss the last algorithm for today. This one is very complicated but I will try to make it as simple as possible.

The idea behind this algorithm is that the naïve approach is great unless the string and the pattern have many repeats – like for example searching for AAAB in AAAXAAA. In this case do we really need to reset the j pointer to 0 after the first mismatch? Actually no we don't, and I will show you why.

When we analyze this pattern, we can see that it's quite special. Let's say we started at i=0 and we reached j=3. Then the next iteration we got a mismatch.

We don't really need to reset j, since for this given pattern we have the two first characters equal to the second and third characters. And since j already was 3, then the first 3 characters in the string are equal the first three characters in the pattern. And the second and third characters in the string are equal to the first and second characters in the pattern. So we can skip two positions by resetting j to 2 instead of 0.

Now you might ask how we'll know the value of j after the mismatch. Well, the answer depends on the pattern. For example abac if we got a mismatch when we reached j=3 (when we reached c) and since ab is equal to ba, we can actually skip b for the next iteration.

As you can see this works when we have a common suffix and prefix in a substring of a pattern, so we need to preprocess the string. And for each index of that substring, we can compute the number of skips and store it in an array known as the longest suffix prefix array.

Now we'll write the function for computing the LSP array. But first I will explain what I will be doing:

• the first element in the array is always 0
• we will create an array LSP with the same length as the pattern
• we will have twp pointers i and prevlps. i is an iteration variable initially set to 1, since the first element in the array is always 0. prevlps keeps track of the previous longest prefix suffix.
• we will run a while loop which will keep running while i is less then the length of the pattern. It will compare pattern[i] and pattern[prevLps]. If they match, we will set LCP[i] to prevlps +1, and we'll increment i and prevlps by 1.
• if they don't match and prevlps was 0 already, we will set LCP[i] to 0 and increment i.
• if prevlps was not 0, we will set prevlps to LCP[prevlcp-1].

Let's take an example using the string ANAN. First i was 1 and prevlps was 0. The first iteration happens, and A is not equal n and prevlps is 0 – so the LCP is now [0,0,0,0].

Now for the second iteration we will compare pattern[prevlps] which is A and A which evaluates to true. So now i is 3, prevlps is 1, and LCP is [0,0,1,0].

And finally, in the final iteration we will compare N and N. The same thing happens as in the past iteration, and LCP is [0,0,1,2].

The code for LCP is the following:

def LCP(pattern):
 LCP_array=[0]* len(pattern)

 i=1
 prevlcp=0

 while i<len(pattern):
  if pattern[i]==pattern[prevlcp]:
   LCP_array[i]=prevlcp+1
   i+=1
   prevlcp+=1

  elif prevlcp == 0:
   LCP_array[i]=0

  else:
   prevlcp=LCP_array[prevlcp-1]

 return LCP_array

Now since we have the LCP array we can run the KMP algorithm. It's similar to the naïve algorithm but with some improvements. It will look like this:

def KMP(pattern,string): 

  LCP_array=LCP(pattern)

  #initialise i and j
  i=0
  j=0

  while i<len(string):
   if string[i+j] == pattern[j]:
     j+=1
   if string[i] != pattern[j]:
     #The line that changed
     j=LCP_array[j-1] 
     i+=1
   #Let's say j is equal to the length of the pattern. Then to reach the first match index we can go back a number of steps equal to tje length of the pattern.
   if j==len(pattern):
    return i-j

  #In case there is no match  
  return -1

This algorithm runs with O(n+m) time complexity which is great – but it's little bit complicated. If you noticed, almost nothing changed (just in computing the LCP and a single line changed). This single line is what makes the algorithm so efficient.

Conclusion

In the end I hope you learned something new from this article. We learned about data structures for searching as well as some famous algorithms for searching.

This tutorial was the result of two weeks of research. There are a lot of things that I wanted to cover but I wanted to keep this manageable.

If you found this useful and want to get more awesome content, follow me on LinkedIn. It will help a lot.

In this tutorial we will be building a path finding algorithm visualizer with React. It will support Breadth-First Search (BFS), Depth-First Search (DFS), adding walls, and weighting nodes for weighted graph algorithms like Dijkstra's. This will help us identify features like streets with high traffic that you don't want to take.

To go through this tutorial, you should have a basic understanding of BFS and DFS. In case you need to review, I will leave a link for a YouTube video explaining the two algorithms.

You should also have a basic understanding of React.

Here's the final version of what we're going to build and here's the source code on my GitHub account.

In this tutorial we will be using Visual Studio Code (but you can use any editor you want), a command line prompt, some basic React, ES6 JavaScript, and HTML and CSS.

So let's start coding!

Project Setup

For this tutorial I will be using Vite, which is a tool that helps you start projects way faster than npm create-react-app.

First, install Vite if you haven't done that yet. Create a folder in a well-known directory on your machine. Then using the terminal, navigate to this directory and run these commands:

$ npm create vite@latest my-app
$ cd my-app
$ npm install

Now inside the src folder, create a components folder, a contexts folder, and a utils folder – and you're done. Here's a screenshot of what your project should look like:

Project folder structure

How to Add Bootstrap

Now we need to add bootstrap to our project for the buttons and icons we're going to add, since we need to focus on the JavaScript part.

To do this, just add the Bootstrap CDN to the head tag in your HTML file. After adding these links you should notice the font changing.

<link href="https://cdn.jsdelivr.net/npm/bootstrap@5.2.2/dist/css/bootstrap.min.css" rel="stylesheet" integrity="sha384-Zenh87qX5JnK2Jl0vWa8Ck2rdkQ2Bzep5IDxbcnCeuOxjzrPF/et3URy9Bv1WTRi" crossorigin="anonymous">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bootstrap-icons@1.9.1/font/bootstrap-icons.css">

How to Represent the Cells

For the representation of the grid and the cells, I will be building a two dimensional array of objects containing all the properties we need to represent a certain cell.

Now in the utils folder, create a startingGrid.js file. Here, you'll write a function that returns a grid which is a two dimensional array of objects representing the cells.

Each object will have these properties: x, y, isstarting, istarget, iswall, and weight.

x and y represent the coordinates of the cell. isstarting is a Boolean that's only true for the starting cell. istarget is similar, but for the target node. iswall is a Boolean that's only true for walls. And weight is an integer.

All normal cells have a weight of 1, and the weighted cells have a weight of 5. The function should look like this:

export function getGrid(width,height){
    let grid=[]
    for (let i =0 ; i<height ; i++){
      let local=[]
      for (let j =0 ; j<width ; j++){
          local.push({x:j,y:i,isstart:false,istarget:false,weight:1,
          iswall:false})
          }
      grid.push(local)
      }
    grid[Math.floor(height/2)][Math.floor(width/2)].isstart=true
    grid[height-2][width-2].istarget=true
    return  grid
    }

How to Create the Context

In React, passing props from parent to child may become unmaintainable. For this reason, it's better to store all of our state in a single place where state will be accessible to all elements. That's what a context is.

In React we can create a context with createContext and access all its variables using the useContext hook.

Now let's create a context with everything we need. When we hover over a cell we will control the behavior of the event listener based on a variable called mode. For example, if the mode is addwalls, then hovering over a cell makes it a wall.

We will use the same logic for adding weighted cells, and also for setting the starting and ending cells.

The structure I will be using for creating the context is very simple. You can make use of it in all of your projects, and it will look like this:

import { useContext,createContext } from "react";

const context = createContext()

export const useParams=()=>{
    return useContext(context)
}

export const ParamsProvider = ({children}) => {

      return (<div>
       <context.Provider value={}>
        {children}
       </context.Provider>
      </div>)

}

Now we will create state for:

• The mode we're in, either building walls or setting the starting cell.
• The algorithm that we will run.
• The grid which we will equal by default to the grid returned by the function we already created.
• Determining if we're editing or not.
• For the starting and target node coordinates.
• Determining that we want to run the algorithm and clear the grid when changed using useEffect (A separate state for each that, when we change its value, we run a useEffect with an appropriate side effect).

The code will look like this:

import { useContext, useState,createContext, useEffect, useRef } from "react";
import { getGrid } from "../utils/startinggrid";

const context = createContext()

export const useParams=()=>{
    return useContext(context)
}

export const ParamsProvider = ({children}) => {

     const [mode,setmode] = useState(null)
     const [algo,setalgo] = useState('')
     const [run,setrun] = useState(false)
     const [grid,setgrid] = useState(getGrid(50,25))
     const [editing,seteditFlag] = useState(false)
     const [res,setres] = useState(false)
     const start=useRef({x:25,y:12})
     const end=useRef({x:48,y:23})

     useEffect(()=>{    
      restart()
     },[res])


     function restart(){
      setgrid(getGrid(50,25))
     }


      return (<div>
      <context.Provider value={{mode,
        setmode,
        algo,
        setalgo,
        grid,
        setgrid,
        setres,
        editing,
        seteditFlag,
        start,
        end,
        run,
        setrun,
        res}}>
         {children}
       </context.Provider>
       </div>)

     }

And finally, we'll wrap the app component with the ParamsProvider like this:

import React from 'react'
import ReactDOM from 'react-dom/client'
import App from './App'
import './index.css'
import {ParamsProvider} from './context/context'

ReactDOM.createRoot(document.getElementById('root')).render(
  <React.StrictMode>
      <ParamsProvider>
      <App />
      </ParamsProvider>
  </React.StrictMode>

)

Now to make sure everything is working, import the useParams custom hook to your any components. Now use the console to check its return value. It should return an object with all the variables we've added to the store.

import './App.css'
import {useParams} from './context/context'


function App() {

console.log(useParams())

return ( <div></div>)

}

export default App

How to Create the Navbar

Now it's time for the navbar which we'll use to control the modes. First, create a Navbar folder with two files: Navbar.jsx and Navbar.css. This structure is very useful, especially when using Sass (so each component and its CSS can be found in the same folder).

The navbar will consist of six buttons: two for setting the mode for starting/ending node editing, two for setting the mode for building blocks/adding weighted cells, and two for clearing the board and running the algorithm.

The code will look like this:

import React, { useState } from 'react'
import './Navbar.css'
import { useParams } from '../../context/context'


export default function Navbar() {

  // const [algo,setalgo] = useState('')
  const {mode,setmode,algo,setalgo,setres,setrun}=useParams()



  return (
    <div className='navbar'>
      <div className='container'>
       <button type="button" className={['btn' ,'btn-primary', mode=='setstart'? 'selected' : ''].join(' ')} onClick={()=>{
        if(mode == 'setstart') setmode(null)
        else {setmode('setstart')}
       }}>
        <i className="bi bi-geo-alt"></i>
       </button>
       <button type="button" className={['btn' ,'btn-primary', mode=='settarget'? 'selected' : ''].join(' ')} onClick={()=>{
        if(mode == 'settarget') setmode(null)
        else {setmode('settarget')}
       }}>
       <i className="bi bi-geo"></i>
       </button>
       <button type="button" className={['btn' ,'btn-primary', mode=='addbricks'? 'selected' : ''].join(' ')} onClick={()=>{
        if(mode == 'addbricks') setmode(null)
        else {setmode('addbricks')}
       }}>
       <i className="bi bi-bricks"></i>
       </button>
       <button type="button" className={['btn' ,'btn-primary', mode=='addweight'? 'selected' : ''].join(' ')} onClick={()=>{
        if(mode == 'addweight') setmode(null)
        else {setmode('addweight')}
       }}>
       <i className="bi bi-virus"></i>
       </button>
       <button type="button" className="btn btn-primary" onClick={()=>{setres((old)=>{ return !old})}}>
       <i className="bi bi-arrow-counterclockwise"></i> 
       </button>
       <button type="button" className="btn btn-primary" onClick={()=>{setrun((old)=>{return !old})}}>
       <i className="bi bi-caret-right"></i> 
       </button>
       <div>
       <select className="form-select" aria-label="Default select example"  value={algo} onChange={(e)=>{
        setalgo(e.target.value)
       }}>
       <option value=''>Choose your algorithm</option>
       <option value="dijkstra">dijkstra</option>
       <option value="BDS">BDS</option>
       <option value="BFS">BFS</option>
</select>
       </div>
      </div>
    </div>
  )
}

Each button sets the mode to the desired value – or to null if it's already set to the button's mode.

The run and restart button change the values of the state context variables res and run. We'll use these with a useEffect hook to run the algorithm or clear the board. The select input element is to select the algorithm.

Now, for example, if the building blocks mode button is selected, we want this button to have a different styling from other buttons. We'll do that by using the selected class that will be added for the button depending on which mode is selected. The CSS will look like this:

.navbar{
    width:100%;  
    height:min(20vh , 100px);
    background:black;
}

.navbar .selected {
    box-shadow: rgb(204, 219, 232) 3px 3px 6px 0px inset, rgba(255, 255, 255,     0.5) -3px -3px 6px 1px inset;
}

This is how the app is going to look right now. To test it out, you can check for context variable changes on button clicks:

Current state of the app

How to Create the Grid

Now the cells are divs contained in a div with the class of board which will contain all the cells. The grid will look like an Excel sheet where each cell has an x and y coordinate.

First, create a Grid folder in the components folder. Then add two files in it: Grid.jsx and Grid.css.

Now let's create the grid. First we will create a function that takes the grid and returns an array of refs for each cell.

When we run the algorithms, there will be a lot of state changes if we use regular state and the application will crash. So the solution is to create a ref for each cell, and when we render the cells, each will have its corresponding ref. This lets us manipulate the div without re-rendering the component.

This approach comes with a cost, though, which is unexpected behavior – because this is not the way React is supposed to work. But if we don't use this approach, the application will crash because of the re-renders.

We will create a state to save the ref array. The algorithm will look like this:

  const {grid,setgrid,editing,seteditFlag,mode,start,end,run,res,algo}  =       useParams()

  const [refarray,mm]=useState(getrefarray(grid))

  function getrefarray(grid){
    let array=[]
    grid.forEach((elem)=>{
     elem.forEach((child)=>{
      array.push(useRef())
    })
   })
   return array
   }

First we will render a div with class of board. Inside the board and for each element of refarray we will render a div with a ref property (the element itself) so we can access and modify it without rendering the component again.

Each div will have the cell class and the wall class if its corresponding cell object in the grid has the iswall property equal to true. Also we will add the corresponding icon to the cell based on its cell object.

{refarray.map((elem,index)=> {
        let classList=['cell']

        let yindex=Math.floor(index/50)
        let xindex=index % 50
        let cell=grid[yindex][xindex]

        if (cell.iswall) {
          classList.push('wall')
        }

        return <div key={`${index}`} ref={elem}  className={classList.join('         ')} >


          {cell.weight > 1 ? <i className="bi bi-virus"></i> : null}
          {cell.isstart ? <i className="bi bi-geo-alt"></i> : null }
          {cell.istarget ? <i className="bi bi-geo"></i> : null }

        </div> 
})

This is how the grid is going to look:

App showing the grid

Now we need to add three event listeners to each cell. First, we'll add onMouseDown and onMouseUp event listeners – we use these to set the editing context variable. Then we'll add an onMouseOver which will determine – based on the mode and that editing flag – what changes are being applied to the grid.

We will be updating the grid as usual – we will only use the ref method when running the algorithm. The code will look like this:

return (
    <div className='board'>
      {refarray.map((elem,index)=> {
        let classList=['cell']
        let yindex=Math.floor(index/50)
        let xindex=index % 50
        let cell=grid[yindex][xindex]

        if (cell.iswall) {
          classList.push('wall')
        }

        return <div key={`${index}`} ref={elem}  className={classList.join(' ')} 
        onMouseDown={()=>{seteditFlag(true)}} 
        onMouseUp={()=> {seteditFlag(false)}}
        onMouseMove={()=>{
          if (!editing) return
          const current= grid[yindex][xindex]
          if (current.isstart || current.istarget ) return
          switch(mode){
            case 'setstart':
              var newgrid=grid.map((elem)=>{
              return elem.map((elem)=>{
                if (!elem.isstart) return elem
                return {...elem,isstart:false}
              }) 
              })
              newgrid[yindex][xindex]={...newgrid[yindex][xindex],isstart:true,istarget:false,weight:1,iswall:false}
             start.current={x:xindex,y:yindex}
             setgrid(newgrid)
             break;

           case 'settarget':
                var newgrid=grid.map((elem)=>{
                return elem.map((elem)=>{
                  if (!elem.istarget) return elem
                  return {...elem,istarget:false}
                }) 
               })
               newgrid[yindex][xindex]={...newgrid[yindex][xindex],isstart:false,istarget:true,weight:1,iswall:false}
               end.current={x:xindex,y:yindex}
               setgrid(newgrid)
               break;

             case 'addbricks':
                var newgrid=grid.slice()
               newgrid[yindex][xindex]={...newgrid[yindex][xindex],weight:1,iswall:true}
               setgrid(newgrid)
               break;

            case 'addweight':
                var newgrid=grid.slice()
               newgrid[yindex][xindex]={...newgrid[yindex][xindex],weight:5,iswall:false}
               setgrid(newgrid)
               break;
           default:
             return 
            }}}>


          {cell.weight > 1 ? <i className="bi bi-virus"></i> : null}
          {cell.isstart ? <i className="bi bi-geo-alt"></i> : null }
          {cell.istarget ? <i className="bi bi-geo"></i> : null }

         </div>
      })}
    </div>
  )

If the editing flag is false, we will return. The same applies if the cell is a starting cell or a target one – then we don't want to modify them. Else if the mode is equal to addwalls, then we will modify the corresponding cell in the grid and set the iswall property to true.

Also if the mode is equal to addweight we will modify the corresponding cell in the grid and set the weight property to 5 instead of 1.

For the setstart we will create a copy of the grid where all the cells have the isstart set to false. Then we'll set the corresponding cell for the new start cell to true. The same goes for the settarget mode.

Now you should be able to add walls, weights and change the position of the starting and ending node:

The Algorithms

We can find the shortest path using the algorithms we will implement. Each algorithm finds a path in a unique way and, depending on the algorithm, the output will change.

Let's start with the breath-first search (or BFS) algorithm. We will create a function BFS that takes 5 arguments:

• the graph
• the start and end point coordinates, start and target
• prevmap, which is a hashmap used to track the previous cell for each cell in the grid when the algorithm runs
• hashmap, which is a hashmap that we will use to track visited cells. A hashmap is an object with key value pairs, like a dictionary in Python.

For each cell in the graph, we will create an id x-y which will be unique. We'll set its value to false for hashmap and null for prevmap. Here is how we will implement those in a useEffect later:

  let hashmap={}
  let prevmap={}
  for (let j=0;j<25;j++){
   for (let i=0;i<50;i++){
     hashmap[`${i}-${j}`]=false
     prevmap[`${i}-${j}`]=null
   }
 }

Now we will start with an array with one element – the starting node's coordinates – and a counter set initially to zero. While the length of the array is not zero, we will pop the last element off the array and increment the counter.

Now using the coordinates of the element, we will access its ref and add the visited class with a transition delay proportional to the counter.

Then we will access the siblings of the element from the grid and check if they are visited or not from the hashmap. If they are visited we will ignore them, but if they are not visited we will mark them as visited and add them to the top of the array. Then we'll mark their value in the prevmap to the current element.

When popping elements off, if we come to an element with x and y coordinates equal to those of the target, we will return this object with the current counter.

Depth-first search is very similar: with small changes in the order, we can remove and add elements to the array. Here is Alvin's YouTube video which explains the topic in a helpful way.

Finally, if there is no path from a to b – for example if a is surrounded by walls – we will return null. This will happen only when the array gets empty before returning a value. The code will look like this:

  function BFS(graph,hashmap,prevmap,start,target){
    let queue=[start]
    let count=0
    hashmap[`${start.x}-${start.y}`]=true
    while (queue.length > 0){
      count+=1
      let c=queue.pop()
      refarray[c.x+c.y*50].current.style['transition-delay']=`${count * 8}ms`
      refarray[c.x+c.y*50].current.classList.add('visited')
      if (c.x == target.x && c.y == target.y) return [c,count]

      if(c.x+1 < 50 && !hashmap[`${c.x+1}-${c.y}`] && !graph[c.y][c.x+1].iswall){
        queue.unshift({x:c.x +1,y:c.y})
        prevmap[`${c.x+1}-${c.y}`]={...c}
        hashmap[`${c.x+1}-${c.y}`]=true
      }
      if(c.x-1 >=0 && !hashmap[`${c.x-1}-${c.y}`] && !graph[c.y][c.x-1].iswall){
        queue.unshift({x:c.x -1,y:c.y})
        prevmap[`${c.x-1}-${c.y}`]={...c}
        hashmap[`${c.x-1}-${c.y}`]=true
      }
      if(c.y+1 < 25 && !hashmap[`${c.x}-${c.y+1}`] && !graph[c.y+1][c.x].iswall){
        queue.unshift({x:c.x ,y:c.y+1})
        prevmap[`${c.x}-${c.y+1}`]={...c}
        hashmap[`${c.x}-${c.y+1}`]=true
      }
      if(c.y-1 >=0 && !hashmap[`${c.x}-${c.y-1}`] && !graph[c.y-1][c.x].iswall){
        queue.unshift({x:c.x ,y:c.y-1})
        prevmap[`${c.x}-${c.y-1}`]={...c}
        hashmap[`${c.x}-${c.y-1}`]=true
      }
    }
    return null
  }

  function BDS(graph,hashmap,prevmap,start,target){
    let queue=[start]
    let count=0
    hashmap[`${start.x}-${start.y}`]=true
    while (queue.length > 0){
      count+=1
      let c=queue[0]
      queue.shift()
      refarray[c.x+c.y*50].current.style['transition-delay']=`${count * 8}ms`
      refarray[c.x+c.y*50].current.classList.add('visited')
      if (c.x == target.x && c.y == target.y) return [c,count]



      if(c.y+1 < 25 && !hashmap[`${c.x}-${c.y+1}`] && !graph[c.y+1][c.x].iswall){
        queue.unshift({x:c.x ,y:c.y+1})
        prevmap[`${c.x}-${c.y+1}`]={...c}
        hashmap[`${c.x}-${c.y+1}`]=true
      }
      if(c.x-1 >=0 && !hashmap[`${c.x-1}-${c.y}`] && !graph[c.y][c.x-1].iswall){
        queue.unshift({x:c.x -1,y:c.y})
        prevmap[`${c.x-1}-${c.y}`]={...c}
        hashmap[`${c.x-1}-${c.y}`]=true
      }
      if(c.y-1 >=0 && !hashmap[`${c.x}-${c.y-1}`] && !graph[c.y-1][c.x].iswall){
        queue.unshift({x:c.x ,y:c.y-1})
        prevmap[`${c.x}-${c.y-1}`]={...c}
        hashmap[`${c.x}-${c.y-1}`]=true
      }
      if(c.x+1 < 50 && !hashmap[`${c.x+1}-${c.y}`] && !graph[c.y][c.x+1].iswall){
        queue.unshift({x:c.x +1,y:c.y})
        prevmap[`${c.x+1}-${c.y}`]={...c}
        hashmap[`${c.x+1}-${c.y}`]=true
      }
    }
    return null
  }

We will be running the algorithm only when the run button in the navbar is clicked. That will change the value of run, so we will run a useEffect for this with the context variable run in its dependency array.

We will save the return value in a result variable. If the result is null, we will do nothing and there will be no path. Otherwise, we will use the coordinates of the target and the prevmap to get the path from the starting point and the target. Then we will run a timeout with a callback that will add the path class and the corresponding transition delay to each cell.

This is how the code will look:

 useEffect(()=>{

if (algo == 'BFS'){
  let hashmap={}
  let prevmap={}
  for (let j=0;j<25;j++){
   for (let i=0;i<50;i++){
     hashmap[`${i}-${j}`]=false
     prevmap[`${i}-${j}`]=null
   }
 }
 let result=BFS(grid,hashmap,prevmap,start.current,end.current)
 let path=[]
 if (result !=null){
  let current=result[0]
  while (prevmap[`${current.x}-${current.y}`] != null){
    path.push(current)
    current=prevmap[`${current.x}-${current.y}`]
  }
  setTimeout(()=>{path.reverse().forEach((elem,index)=>{
    refarray[elem.x+elem.y*50].current.style['transition-delay']=`${( index) * 15}ms`
      refarray[elem.x+elem.y*50].current.classList.add('path')
  })},result[1]*9)

 }


}
if (algo == 'BDS'){
  let hashmap={}
  let prevmap={}
  for (let j=0;j<25;j++){
   for (let i=0;i<50;i++){
     hashmap[`${i}-${j}`]=false
     prevmap[`${i}-${j}`]=null
   }
 }
  let result=BDS(grid,hashmap,prevmap,start.current,end.current)
  let path=[]
  if (result !=null){
   let current=result[0]
   while (prevmap[`${current.x}-${current.y}`] != null){
     path.push(current)
     current=prevmap[`${current.x}-${current.y}`]
   }
   setTimeout(()=>{path.reverse().forEach((elem,index)=>{
     refarray[elem.x+elem.y*50].current.style['transition-delay']=`${( index) * 15}ms`
       refarray[elem.x+elem.y*50].current.classList.add('path')
   })},result[1]*9)

  }


 }
 },[run])

Now after pressing the start button this is the output we're going to get:

How to Clear the Board

The side effects of running these algorithms are the classes we've added and the transition delay property (which we need to clear before running the algorithm once again). That's what we're going to do to reset the grid.

The last thing we need to worry about is clearing the board. This will happen when the clear button in the navbar gets clicked, and it will change the value of the res context variable.

So the final useEffect will iterate over every ref of the refarray and reset its classes and transition delay. Also in the context there is another useEffect that will regenerate a new grid (you can check the context code out). It will look like this:

 useEffect(()=>{
  refarray.forEach((elem)=>{elem.current.style['transition-delay']='0ms'})
  refarray.forEach((elem)=>{elem.current.classList.remove('visited');elem.current.classList.remove('path')})
 },[res])

Here's the CSS for the grid:

.board{
    width:100%;
    height:calc(100vh - min(20vh , 100px));
    background:black;
    display:grid;
    grid-template-rows: repeat(25 , 1fr);
    grid-template-columns: repeat(50 , 1fr);
    gap: 1px;

}

.board .cell{
    display:flex;
    justify-content: center;
    align-items: center;
    background: white;
}

.wall {
    background:black !important
}

.visited{
    background:rgb(33, 85, 228) !important;
    transition:all 8ms cubic-bezier(0.075, 0.82, 0.165, 1);

}

.path{
    background:rgb(244, 255, 87) !important ;
    transition:all 8ms cubic-bezier(0.075, 0.82, 0.165, 1);


}

Now when you click the restart button the board will be back to normal.

Conclusion

Finally in this tutorial we've learned a lot about path finding algorithms, React, contexts, refs, algorithmic thinking and much more.

Hopefully you enjoyed this tutorial as much as I enjoyed writing it. This is one of many tutorials that I will be creating for freeCodeCamp.

You will find the code for this project on my GitHub and here's the hosted version. If you want to support me, follow me on LinkedIn It means a lot for me.