Creating a Word Search Puzzle for my Portfolio (part 2)
Published: 2023-01-06 02:10:39

In case you haven't already, please check out the first part of this series: [Part 1](https://dev.to/singhimat99/how-i-created-a-word-search-game-for-my-portfolio-react-part-1-138n)

### 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.

![image of grid](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cb134ue0h5xtxw5b9vic.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/t2a48jkqfaqw24vaj6ri.png)

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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jcm2avishf5ocbfsl8ik.png)

### 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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1xyuxuuvm95czvwvzm8y.png)

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:

![initial starting position](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gria6ctrqrfhwhaogap2.png)

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.

![orientations rise and run](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nwn13ewl2llnqa6rn968.png)

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).

![switch case statement](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/h7bzs57kazo92es60uu4.png)

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.

![find end of word](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fjmypwep5dhen8glhugw.png)

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.

![picture of loop](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/q20bs0whv0mfr8uv00j9.png)

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:

![if failed, continue](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/v9j4grqnvq7hm78ms7si.png)

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!!

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cbvdv17qv7g43avwwtx3.png)

### 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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/mh0h2ruuf7dytppnmrzg.png)

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…