How to compare 2 strings with int out of errors?

KaktusJack

I've searched online for a diff algorithm but none of them do what I am looking for. It is for a texting contest (as in cell phone) and I need the entry text compared to the master text recording the errors along the way. I am semi-new to C# and I get most of the string functions and didn't think this was going to be that hard of a problem, but alas I just can't wrap my head around it.
I have a form with 2 rich-text-boxes (one on top of the other) and 2 buttons. The top box is the master text (string) and the bottom box is the entry text (string). Every contestant is sending a text to an email account, from the email we copy and paste the text into the Entry RTB and compare to the Master RTB. For each single word and single space counts as a thing to check. And for every error add 1 sec. to their time.

Examples:

Hello there! <= 3 checks (2 words and 1 space)
Helothere! <= 2 errors (Helo and space)
Hello there!! <= 1 error (extra ! at end of there!)

Hello there! How are you? <= 9 checks (5 words and 4 spaces)
Helothere!! How a re you? <= still 9 checks, 4 errors(helo, no space, extra !, and a space in are)
Hello there!@ Ho are yu?? <= 3 errors (@ at end of there!, no w, no o and extra ? (all errors are still under the 1 word)

What I have so far:
I've created 6 arrays (3 for master, 3 for entry) and they are

Char array of all chars
String array delimited with " " and also counting the " "
Int array with length of the string in each string array

My biggest trouble is if the entry text is wrong and shorter than the master. I keep getting IndexOutOfRange exceptions (understandably) but can't fathom how to go about checking and writing the code to compensate.
I hope I have made myself clear enough as to what I need help with. If anyone could give some code examples or something to shoot me in the right path would be very helpful.

22 Replies

Know the answer? Post it — somebody with the same question will find it here.

Suthish Nair15y ago
This was a good thread.. Thumps Up !
0
KaktusJack15y ago
@ Vupes: I do see now thank you, didn't even think of the line above. But thank you for your help. It will be a lot of work to get this to work the way I want so I might try in the future to make a program to check for everything. Right now I'm running out of time so..... Thanks again to all, {KJ}
0
Vulpes15y ago
With regard to the line:

if(words.Length == 1) return 1;

I put that in because, if there was only a single word in the original master string (unlikely but I like to cover as many possibilities as I can), then the following code wouldn't work because (unless we're processing the last word) it assumes there will be a 'next' word.

Also, we know that the single word can't be the same as 'entry', because if it were, then it would have been picked up by the earlier line:

if(master == entry) return 0;

So, there must therefore be exactly one error.

It's been an interesting exercise to try and come up with something though because, as Sam said, questions like this are rarely asked on C# forums.
0
KaktusJack15y ago
@ All:

