C# Yields a better Fibonacci Sequence

In the title of this blog entry I've done a bit of punning. This quick blog entry is about an alternate usage of the Yield command and how, for example, it can help build a better FibonacciSequence() function.

With the addition of the Yield command, we can now create looping functions that return a value for each iteration. Ever need to walk through a sequence and perform some fuction for each element? Now it is as easy as pie!

private IEnumerable FibonacciSequence(int MaxIterations)
{
    decimal i = 0;
    decimal j = 1;

    while(true)
    {
        yield return j;
        MaxIterations--;

        if (MaxIterations==0) yield break;

        var temp = (ulong) j;
        j = temp+i;
        i = temp; 
    }
}

private IEnumerable FibonacciSequence()
{
    return FibonacciSequence(49);
}

C# - Counting the number of occurrences of a substring - Take two

In my last post, I stated that I knew of only one way to find a count of all the substrings within a string without looping through the string. Well, a co-worker pointed out to me the other day that I had shown a non-looping way to count all the substrings within a string when I gave a class on Regular Expressions.

That is true. A very simple Regular expression:

new Regex(mySubString).Matches(myString).Count

But, that simple line of code is not the reason for this post. I've found an even deeper issue, and it all comes down to how you define the problem (doesn't it always).

Lets say that my string is "BOBOBOB"

How many instances of the substring "BOB" is in "BOBOBOB"? 2 or 3?

My way in the previous post and the regular expression both agree, the number is 2.

But, say you are writing a game and you are using a string to store previous moves. Each move can have only two choices: a 0 or a 1. So after a number of moves, the storage string could look like this "0111110010100111110110111101".

Now, how many times did the player choose to play a 1 after playing a 1 the prior two moves, i.e. a "111"? If you did a substring search, you would get a 3. But if you count the number of times "111" appear including overlap, the number is much higher: 8.

So, an AI routine that was based on prior moves would need to find all combinations of "111" even if one set is partially contained within another.

So, here is my LOOP that counts the number of substrings within a string, even if the substring is partially contained within another substring.

for (var i = 0; i <= myString.Length - mySubString.Length; i++)
{
    if (myString.Substring(i, mySubString.Length) == mySubString)
    {
        count++;
    }
}

C# - Counting the number of occurrences of a substring

How many times have you needed to find the total number of times a substring has appeared within a string? This common programming problem can be approached from many different angles.

You could write brute force code that walks through the string and looks at it character by character, keeping a tally of how many complete matches with the substring was found.

You could use IndexOf within a while loop, incrementing the counter and moving the start point on each iteration of the loop, exiting the loop when IndexOf returns that there are no more occurrences of the substring.

But, there is only one way that I know how to do it without a loop. Use the Replace method of string.

Here is a code snippet showing how to use this very simple yet powerful way to count the number of occurrences of a substring within a string.

string myString = "Lorem ipsum dolor sit amet, " +
    "consectetur adipisicing elit, sed do eiusmod " +
    "tempor incididunt ut labore et dolore magna " +
    "aliqua. Ut enim ad minim veniam, quis nostrud " +
    "exercitation ullamco laboris nisi ut aliquip " +
    "ex ea commodo consequat. Duis aute irure " +
    "dolor in reprehenderit in voluptate velit " +
    "esse cillum dolore eu fugiat nulla pariatur. " +
    "Excepteur sint occaecat cupidatat non proident, " +
    "sunt in culpa qui officia deserunt mollit anim " +
    "id est laborum.";

string mySubString = "dolor";

int Count = (myString.Length - 
             myString.Replace(mySubString, string.Empty).Length)
             / mySubString.Length;

This will return a count of 4, the correct number without a single loop in your code!

This code is case sensitive. To create a case insensitive version, just move myString and mySubString to lowercase.

string mySubString = "lo";

int Count = (myString.Length - 
             myString.ToLower().Replace(mySubString.ToLower(), 
             string.Empty).Length) / mySubString.Length;

The case sensitive version would have only returned 4 because it would not have found the first lo at the beginning because the L in Lorem is capitalized. But with the case insensitive version, the code correctly finds all 5 instances of our substring.

This may seem like such a small thing, but everyday programming is filled with these "Old School" tricks!