In this video we combine what we've learnt about abstraction and problem decomposition to consider algorithmic thinking. Algorithmic thinking along with abstraction and decomposition is one of the three principles of computational thinking which you need to be aware of at GCSE. Algorithmic thinking is a way of getting to a solution by identifying the individual steps that were needed, creating a set of rules called an algorithm that if followed precisely leads to an answer. For example, we all learn algorithms for doing multiplication at school. If you or a computer follow these rules that we're taught precisely, we can get an answer for any multiplication problem.
Algorithmic thinking allows solutions to become automated. Let's have a look at this in the context of word searches. Now when you try to solve a word search what you could do is just randomly look around the grid of letters for one of the words. But this is probably not the most successful approach.
What you want to do is first identify which word you're going to be looking for. So breaking the problem down If we're just looking for the word algorithm, we could then just again randomly look around the grid for the word algorithm, but we're unlikely to find it quickly. So what we could do is take an algorithmic thinking approach and look for the first letter of the word algorithm.
And once more, we could just look randomly around the grid for letter A. So an example can be seen in these two places on the screen. But we need a bit more of a logical approach.
Once we find the letter we need, we then need to look at all the other letters that are around it and see if any of those letters are the second letter of our word. And if they are, then we need to follow that path to see if we can find any more letters. So we're beginning to find an algorithmic approach to solving the problem of a word search. However, it's still not the most efficient approach. We'd be far better off starting in the top left hand corner and checking if that letter is the letter A, and if not, moving to the next letter, and the next, and the next, until we find an A.
At this point, we can then check all the letters that are adjacent to it, to see if we can find the second letter in the word, and if not, we can move on to the next letter. So we want to try all the letters in a row and then we want to try all the rows so we've done all the columns. Eventually we're going to find an instance of A that when checked is connected to an instance of L and then we can follow the path until we find the word algorithm.
It feels like there's a very systematic and logical approach that we can take here and therefore Using algorithmic thinking, we should be able to create an algorithm to solve this problem. So here is an outline algorithm for solving the word search. For every word to find in the word search, we need to check every letter in the grid.
If the letter in the grid equals the first letter of the word, Then, for all the letters adjacent to the letter found, check if the adjacent letter in the grid is equal to the second letter of the word. And if it is, then for the length of the word, check all the letters in the same direction. If a letter does not match, then the word hasn't been found. If there's no more letters to check because we're outside the bounds of the grid, then the word is not found.
If all the letters match, then the word is found. And we could finish by outputting that the word was found. So the first thing that we're going to need to do is to think about how we can store our data.
Now, if we use the concept of abstraction, We can think about what's important and what's not important in terms of the data we need to store. Now, clearly the letters need to be stored and the grid is also important because we need to know which letters are connected to which other letters. But we need to be able to refer to them somehow and therefore we could number them.
It would also probably be useful if we could have some kind of X and Y coordinates. So when we're looking at this instance of the letter D, for example, we know that X is 7 and Y is 5. and it will make deciding which letters to check next much easier because we can refer to them by their numbers or their coordinates. Now if we take the concept of abstraction just a little further, the size of the grid is actually not important, and in fact even the words that we're looking for are not important, and the individual letters are not important.
The only thing we're really interested in is the current word we're looking for, and the letters for that word in the grid. All the other letters are irrelevant. So we could simplify our grid for the purpose of programming and testing into something like this. Now taking a problem decomposition and algorithmic thinking approach, we can think about how to store our data using the data structures provided by our programming language.
Here we're showing a Python example. Now Python supports lists and we can have lists inside lists and then we can refer to a particular item in the list using its number. So it's a good fit for our problem.
We can also store the word that we're going to be looking for in a variable. So the next thing we need to do is think about how we're going to look at every single letter in the grid. Well because we want to look at all of the columns and we want to look at all of the rows, then it feels like two for loops would be a good approach. This is because the bounds of the grids are known in advance.
We know the size of the grid in x and y coordinates, so it suits well for a loop. We could refine this a little bit further if we wanted to. If we knew there was ever only going to be one instance of the word in the grid, then we could use a while loop just to make the algorithm a little bit more efficient.
But for the purposes of this demonstration, and to keep things simple, we're going to use two for loops, which does give us the advantage that if there's more than one occurrence of the word in the grid, it will find all the occurrences. So now that we can visit every letter in the grid, we need to think about whether that letter is going to match the first letter of our word. Now here, we can make use of the fact that a string has an index for every letter. So word 0 in our example would be A, word 1 would be B, word 2 would be C. So we're looking for word 0 matching the letter in the grid and we can achieve this with a simple if statement.
If grid XY equals word 0, then we find a letter in the grid that matches the first letter of the word that we're looking for. So once we've found the first letter, we then need to expand our search to the adjacent letters. So we need to look at the one in the top left, we need to look at one above, the one in the top right, the one to the left, the one to the right, the one to the bottom left, the bottom, and the bottom right.
Now because we're storing all our letters in the grid in two lists, and we've got some numbers, then we can index those items and it can become quite straight. forwards. So you can see that if we're going to check the letter that is diagonally up to the left of the one that we're looking for, then it would have the relative coordinates of minus 1 and minus 1 from our original position. So in both the x and y, we need to check all the numbers from minus 1 to 1. That's minus 1, 0 and 1. For both the x and y, we need to add these offsets to our original X and Y positions.
Now, when we do this, there's a danger that the cells we end up checking are off the edge of the grid. And so we need to make sure we keep track of that. Otherwise, we're going to get an error when we run our program.
So we need to be saying if X plus the offset is greater than or equal to zero and X plus the offset. is less than or equal to 2 and y plus the offset is greater than or equal to zero, and y plus the offset is less than or equal to two, then we're OK to check if that's a letter in the grid. Otherwise, we can't because it would be outside the bounds.
So here we've introduced the variables i and j, representing the offsets from the original x and y positions. Now it can get a little bit confusing if you don't use sensible variable names, but for algorithms like this it's quite common to just use single letters for variable names. Perhaps it would have been better in this instance if we'd had offset x and offset y as names instead. So we can now go ahead and check if the letter in the offset position matches the second letter in our word, and we need to make sure that we're not going to check the original first letter as well. So we've got an exception to the rule.
If x plus the offset and y plus the offset equals zero, then that would be the first letter, and we don't want to check that again. So we've introduced just an extra little condition to the rule. Now at this point it might seem like our algorithm is getting quite complicated, and indeed if you were to try and write this algorithm from scratch just in one go, it would be quite difficult. which is why you need to apply problem decomposition and then step by step some algorithmic thinking, considering exactly what you want the computer to do. It makes solving the problem a little bit easier.
So once we've found a second letter, we then simply need to carry on in that direction to see if we can find a third and then subsequent letters up to the length of the string that we're looking for. So if the second letter was in an upwards direction, then we'd continue checking upwards. In a similar way, if the second letter was in the right direction, we would continue checking right.
And so at this point, we only need to change one of the variables to check all the other letters. So we introduce two new variables, o and p, which are then going to be incremented in the appropriate direction, so we can check the other letters. And we're going to check up until either we reach the edge of the grid, or we're going to reach the end of the word we're looking for.
So we introduce a statement that makes sure we stay within the bounds of the grid, and then we can check if the letter in the grid matches the letter in the word. At this point, we've used our algorithmic thinking to create a solution to the problem that will work for any word and any size grid. We just need to change the value of the constants in our program.
The final thing to do is to provide some sensible output. It would be handy if the program told us where it found the first letter of the word, and then which direction to look for the rest of the letters. So this little part of the program tells you the x and y coordinates where the first letter is found, and then whether you're going backwards, forwards, up, down, or diagonally. in order to find the rest of the word. And so that is how you can apply algorithmic thinking into writing a program that would solve a word search.
You can apply the same approach to any program, you just need to break the problem down, you need to think about what data is important to store and what data is not important to store using abstraction, and think about the relevant data structures that you've got in your programming language. which would enable you to store that data. Then, taking an algorithmic thinking approach, just take it step by step and solve each individual part of the problem to create a solution that can easily scale up to solve any similar problem. Now I will admit this skill is not easy when you're learning to program for the first time. It does take a certain amount of experience and certainly some perseverance.
You need to just keep trying and thinking logically about what you're trying to achieve and how a computer can actually achieve it.