I thank you all for trying to help! Especially you Vulpes. After countless hours and a weeks worth of work I decided to accept defeat and just use the Levenshtein Distance Algorithm and just change the error management. I went through so many ideas and trials that none was what I was looking for (although Vulpes's last code was the closest by far). I even tried to treat the situation as I was entering the entry text one character at a time and it worked great for a bit....I was so close, real close but oh well.

Again thanks to all who tried to help.

KaktusJack

My other post:
http://stackoverflow.com/questions/5335244/how-to-compare-2-strings-with-int-out-of-errors
0
KaktusJack15y ago
@ Vulpes:
I'm going to implement a cap check with your code and see if that helps.

I do have one question about the code you posted tho.

if(words.Length == 1) return 1; // we know they're not the same so 1 error

I'm not sure as what this was supposed to do. I commented it out and it still worked and as far as logic I would think that but it doesn't check anything to know they're not the same. So that was kind of my question.

{KJ}
0
Vulpes15y ago
If you don't want to regard incorrect capitalization as an error, then you can just apply the ToLower() method to both the 'master' and 'entry' strings before you begin the comparison.
0
KaktusJack15y ago
@ Vulpes: That last bit of code is by far the closest!! The only thing I can see is that it has issues with caps and non-caps. That's all I can see so far. I'm working with the Levenshtein Distance to come up with something as well.
0
Sam Hobbs15y ago
Comparing strings to determine whether they are the same is common of course. Determining differences in strings where the differences are in a specified manner is rare but does happen. I think it is more common to compare large pieces of text, such as source code or other documents. I have seen roughly 10 thousand questions (at least) in forums in various web sites (mainly CodeGuru and MSDN as well as here) and I think this is the first time I have seen this asked. I have seen a few asking how to find differences in source code and/or documents. I have seen a couple of questions asking how to compare a word to the words in a list, as for a Hangman game.
0
Vulpes15y ago
Calculating WPM and highlighting errors as the user types by comparing each keypress with the master text aren't too difficult.

The problem here is that we're comparing whole words and spaces (or the lack of them) between words. This is much more difficult because we don't always know where the words begin and end. Also, if they can contain embedded spaces as well, it's difficult to distinguish word separators from content. Some sentences may be ambiguous even to a human reader.

As Sam said, there are some sophisticated algorithms for comparing differences between files (see http://en.wikipedia.org/wiki/Diff) and I'm sure there are better ways of doing it than I've been able to come up with.
0
KaktusJack15y ago
@ Vulpes: I will give this a try when I get home. I appreciate the help. I just don't understand why this isn't more common of a problem. I mean there are 100's of software apps that are for typing. They give WPM, and errors and pretty colors to highlight things. With all of these I thought this would be a goal I could accomplish. Hmm...
0
Vulpes15y ago
OK, this is my latest (and probably last) attempt at this.

I've dealt with the problem of extra characters at the end of words by creating a spaceless version of 'entry' and then testing whether the following character is the first character of the next word.

As the spaceless entry would give a match for a combination such as "a re" and the presence of the extra space would also reduce the error tally by 1, I've compensated for this by looking to see whether 'entry' (without removing the spaces) contains "are" and if it doesn't adding 2 to the error tally. This works for one embedded space but overcompensates for two or more embedded spaces (i.e. "a r e") and I haven't been able to figure out a way to cope with this.

I'm sure there will be some other cases we haven't considered which it won't cope with either but FWIW here it is:

using System;
using System.Text;

class Kaktus
{
   static void Main()
   {
   string master = "Hello there!";
   string entry = "Helothere!";
   Console.WriteLine("{0} error(s)", CountErrors(master, entry)); // 2, correct
   entry = "Hello there!!";
   Console.WriteLine("{0} error(s)", CountErrors(master, entry)); // 1, correct
   master = "Hello there! How are you?";
   entry = "Helothere!! How a re you?";
   Console.WriteLine("{0} error(s)", CountErrors(master, entry)); // 4, correct
   entry = "Hello there!@ Ho are yu??";
   Console.WriteLine("{0} error(s)", CountErrors(master, entry)); // 3, correct

   Console.ReadKey();
   }

   static int CountErrors(string master, string entry)
   {
   master = master.Trim(); // get rid of leading and trailing space
   entry = entry.Trim(); // ditto

   if(master == entry) return 0; // if they're the same, there are no errors

   string[] words = master.Split(' ');

   if(words.Length == 1) return 1; // we know they're not the same so 1 error

   int errors = 0;
   int mSpaces = CountSpaces(master);
   int eSpaces = CountSpaces(entry);
   if (eSpaces != mSpaces) errors += Math.Abs(mSpaces - eSpaces);

   string spaceless = entry.Replace(" ", "");

   for(int i = 0; i < words.Length; i++)
   {
   if (i == 0)
   {
   if (!spaceless.StartsWith(words[0] + words[1][0]))
   errors++;
   else if (!entry.StartsWith(words[0]))
   errors += 2;
   }
   else if (i == words.Length - 1)
   {
   if (!spaceless.EndsWith(words[i]))
   errors++;
   else if(!entry.EndsWith(words[i]))
   errors += 2;
   }
   else
   {
   if (!spaceless.Contains(words[i] + words[i+1][0]))
   errors++;
   else if(!entry.Contains(words[i]))
   errors += 2;
   }
   }

   return errors;
   }

   static int CountSpaces(string s)
   {
   int count = 0;
   foreach(char c in s) if(c==' ') count++;
   return count;
   }
}
0
KaktusJack15y ago
@ Sam: Yeah that ain't no ....... umm....your right! :). The length of any given text message on cell devices is max of 160 by default. So the text char would never exceed 160...that is if someone has a phone that could go over. But either way, it should be close to 160 and the program should check anyway.

thanks for replying.
0
Sam Hobbs15y ago
As you are discovering, comparisons such as this are more difficult than many people would think. There are sophisticated algorithms for comparing files, such as source code file. You probably don't need something that sophisticated but the longer that the text is, the more sophisticated your requirements become.
0
KaktusJack15y ago
@ Vulpes: I thank you for your time and effort. My train of thought is stuck and I can come up with only one way of doing it properly. I just can't dig into it with code.

In my head:

first check if strings match if they do then its done. if not then check StringArray if they compare. If they do, for loop and continue until they don't. If they don't then manage somehow to check the CharPerString.Length to see if the lengths are the same. If not then 1 error. Problem starts here if the space is missing and the second word is part of first word. Then I think that maybe we check if next mStringArray index is space, if so continue to next mStringArray. If the substring is found in first word then we have to do something to get it to count 1 for word1 and 1 for space then check for word two and start from there again to continue. Or check the two words on each side of the first space then compare to the first 3 entry ones. If words or substrings are found and blabla then we have to check to see if the spaces are right......

Wow! Look at me go. Ok.

Maybe this will help someone with a greater knowledge of the C# language to do more with that train of thought.
0
Vulpes15y ago
Now that I'm clear what you're trying to do, I'm posting my latest attempt at this which, as you'll see, is still far from perfect because it doesn't really deal with the 'awkward' cases at all. Basically, what I've done is broken up the master string into words and then looked to see how many of those words are present (not necessarily as individual words) in the entry string and then adjusted the result by the difference in the number of spaces between the two strings.

It seems to be one of those problems which is easy for humans (with our fuzzy logic) to solve by inspection but difficult to program a computer to do. Particularly awkward is having to deal with words which might have extra characters at the end or an embedded space in them, when we're using spaces to split the string into words in the first place!  Anyway, you (or someone else) might be able to use this as a basis for finding a more accurate solution:

using System;
using System.Text;

class Kaktus
{
   static void Main()
   {
   string master = "Hello there!";
   string entry = "Helothere!";
   Console.WriteLine("{0} error(s)", CountErrors(master, entry)); // 2, correct
   entry = "Hello there!!";
   Console.WriteLine("{0} error(s)", CountErrors(master, entry)); // 0, should be 1
   master = "Hello there! How are you?";
   entry = "Helothere!! How a re you?";
   Console.WriteLine("{0} error(s)", CountErrors(master, entry)); // 2, should be 4
   entry = "Hello there!@ Ho are yu??";
   Console.WriteLine("{0} error(s)", CountErrors(master, entry)); // 2, should be 3

   Console.ReadKey();
   }

   static int CountErrors(string master, string entry)
   {
   int errors = 0;

   int mSpaces = CountSpaces(master);
   int eSpaces = CountSpaces(entry);
   if (eSpaces != mSpaces) errors += Math.Abs(mSpaces - eSpaces);

   string[] words = master.Split(' ');

   foreach(string word in words)
   {
   if (!entry.Contains(word)) errors++;
   }

   return errors;
   }

   static int CountSpaces(string s)
   {
   int count = 0;
   foreach(char c in s) if(c==' ') count++;
   return count;
   }
}

0
KaktusJack15y ago
I did run it and the instance I gave was correct 2 errors. But this "Hello there! How are you?(M) vs "Helothere! How a re yu??"(E) was 15 errors which should only be 3. However, it did not throw the exception so that's at least a start.
0
Vulpes15y ago
I tried my code before posting it and it doesn't throw an exception if the entry string is shorter than the master string because it assumes that if there's a mismatch then the entry string is missing a character at that position and adjusts the index for subsequent comparisons accordingly.

However, this isn't a very sophisticated way of doing things and, when I have a bit more time, I'll have another think about it.
0
KaktusJack15y ago
@ Vulpes and Suthish: I believe your first for loop would throw my exception i get all the time. If the Entry text is less than the master i get OutOfBounds. If the Entry is more than the master I get OuOfBounds. I updated my original post hopefully to better understand my quest, rules and all.
0
Suthish Nair15y ago
Hope this also...

string[] master = ("Hello there!").Split(' ');

   string entry = "Helothere!";
   int errors = 0;
   List ss = new List();

   for (int i = 0; i < master.Length; i++)
   {
   if (!entry.ToString().Contains(master[i]))
   {
   ss.Add(master[i]);
   errors += 1;
   }
   }

   Console.WriteLine("Errors: {0}", errors);
   Console.WriteLine("");

   if (ss.Count > 0) { Console.WriteLine("Following words not found from entry text:"); }
   foreach (var item in ss)
   {
   Console.WriteLine(item);
   }
   ss = null;
   Console.ReadKey();

0
Vulpes15y ago
I'm not completely clear on the rules but does this help?

using System;

class Kaktus
{
   static void Main()
   {
   string master = "Hello there!";
   string entry = "Helothere!";

   int errors = 0;

   for(int i = 0; i < master.Length; i++)
   {
   if (master[i] != entry[i - errors]) errors++;
   }

   if(entry.Length + errors > master.Length) errors += entry.Length + errors - master.Length;
   string verb = (errors != 1) ? "were" : "was";
   string plural = (errors != 1) ? "s" : "";
   Console.WriteLine("There {0} {1} error{2}", verb, errors, plural);
   Console.ReadKey();
   }
}
0
KaktusJack15y ago
@ Krishna: Thank you for the reply. I looked over the site and downloaded the code. I will dig into it tomorrow and see what I can come up with.
0
Krishna Garad15y ago
Take a look here it may help you.
0