Trivia for the weekend: Get the number of occurrences of text in a string

For the fun of it, try to solve this during the weekend. I've got this simple puzzle from the friend working in MSDN, enjoy!

Language: C#
Difficulty: Easy
Familiarity: Famous puzzle in programming job interviews/exam in most companies in the United States
Problem: Get the number of times a particular text has occurred in a sentence without looping.

Example:

   string sentence = "As much as I hate to, " +
                     "I have to go to school tomorrow";
   string text = "to";

The answer to the above example is 4:
"As much as I hate to, I have to go to school tomorrow" = 4 occurrences

      int occurrences = ...;
      MessageBox.Show(occurrences.ToString() + " occurrences");

Restrictions: No looping, and without using IndexOf/IndexOfAny/Split string methods.
Time Limit: Answer will be posted on Tuesday.

Enjoy

-chris

here's my entry

[code language="C#"]

using System;
using System.Text;
using System.Text.RegularExpressions;

namespace CountWordOccurence
{
 class CountInstance
 {
  [STAThread]
  static void Main(string[] args)
  {
   string sentence = "As much as I hate to, " +
    "I have to go to school tomorrow";
   string key = "to";

   int occurence = CountOccurenceOfWord(sentence,key);
   Console.WriteLine("Source: " + sentence);
   Console.WriteLine("Search Key: " + key);
   Console.WriteLine("Number of Occurence: " + occurence);
   Console.ReadLine();
  }

  public static int CountOccurenceOfWord(string source, string searchKey)
  {
   int wordCount = 0;
   Regex regExp = new Regex(searchKey);
   MatchCollection matches = regExp.Matches(source,0);
   wordCount= matches.Count;
   return wordCount;
  }
 }
}

[/code]

my entry :)

static void Main(string[] args)

{

           string sentence = "As much as I hate to, " +
                                     "I have to go to school tomorrow";

           string text = "to";

           int occurence = CountOccurence(sentence, text, 0);

           Console.WriteLine(occurence.ToString() + "occurrences");

}

static int CountOccurence(string sentence, string countThisText, int startPos)
{

        int counter = 0;

        if (startPos + countThisText.Length <= sentence.Length)
        {
                if (sentence.Substring(startPos, countThisText.Length) == countThisText)
                {
                     counter++;
                     startPos += countThisText.Length;
                }
                else
                {
                     startPos++;
                }

                counter += CountOccurence(sentence, countThisText, startPos);

        }

        return counter;

}

recursion, passing the modified target string each time
but I like keith's implementation.. sweet

[code language="C#"]
using System;                                                                  

namespace ConsoleApplication4
{                                                                                    
    class Program
    {
        static void Main(string[] args)
        {
            String srchString = "to";
            String targString = "As much as I hate to, " +
                                     "I have to go to school tomorrow";
            int occurences = 0;                                                   
            occurences = CountNumOcc(srchString, targString);
            Console.WriteLine("Number of times '{0}', appeared in '{1}' is :{2} time(s)", srchString, targString, occurences );
        }

        public static int CountNumOcc(string keyStr, string targetString)
        {
            int numTimes=0;          
          
            if (targetString.Length >= keyStr.Length)
            {
                if (targetString.Substring(0,keyStr.Length ) == keyStr)
                {
                    numTimes++;
                }
                numTimes += CountNumOcc(keyStr, targetString.Substring(1));
            }
            return numTimes;
        }


    }
}
[/code]

that's what i thought of too...use RegEx

nice work keith

 I think using RegEx is like the Math.Abs call in the comparison trivia question. There's most likely a loop inside the RegEx implementation.

I like dotnetapp's implementation, it's efficient.

And the answer for the current problem

Here are the answer forwarded to me (sorry for the delay, I also waited for the answer):

Using Replace to empty/Length calculation:

int occurrence;
occurrence = sentence.Length;
occurrence -= sentence.Replace(text, string.Empty).Length;
occurrence /= text.Length;

Recursive function call:

