DEV Community: singhimat99

Introduction to Graphs

singhimat99 — Fri, 03 Feb 2023 22:13:46 +0000

Welcome to a new post on 'In My Own Words', where we take on programming concepts and make them simple for the every-day learner. With easy-to-follow examples and explanations in plain language, join me on my journey to understand the world of programming. Let's get started!

Today we will be talking about Graphs! A common data structure used to solve a ton of different problems.

Now what is a graph?

A graph is a data structure (an organized way to store information) that has vertices and edges. Now, those are some complicated words. Instead, let's refer to "nodes" as "dots" and "edges" as "connections" or "lines".

A simple way to grasp the concept of a graph is to think of the childhood game "Connect the Dots". Just as in the game, a graph consists of points or nodes connected by lines or edges, creating a network of relationships between the nodes. This network can then be used to solve a variety of real-world problems and serves as the foundation of many crucial algorithms.

A graph is a visual representation of information and the relationships between it. For instance, you and your followers on Instagram can be represented as points, and the fact that they follow you is represented as a connection between those dots. The connection represents the relationship or interaction, in this case, following on Instagram.

What are graphs useful for?

Have you ever wondered how Google Maps shows us the location of everything and provides us with routes that follow actual roads instead of a straight line path? They use graphs! Landmarks and intersections are represented as dots, and roads, streets, and highways are represented as connections. What we see as the map is just a satellite image of the Earth. The actual mapping happens beneath the image.

When you ask the Google Maps app for directions from your current location to a destination, it first finds the two locations in the graph data structure where they are stored. Then, it runs an algorithm to find the shortest path between the two dots. In simple terms, Google Maps uses graphs to understand how different places are connected and then creates a path by connecting those dots in the most efficient way.

Graphs are a powerful data structure that has many practical applications in the real world. In the coming days, we will delve into some of the numerous algorithms related to graphs. I hope you found this informative and now have a clearer understanding of graph data structures. Thank you for reading!

Creating a Word Search Puzzle for my Portfolio (part 2)

singhimat99 — Fri, 06 Jan 2023 02:10:39 +0000

In case you haven't already, please check out the first part of this series: Part 1

So, where were we...

We had just finished setting up the grid for our game, which serves as the foundation for the word search. The grid acts as the backdrop for the letters that players will choose from to form a sequence.

Now we can focus on replacing all these 0's with letters.

For this we are going to need an algorithm that does the following:

arranges all of the provided words on a grid of the same size in random order
fills all remaining cells with random letters

Lets tackle this problem

We know the words can only be placed either horizontally, vertically, diagonally up, or diagonally down. (refer to part 1, if you are lost),

So we need a grid and we need to place a list of words on that grid in one of 4 possible orientations.

To begin, we can define a function that accepts the size of the grid and a list of words as input. We can use the size to create a 2D matrix, and then iterate over the list of words using a loop

Inside the loop, we need to randomly select a direction for the current word. To do this, we can create an array containing the four possible orientations: horizontal, vertical, diagonally up, diagonally down.

Hold on just a second

I just thought of a problem that we would likely face while solving this.

If we randomly place a word on the grid and select an orientation for it, there is a possibility that the word will be positioned outside the boundaries of the grid.

For example, if I select the word "javascript" and give it a horizontal orientation, and then try to place it starting at the rightmost edge of the matrix, there will likely be an error because we will be attempting to place a letter outside the boundaries of the matrix.

To prevent this issue, we can add a do-while loop inside our for loop. This loop will continue running until the word is placed within the boundaries of the matrix. To keep track of this, we can initialize a variable "placed" that is set to False and will be set to True if the word is successfully placed. This will allow us to break out of the loop when the word has been properly positioned.

Now, as we go through the process of placing the word, if we encounter a location that is outside the boundaries of the matrix, we can use the continue keyword to restart the while loop and select a new orientation and position for that word.

Okay, back to the algorithm

So first let’s assign a random starting position for the word with the following:

Next, we can select a random orientation from our array of orientations. We will also initialize our rise and run variables, which we will use in various operations later on.

Now we just need to determine the slope (rise and run) based on the random orientation that we got.

We can use a switch case statement and assign the appropriate rise and run values. (Notice how these values can be derived from our slope validation function in part 1).

