String Search in Scratch

When I originally wrote the custom string blocks for Scratch, I posted a discussion on the ScratchEd site to let people know about them. I received a message a couple of weeks ago about adding a block that allows a string to be searched for a specific string (sub string). This is certainly a useful addition to the library of blocks and one I wanted to add when I had some free time.

Having found myself with the free time this morning, I have implemented a new custom block called FindString. FindString allows you to specify a string to be searched, a string to find and finally the search start character position within the string to be searched. The block is used as follows:

FindStringLooking at the example above, when executed, the block will search the string I like programming in Scratch for the string in starting at the character position 1 within our string to search. The block returns the start position of the string to find in a variable called startsAt. Executing the example will set startsAt to 16, as in starts at character position 16 in our string to search, if the string is not found, startsAt will be set to zero.

This block stops running after it has found the first occurrence of the string to search for. I will explain at the end how to search for more than one occurrence of a string.

How Does It Work?

So, how does the block work? Well, its actually very simple to follow. The image below shows the program code for the block.

Find String BlockWhen I first started writing the block, my first version used two loops (nested loops). The block worked fine, but after looking at the finished block, I realised that it could be re-written to use just one loop, making it a little easier to follow. So, lets break down the block above into logical steps to understand whats going on.

1. As we are doing a charcter by character comparison of the two strings, we need two variables to act as ‘pointers’ into our string to be searched and the string we are searching for. stringPos will hold the current character position in our string to be searched and subPos will hold the character position in the string we are searching for.

2. We initialise the startsAt variable to zero. Remember this variable holds the start position of our string we are searching for when the block has completed.

3. We now loop over the whole of the string to search for character by character, doing the following:

4. We check if the character at position stringPos in our string to be searched is the same as the character at position subPos in our string we are searching for. If they are, we first check if subPos is set to 1, if it is, we want to set startsAt to the value of stringPos, as this could possibly be the start location of our string to search for.

5. We then add 1 to both stringPos and subPos.

6. We next check to see if subPos (remember this is the character position in our string to search for) is equal to the length of our string to search for plus 1 character. If this is the case, we have actually found our string, so we can stop the block executing any further.

7. You may find what has been said in Step 6 confusing, but when we check if the characters from the two strings match in Step 4, if they don’t match, we set subPos back to 1 and add 1 to stringPos. We set subPos back to 1, as we want to continue searching the rest of the string should only a few of the characters of our string to search for has been found.

Its actually quite tricky to clearly explain in words what the block is doing, the best way to understand it is to look at it in Scratch, it really won’t be that hard to follow.

How Can I Search More Than Once Occurrence?

I did say at the beginning of this post that the block will only search for the first occurrence of a string, but what if you want to search for more than one occurrence of the same string? Well its very simple, all we need to do is keep calling the FindString block with a new start position. The easiest way is to do this in a loop and keep calling the block until startsAt equals zero. We will change the start position of each call to the FindString block by the position the last occurrence was found plus 1 character, this ensures we don’t find the same occurrence twice.

I have written a simple example below, that inserts all the positions of the occurrences in a list. The string we are going to search is “My cat likes to eat cat food. He is a happy cat” (I don’t have a cat by the way!). We will search for all the occurrences of the word cat. Shown below is the Scratch code to do this.

Occurrence CodeOnce this code has been run, the Occurances list will look as follows:

Occurrence ListAs you see, searching for multiple occurrences of string is quite a simple process. I hope you find the addition of this block useful and feel free to use it in any way you like.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s