private int RecurseCount(string sentence, string text)
{
 if (sentence.Length > 0)
 {
  if (sentence.StartsWith(text))
  {
   return RecurseCount(sentence.Remove(0, text.Length), text) + 1;
  }
  else
  {
   return RecurseCount(sentence.Remove(0, 1), text);
  }
 }
 return 0;
}

Here are the summary of 12 submitted solutions, 3 was posted in the thread, 1 from private message and the rest of solutions are emailed to me (4 of the emails are private message notifications from other online community):

3 solutions using RegEx:

CryptoKnight:
        int count = Regex.Matches(sentence, text).Count;
        Response.Write(count);

Marsman (marsman_magic@yahoo.com):
        int occurences = Regex.Matches(sentence, text).Count;
        MessageBox.Show(occurences.ToString());

Keith's solution is posted in this thread.

5 solutions using Recursive function call:

dotnetapp and bonskijr's solution is posted in the thread.

IAmRicky (IAmRicky@gmail.com, NosinanGuy (other community), and Dr. (other community) sent the solution almost exactly similar to above recursive function:

private int NumberOfText(string sentence, string text)
{
 if (sentence.Length > 0)
 {
  int extends = 1;
  if (sentence.StartsWith(text))
  {
   extends = text.Length;
  }
  return NumberOfText(sentence.Remove(0, extends), text);
 }
 return 0;
}

The sent different functions with different function names, and for this summary I've merged them into one function using Dr.'s solution.

Other 4 solutions are either incorrectly producing output and/or using while loop which is one of the restrictions.

No one got the solution using the first approach, which is using Replace/Length calculation.


A little trivia regarding this puzzle

According to a friend working in Microsoft who has given me this puzzle, the most common answer in this puzzle is using regular expressions, that's why he adviced me not to include RegEx as part of the restrictions. On our case, based on summary of sent solutions, DevPinoy's most common answer is not RegEx but recursive function call.

Another trivia: though it is already mentioned in the familiarity of the puzzle, this is common in job interviews and exams for programming position (not only in U.S.). So, the next time you're into job hunting, there may be a chance that you'll be asked to solve this puzzle, but that time, you are already prepared, thanks to those who submitted their solutions, listed in the summary above.

In closing

Once again, thank you for your participation, and compliments to those who sent their solution. Keith mentioned before that he is working on a recognition system for DevPinoy for mini-puzzles solving like this.

See you next time, hope you enjoy it, cheers

-chris

the first solution(The Replace) is quite fast(I used your benchmark in your string vs sb post) , the sentence in question is a 10KB file and even on a 60KB file. It was the only one w/c was able to handle bigger than 10KB sentence and was fast enough (shade under 2 seconds.) Word counter is good application for this one.

Note though: 
[code language="C#"]private int NumberOfText(string sentence, string text)
{
if (sentence.Length > 0)
{
int extends = 1;
if (sentence.StartsWith(text))
{
extends = text.Length;
}
return NumberOfText(sentence.Remove(0, extends), text);
}
return 0;
}[/code]
this one didn't find any occurences at least on my test...

Hi bonskijr,

Thanks for testing it. None of the posted codes in the summary are mine, those are all submitted to me, so I can't actually make any correction with any of those (though I made a modification to merge 3 similar functions, I didn't alter the actual functions itself), I will inform the sender about their function for inaccuracy, thanks again, cheers 

Also, this morning I've receive a message that I shouldn't included senders who are not part of this community (DevPinoy), I was thinking, but DevPinoy is searchable via google, and people who are not member of this community may view the postings, hence may provide an answer to the posted problem, and it happens that they sent the solution to my email (which is also visible). I would like to ask for opinions from your guys regarding this, if majority think that only members of DevPinoy can send their solution, then I will deal with it.

Thanks,

-chris

i think we should accept solutions from non-devpinoy forumers and we should also encourage them to become forumers here at devpinoy, pinoy or not

anyway i appreciate the stuff that you do chris. keep it up!