Now we need to determine if the end of our word will be placed outside the grid. To do this, we can calculate the position of the last letter in the word. We can do this by adding the row to the product of the length of the word and the run, and doing the same with the column and rise variables.

After this calculation, we will have the row and column values for the last letter of the word. If either of these numbers is larger than the length of the matrix or less than 0, we need to try a different orientation (restart the while loop) to make sure that the word fits within the grid.

If we pass this check, it means that the beginning and end of the word are both within the boundaries of the matrix.

Now, we need to check if there are any other words in the way. We can't overlap words unless they share one letter.

We need to set up a loop to iterate over each letter of the current word to check if the current position is already taken. We will also initialize a variable called failed outside the loop. This variable will be used later in the while loop.

For each letter in the word, we can calculate the position on the matrix where this letter would be placed. We can do this by multiplying the index of the letter by the run or rise and adding it to the initial row or column, respectively.

Here's how it works: on the first iteration, the index is 0, so after multiplying it to the run or rise we end up with 0 which we add to the row and column values, which means we check the starting position.

On the next iteration, the index is 1. This time we are multiplying the run and rise by 1 which means this time we will be adding the run and rise values tot he row and column values respectively. By doing these calculations we will be checking where the current letter of the word would be placed based on the orientation we selected at the beginning of the while loop.

After that, we can check if the position in the matrix is empty or if it is occupied by the same letter as the current letter of the word.

If at any point we find that this condition is false we break out of the loop as set failed to true. So that we can restart the whole loop based on this condition:

Now, if our word passes all the previous checks we know two things that are crucial before attempting to place the word on the matrix.

the word is within the matrix
we can place the word without overriding a previous word

So we can finally place the word!!

We have already done half of this in our last check so it is simple from here. We just calculate the new row and column using a similar calculation and then we place the current letter at that position on the matrix. Once we have finished this we can finally set placed to True and break out of the loop!!

We have finally finished the hard part

Now all that we have left to do is replace all of the empty spaces with a random word. This very simple we just iterate over the matrix with a nested for loop and if the current index is empty. We assign it a random letter.

We have a puzzle that is now ready to be solved all we have to do now is check if the player is picking the right word.

To be continued…

My Strategy for Learning Data Structures

singhimat99 — Thu, 05 Jan 2023 04:35:27 +0000

Like all good stories in the past few weeks mine starts with OpenAI's Chat GPT.

I have just started my journey in learning Data Structures so naturally I ask chat GPT the best strategy for learning and one of the methods was to implement the given data structure from scratch. Now that sounds daunting...

However, this is a great idea! I am definitely going to add it into my learning strategy. So heres what I have so far.

First I have to pick a data structures to study then I will follow these steps until I feel confident in my ability to understand and use the data structure:

1. Research Research Research.

I will spend some time first gathering information on the data structure.

My research will be focused on the following:

basics of how to read and write from the structure
how it came about
which problems it solves

2. Next I will try to implement it on my own in Java.

Yes, I said Java, a language I do not even know yet. Why would I do this? There is a couple reasons:

The main reason is that in order to find all of the syntax necessary to create this structure I will need to fully understand how it works.
I want to learn Java, I remember asking ChatGPT a while ago the best way to learn Java and one of the answers it gave me was to implement data structures in the language.

This step is only possible if I have a deep understanding of the data structure. I will develop this by first learning all of the necessary lower level concepts that go into building the structure like how it is stored in memory and what other data structures are used to build it. These are the steps:

Learn the low level concepts
Write the data structure in pseudocode
convert the pseudocode into Java (and possibly Javascript just for fun)

This is going to be the hardest step and will likely take a couple of days but I believe it's necessary for the learning process.

3. Finally I will solve Leetcode easy questions with my own implementation of the data structure.

I believe this step is crucial because it will help me learn how to actually use the data structure to solve a problem. This will connect all of the dots and align all of the stars for me to understand the data structure.

In case you haven't noticed all of the pictures in this post have been generated by AI.

Once I have done all of these steps I believe I can start tackling harder Leetcode questions using the data structure (and maybe even my implementation of it ¯_(ツ)_/¯).

How I created a Word Search Game for my Portfolio (React) Part 1

singhimat99 — Wed, 28 Dec 2022 23:58:01 +0000

So what does it take to build word-search?

