Arsalan's Musings on Software

Software design and development techniques, ideas, and source code snippets…

Determine all 3,4,5 & 6-letter combinations within a jumble: C# Solution

leave a comment »

Problem:

Given a six-letter alphabetic jumble and a dictionary of words, determine all 3,4,5 & 6-letter
combinations within the jumble that are also words in the dictionary. Each letter in the jumble can be (but does not have to be) used only once per combination, however n occurrences of the same letter can be used n times. For example, given the jumble: ‘rlerta’, the words ‘tar’, ‘tale’, and ‘rear’ are among the legal combinations (and — assuming they are in the dictionary — words), but ‘rattle’ is not (there are not two t’s in the jumble).

Input: Six sets of data each consisting of a six-letter jumble (no spaces will be in the input), and a filename for the dictionary (the dictionary can be assumed to be in the same folder as the program, and will consist of an ascii text file with one word per line).

Output: the number of 3, 4, 5 & 6 letter words found in each jumble.

Sample Input (3 sets): Sample Output:
rndlae, dictionary.txt 17, 34, 13, 7
nuetbr, dictionary.txt 23, 29, 12, 4
zrftmx, dictionary.txt 0, 0, 0, 0

Dictionary can be found here.


Solution

Let’s make this a console application. The Main method looks like the following.


static void Main(string[] args)
{
if (args[0].ToLower().Equals("-i"))
{
// Interactive Mode
InteractiveMain();
return;
}

JumbleSolver aJumbleSolver = null;
string enteredJumble =  args[0];
string enteredFileName = args[1];

if (enteredJumble.Equals(String.Empty))
{
// error in argument
Console.WriteLine("There was an error in the first argument: Jumble");
Console.WriteLine("Abandoning execution...");
throw new ArgumentException("Jumble must be a valid string");
}

else if ((enteredFileName != String.Empty) && (File.Exists(enteredFileName)))
{
if (enteredJumble.EndsWith(","))
{
enteredJumble = enteredJumble.Remove(enteredJumble.Length - 1);
}

aJumbleSolver = new JumbleSolver(enteredJumble, enteredFileName);
}
else
{
// error in argument
Console.WriteLine("There was an error in the second argument: Dictionary");
Console.WriteLine("Abandoning execution...");
throw new ArgumentException("Dictionary must be a valid file name.");
}

// Count and display matches
if (aJumbleSolver.CountMatchingWords())
{
Console.Write(aJumbleSolver.MatchCount3Letters + ", ");
Console.Write(aJumbleSolver.MatchCount4Letters + ", ");
Console.Write(aJumbleSolver.MatchCount5Letters + ", ");
Console.Write(aJumbleSolver.MatchCount6Letters);
}
else
{
// There was an error in the CountMatchingWords method
Console.WriteLine("CountMatchingWords failed. Please make sure jumble does not contain space.");
}
}

If the first command line argument is valid then we call the InteractiveMain method to interact with the user.

public static void InteractiveMain()
{
#region Setting up lists
List set1 = new List();
List set2 = new List();
List set3 = new List();
List set4 = new List();
List set5 = new List();
List set6 = new List();

set1 = Console.ReadLine().Split().ToList();
set2 = Console.ReadLine().Split().ToList();
set3 = Console.ReadLine().Split().ToList();
set4 = Console.ReadLine().Split().ToList();
set5 = Console.ReadLine().Split().ToList();
set6 = Console.ReadLine().Split().ToList();

List
> allSets = new List
>();
allSets.Add(set1);
allSets.Add(set2);
allSets.Add(set3);
allSets.Add(set4);
allSets.Add(set5);
allSets.Add(set6);
#endregion

string enteredJumble;
string enteredFileName;
JumbleSolver aJumbleSolver = null;

foreach (List set in allSets)
{
enteredJumble = set[0];
enteredFileName = set[1];
if ((enteredFileName != String.Empty) && (File.Exists(enteredFileName)))
{
if (enteredJumble.EndsWith(","))
{
enteredJumble = enteredJumble.Remove(enteredJumble.Length - 1);
}

aJumbleSolver = new JumbleSolver(enteredJumble, enteredFileName);

// Count and display matches
if (aJumbleSolver.CountMatchingWords())
{
Console.Write(aJumbleSolver.MatchCount3Letters + ", ");
Console.Write(aJumbleSolver.MatchCount4Letters + ", ");
Console.Write(aJumbleSolver.MatchCount5Letters + ", ");
Console.WriteLine(aJumbleSolver.MatchCount6Letters);
}
else
{
// There was an error in the CountMatchingWords method
Console.WriteLine("CountMatchingWords failed. Please make sure jumble does not contain space.");
}
}
}

}