I have no problem with non-devpinoy submitting their solution(s), the more solution(s) we have the better we know. As we know already that a problem( or an oppurtunity for a solution for optismists) can have a variety of solutions, so getting solutions from non-members are welcome(at least for me.) Maybe instead you can encourage them to join so that they become members(even if they're not pinoy) Maybe if you receive a well written solution, publish it after all member solutions are made. And one more thing, I think PMng the solution(s) shouldn't be encouraged as the community isn't able to see how they come up with it.

Thanks

bonskijr:

I have no problem with non-devpinoy submitting their solution(s), the more solution(s) we have the better we know. As we know already that a problem( or an oppurtunity for a solution for optismists) can have a variety of solutions, so getting solutions from non-members are welcome(at least for me.) Maybe instead you can encourage them to join so that they become members(even if they're not pinoy) Maybe if you receive a well written solution, publish it after all member solutions are made. And one more thing, I think PMng the solution(s) shouldn't be encouraged as the community isn't able to see how they come up with it.

Thanks

yeah, devpinoy is totally searchable :) i just got an email today talking about my comments on one of the blogs here asking for help.. the other one giving further explanation on one of my comments to a blog post by a member here in devpinoy!

every coder has his own take on a programming trivia thats why we should'nt limit the people who are joining the puzzles and the community itself.. after all we are starting to be a code bank and anybody who is willing to deposit is welcome :)

Thanks for the opinions guys, I think that's what I'm going to do, I will continue accepting sent solutions from communities other than DevPinoy for posted puzzles.

With regard to DevPinoy being "searchable" via google, my blog post Swapping two values using XOR has many hits in google (and other seach engines), for which I received many questions in my mailbox asking how to do the same in "immutable strings" of .NET, not because I asked that question in msforums.ph, but because somewhere else, somebody has given the same question as a programming puzzle, and the participants of that programming puzzle is looking for answer in which they are redirected to my blog post.


Regards,

-chris

I tried doing it so i haven't read the rest of the thread yet. But i did manage to do it in under 30 minutes, my stopwatch says 21:58, but i wasted a few minutes understanding the question before i decided to try it. It's in Delphi, the only language i have on hand at the moment.

procedure TForm1.FormCreate(Sender: TObject);
var
   sentence,text:String;
   B: String;
begin
   memo1.Clear;
   sentence := 'As much as I hate to, I have to go to school tomorrow';
   text := 'to';
   memo1.lines.add ( inttostr(rstr(sentence, text)));
end;

function TForm1.rstr(Orig,key:String): Integer;
var
   I: Integer;
begin
   if LeftStr(Orig,2)=key then result := 1 else result := 0;
   if length(orig)>length(key) then
      Result := Result + rstr(rightstr(orig,length(orig)-1),key);
end;

Jeez, 22 minutes for a simple recursion @_@ Gonna read the rest of the thread now. See how the others did it. =)


EDIT: Whoops, it's a C# puzzle. So sorry.

Hajile:

I tried doing it so i haven't read the rest of the thread yet. But i did manage to do it in under 30 minutes, my stopwatch says 21:58, but i wasted a few minutes understanding the question before i decided to try it. It's in Delphi, the only language i have on hand at the moment.

procedure TForm1.FormCreate(Sender: TObject);
var
   sentence,text:String;
   B: String;
begin
   memo1.Clear;
   sentence := 'As much as I hate to, I have to go to school tomorrow';
   text := 'to';
   memo1.lines.add ( inttostr(rstr(sentence, text)));
end;

function TForm1.rstr(Orig,key:String): Integer;
var
   I: Integer;
begin
   if LeftStr(Orig,2)=key then result := 1 else result := 0;
   if length(orig)>length(key) then
      Result := Result + rstr(rightstr(orig,length(orig)-1),key);
end;

Jeez, 22 minutes for a simple recursion @_@ Gonna read the rest of the thread now. See how the others did it. =)


EDIT: Whoops, it's a C# puzzle. So sorry.

Its ok Hajile! Its nice to see how people do it in a different language too :) i havent seen Delphi code for years now and this made me remember the old days when Pascal was cool :)