Lets Break this down..

We first need to understand the game itself.

Word search is a very common game often found in newspapers. Its quite simple the player just has to find the listed words inside of a grid if seemingly random letters.

So we know we need a grid with randomly placed letters and we need a way for the player to select possible words on the grid.

First lets handle selecting words

What we know:

We know we are dealing with a grid so we can think in terms of x and y coordinates (or rows and columns)
We know that there are only four ways to select a word: horizontal, vertical, diagonally up, and diagonally down.

Lets start with a simple matrix

Start with just a simple react component and then create 10x10 2D array filled with zeros.

Then use the javascript map method on the array state to render out the array as buttons and add some styles (I used tailwind) to get to something like this:

Now we need to keep track of clicks on these buttons. We know that we're going to need a click event listener to do that so I added an 'onClick' event to each button.

Next, we're gunna need some state to keep track of clicks and we need to decide what happens we we do click a button.

When we click a random button on this grid we should first increment clicks and then we can change the 0 to a 1 wherever we clicked as a way of acknowledging the click. In order to keep track of the location we will use the indexes of i and j for rows and columns respectively.

So far we are keeping track of clicks we can see if the user has clicked more than once. For now if the user has clicked more than twice let's just disable all buttons. To do this we are gunna need another state variable and set a disabled prop on each button.

Note: When we change state in react it is asynchronous. This means we have to check if the value of clicks is 1 instead of 2 because the clicks will only be incremented after the handleClick function has already run.

Let's also set up another button to reset the board(returning to our initial table of 0's and clicks to 0).

So right now the user can change 2 of the 0's on the board at a time before they have to reset.

This is useful because in word search you are usually trying to find the beginning or end of a word which is either in a straight line or diagonal.

Now all we have to do is check if the 2 places the user has selected are directly horizontal, vertical, or diagonal from each other.

So let's create a helper function to do so. In this function we are essentially checking whether the slope between the two cells is valid (hence the name isValidSlope).

Oops...

At this point I realized that in order to do this I had to somehow keep track of the 2 cells that had been selected. So lets handle this first...

We are definitely going to need some state to handle this so let's create initialize this to an empty array.

Since we are using a 2D array we should have access to the indexes in the map functions. We can use the indexes that we used earlier to select a cell, which are already passed into the handleClick function.

So if the user is clicking for the first time we can assume that this is the first cell. Then we can save this location to our state variable to keep track of it for the next click.

Now if the user has clicked more than once we can calculate the slope using the previous cell location and the current cell location the user just clicked on. We do this by subtracting the current row (i) from the previous row (previousCell[0]), and the current column (j) from the previous column (previousCell[1]). This will give use the rise and run values for the 2 cells, and we can pass this into our helper function!

Phew! Now that we took care of that we can get back to our isValidSlope function.

Now that we have slope calculated from above all we have to do is to see if it valid or not.

How do we know what a valid slope is?

Well, like we talked about earlier the only way a word can appear on the grid is horizontally, vertically, or diagonally.

This means that there is only a 4 types of possible slopes. So first let's take care of the easy cases. We know that is the word is either horizontal or vertical either the rise or run will be 0. So we can return true if that is the case. (See lines 2-4 in code below)

Now we have 2 more cases in which there could be a valid slope and that is diagonally up or diagonally down.

If the slope if diagonally down, then the rise must be the run * -1. So, this means if we add them together then we will end up with 0. (See line 5)

If the slope if diagonally up, then the rise and run must be exactly the same. So we can check if they are equal and if that is true we can return true. (See line 6)

In any other case we can return false.

Now we can check the slope and see if the 2 cells selected are lined up correctly. But why were we doing this again? Oh yeah, because we want to find words.

We can use this to select the cells in between the 2 cells and change all of the 0's in the cells into 1's.

In order to do this we can use the slope that we calculated earlier. We will start at the current cell and use the slope to calculate the rise and run factors we need to increment over the the cells between the current and previous cells. As we do this we will save each location to a new array called totalCells.

Then we simply set the table to the new version with all of the appropriate locations changed to 1's

we can move all of this code into a helper function that gets called when the user is on their second click called selectCellsBetween.

AWESOME!

We just finished the first part of this problem! We can now keep track of all the cells that are selected and make sure that the user is not just able to select any random cells.