We define the JumbleSolver class to solve the jumble for us keeping the business logic in a separate class, potentially a separate assembly ready for reuse.

The constructors need 3 different flavors as follows.

public JumbleSolver()
        {
            this.wordDictionary = new List<string>();
            this.matchCount3Letters = 0;
            this.matchCount4Letters = 0;
            this.matchCount5Letters = 0;
            this.matchCount6Letters = 0;
        }

        public JumbleSolver(string jumble, string dictionaryFilePath) : this()
        {
            this.CurrentJumble = jumble;
            if (File.Exists(dictionaryFilePath))
            {
                string[] allWords = File.ReadAllLines(dictionaryFilePath);
                this.wordDictionary.AddRange(allWords);
            }
        }

        public JumbleSolver(string dictionaryFilePath) : this()
        {
            this.CurrentJumble = String.Empty;
            if (File.Exists(dictionaryFilePath))
            {
                string[] allWords = File.ReadAllLines(dictionaryFilePath);
                this.wordDictionary.AddRange(allWords);
            }
        }

We will define a WordDictionary List property.

public List</string><string> WordDictionary
        {
            get
            {
                return this.wordDictionary;
            }
            set
            {
                if (value is List</string><string>)
                {
                    this.wordDictionary = value;
                }
            }
        }

We also need a CurrentJumble property.

public string CurrentJumble
        {
            get
            {
                return this.jumble;
            }
            set
            {
                string evaluatingValue;
                if (value is string)
                {
                    evaluatingValue = value.Trim();
                    if (!evaluatingValue.Contains(' '))
                    {
                        this.jumble = evaluatingValue;
                    }
                    else
                    {
                        this.jumble = String.Empty;
                    }
                }
                
            }
        }

Let’s have a method to determine if the word is a match.

public bool IsWordAMatch(string word, string jumble)
        {
            List<char> jumbleLetters = new List</char><char>(jumble.ToCharArray());
            char[] wordLetters = word.ToCharArray();
            bool matchFound = false;

            foreach (char wordLetter in wordLetters)
            {
                if (jumbleLetters.Contains(wordLetter))
                {
                    // remove only the first occurance of wordLetter
                    jumbleLetters.Remove(wordLetter);
                    matchFound = true;
                }
                else
                {
                    matchFound = false;
                    break;
                }
            }
            
            return matchFound;
        }

And, finally, we want to encapsulate the counting of the matching words in a method like the following.

public bool CountMatchingWords()
{
if ((this.WordDictionary.Count <= 0) || (this.CurrentJumble.Equals(String.Empty))) { return false; } foreach (string word in this.WordDictionary) { if (word.Trim().Contains(' ')) { // malformed word. Abort. return false; } else if (IsWordAMatch(word.Trim(), CurrentJumble)) { switch (word.Trim().Length) { case 3: this.matchCount3Letters++; break; case 4: this.matchCount4Letters++; break; case 5: this.matchCount5Letters++; break; case 6: this.matchCount6Letters++; break; default: // Ignore words that do not match the above cases break; } } } return true; } [/code] In the next post, I will write some unit tests to have some degree of confidence in the accuracy of our results.

Advertisements

Written by Arsalan A.

July 7, 2009 at 9:32 am

Posted in 1

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

%d bloggers like this: