Arsalan's Musings on Software

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

Archive for July 2009

Creating an unmodifiable list from a regular old IList

leave a comment »

Your Mission

Create an unmodifiable list utility class that converts any implementation of IList interface into a list that throws exception when modified.  Take into consideration converting implementations of ArrayList<T>.
Give examples of useful usages of such utility class (does not have to be in code).

Do you accept this mission?

Hmmm… let’s see.


Why would anyone want to use a list that cannot be modified?

Consider the following scenarios.
1. Sending an Employee list to an accounting system using RPC, ensuring the list cannot be changed. In such a case, a class can be passed to the Sealed list constructor to get a sealed class and passed on to the remote system.

2. If the list is bound to a control on a Web Form or Windows Form and the control has edit functionality, if the user edits the form and the list could be modified, the sealed list class can be used.

3. A deck of cards [fixed number of items] should not allow addition of other cards in a card game.

There maybe many such cases where you want the collection to stay as-is.


Design

Let’s design the solution using the Decorator design pattern. The decorator pattern is quite fascinating as it creates a paradigm of wrapping increasingly specialized behavior to objects while keeping their base type uniform. Hence, one type decorates another and effectively changes the behavior without modifying existing code. Superb!

Wikipedia has this nice diagram describing our Decorator pattern:
Decorator Pattern


We will start creating our SealedList class as follows.

private IList list;
private const string exceptionMessage = "List cannot be modified.";

public SealedList(IList list)
{
this.list = list;
}

We will make sure that our custom class implements the IList interface. We will not need to implement all the required methods in IList simply throwing a NotImplementedException for methods not implemented. We can always implement them later, if needed. Here are the IList methods.

public int Add(object value)
{
throw new InvalidOperationException(exceptionMessage);
}

public void Clear()
{
throw new InvalidOperationException(exceptionMessage);
}

public bool Contains(object value)
{
return list.Contains(value);
}

public int IndexOf(object value)
{
return list.IndexOf(value);
}

public void Insert(int index, object value)
{
throw new InvalidOperationException(exceptionMessage);
}

public bool IsFixedSize
{
get
{
return list.IsFixedSize;
}
}

public bool IsReadOnly
{
get
{
return list.IsReadOnly;
}
}

public void Remove(object value)
{
throw new InvalidOperationException(exceptionMessage);
}

public void RemoveAt(int index)
{
throw new InvalidOperationException(exceptionMessage);
}

public object this[int index]
{
get
{
return list[index];
}
set
{
throw new InvalidOperationException(exceptionMessage);
}
}

Since the IList interface itself implements the ICollection and IEnumerable interfaces, we have to implement methods required by those interfaces as well.

#region ICollection Members

public void CopyTo(Array array, int index)
{
list.CopyTo(array, index);
}

public int Count
{
get
{
return list.Count;
}
}

public bool IsSynchronized
{
get
{
return list.IsSynchronized;
}
}

public object SyncRoot
{
get
{
return list.SyncRoot;
}
}

#endregion

#region IEnumerable Members

public IEnumerator GetEnumerator()
{
return list.GetEnumerator();
}

#endregion

That should do it as far as creating the sealed list is concerned. But we still haven’t verified that this works correctly. For that, we will have to create an unsealed list and then try to seal it by decorating it with our SealedList and unit test the heck out of it… stay tuned for the exciting conclusion in the next post!

Advertisements

Written by Arsalan A.

July 7, 2009 at 10:50 am

Posted in 1

Writing unit tests for the Jumble problem

leave a comment »

Let’s write some unit tests for the jumble problem solved in the previous post.

We will create some setup and teardown code that will be executed before and after running each test, respectively. We will use the NUnit framework to write our tests. To run the tests we can either use the NUnit Graphical User Interface or the excellent Visual Studio plugin TestDriven.Net which allows inline debugging of our tests. Way cool!

#region ----- Private Members -----
JumbleSolver simpleJumble;
JumbleSolver jumbleWithWordDictionaryFile;
const string dictionaryFilePath = @"dictionary.txt";
#endregion

#region ----- Setup and Teardown -----
[SetUp]
public void Setup()
{
this.simpleJumble = new JumbleSolver();
this.jumbleWithWordDictionaryFile = new JumbleSolver(dictionaryFilePath);
}

[TearDown]
public void TearDown()
{
this.simpleJumble = null;
this.jumbleWithWordDictionaryFile = null;
}
#endregion

Tests

I often like to divide the tests into Happy Path and Negative Test regions.

Happy Path Tests

#region ---------- Happy Path Tests ----------
[Test]
public void SimpleTestIsWordAMatch3Letters()
{
// Arrange
string word = "ran";
string jumble = "rndlae";

// Act
bool isMatch = simpleJumble.IsWordAMatch(word, jumble);

// Assert
Assert.AreEqual(true, isMatch, "The IsWordAMatch method failed for a 3 letter combination");
}

[Test]
public void SimpleTestIsWordAMatch4Letters()
{
string word = "lean";
string jumble = "rndlae";
bool isMatch = simpleJumble.IsWordAMatch(word, jumble);
Assert.AreEqual(true, isMatch, "The IsWordAMatch method failed for a 3 letter combination");
}

[Test]
public void SimpleTestIsWordAMatch5Letters()
{
string word = "ldean";
string jumble = "rndlae";
bool isMatch = simpleJumble.IsWordAMatch(word, jumble);
Assert.AreEqual(true, isMatch, "The IsWordAMatch method failed for a 3 letter combination");
}

[Test]
public void SimpleTestIsWordAMatch6Letters()
{
string word = "lander";
string jumble = "rndlae";
bool isMatch = simpleJumble.IsWordAMatch(word, jumble);
Assert.AreEqual(true, isMatch, "The IsWordAMatch method failed for a 3 letter combination");
}

[Test]
public void SimpleTestCountMatchingWords()
{
List dictionary = new List();
dictionary.Add("ace");
dictionary.Add("are");
dictionary.Add("dak");
dictionary.Add("ross");
dictionary.Add("rosy");
dictionary.Add("rynd");
dictionary.Add("rddnol");;
dictionary.Add("rndle");
dictionary.Add("rlead");

simpleJumble.CurrentJumble = "rndlae";
simpleJumble.WordDictionary = dictionary;
bool didCountSucceed = simpleJumble.CountMatchingWords();
Assert.AreEqual(true, didCountSucceed, "The CountMatchingWords method failed for the jumble 'rndlae'");
}

[Test]
public void MajorTestCountMatchingWords1()
{
jumbleWithWordDictionaryFile.CurrentJumble = "nuetbr";
bool didCountSucceed = jumbleWithWordDictionaryFile.CountMatchingWords();
Assert.AreEqual(true, didCountSucceed, "The CountMatchingWords method failed for the jumble 'rndlae'");

string expectedOutput = "23, 29, 12, 4";
string actualOutput = jumbleWithWordDictionaryFile.MatchCount3Letters.ToString();
actualOutput += ", ";
actualOutput += jumbleWithWordDictionaryFile.MatchCount4Letters.ToString();
actualOutput += ", ";
actualOutput += jumbleWithWordDictionaryFile.MatchCount5Letters.ToString();
actualOutput += ", ";
actualOutput += jumbleWithWordDictionaryFile.MatchCount6Letters;
Assert.AreEqual(expectedOutput, actualOutput, "The CountMatchingOutput method calculated in accurate results.");
}

[Test]
public void MajorTestCountMatchingWords2()
{
jumbleWithWordDictionaryFile.CurrentJumble = "zrftmx";
bool didCountSucceed = jumbleWithWordDictionaryFile.CountMatchingWords();
Assert.AreEqual(true, didCountSucceed, "The CountMatchingWords method failed for the jumble 'rndlae'");

string expectedOutput = "0, 0, 0, 0";
string actualOutput = jumbleWithWordDictionaryFile.MatchCount3Letters.ToString();
actualOutput += ", ";
actualOutput += jumbleWithWordDictionaryFile.MatchCount4Letters.ToString();
actualOutput += ", ";
actualOutput += jumbleWithWordDictionaryFile.MatchCount5Letters.ToString();
actualOutput += ", ";
actualOutput += jumbleWithWordDictionaryFile.MatchCount6Letters;
Assert.AreEqual(expectedOutput, actualOutput, "The CountMatchingOutput method calculated inaccurate results.");
}

[Test]
public void SimpleTestCountMatchingWordsNoMatchesFound()
{
List dictionary = new List();
dictionary.Add("ace");
dictionary.Add("are");
dictionary.Add("dak");
dictionary.Add("ross");
dictionary.Add("rosy");
dictionary.Add("rynd");
dictionary.Add("rddnol"); ;
dictionary.Add("rndle");
dictionary.Add("rlead");

simpleJumble.CurrentJumble = "xyzzqw";
simpleJumble.WordDictionary = dictionary;
bool didCountSucceed = simpleJumble.CountMatchingWords();
Assert.AreEqual(true, didCountSucceed, "The CountMatchingWords method failed for the jumble 'xyzzqw'");

string expectedOutput = "0, 0, 0, 0";
string actualOutput = jumbleWithWordDictionaryFile.MatchCount3Letters.ToString();
actualOutput += ", ";
actualOutput += jumbleWithWordDictionaryFile.MatchCount4Letters.ToString();
actualOutput += ", ";
actualOutput += jumbleWithWordDictionaryFile.MatchCount5Letters.ToString();
actualOutput += ", ";
actualOutput += jumbleWithWordDictionaryFile.MatchCount6Letters;
Assert.AreEqual(expectedOutput, actualOutput, "The CountMatchingOutput method calculated inaccurate results.");
}

[Test]
public void MajorTestCountMatchingWordsNoMatchesFound()
{
jumbleWithWordDictionaryFile.CurrentJumble = "xyzzqw";
bool didCountSucceed = jumbleWithWordDictionaryFile.CountMatchingWords();
Assert.AreEqual(true, didCountSucceed, "The CountMatchingWords method failed for the jumble 'xyzzqw'");

string expectedOutput = "0, 0, 0, 0";
string actualOutput = jumbleWithWordDictionaryFile.MatchCount3Letters.ToString();
actualOutput += ", ";
actualOutput += jumbleWithWordDictionaryFile.MatchCount4Letters.ToString();
actualOutput += ", ";
actualOutput += jumbleWithWordDictionaryFile.MatchCount5Letters.ToString();
actualOutput += ", ";
actualOutput += jumbleWithWordDictionaryFile.MatchCount6Letters;
Assert.AreEqual(expectedOutput, actualOutput, "The CountMatchingOutput method calculated inaccurate results.");
}
#endregion

Negative Tests

#region ---------- Negative Tests ----------
[Test]
public void SimpleNegativeTestCountMatchingWordsSpaceInJumble()
{
List dictionary = new List();
dictionary.Add("ace");
dictionary.Add("are");
dictionary.Add("dak");
dictionary.Add("ross");
dictionary.Add("rosy");
dictionary.Add("rynd");
dictionary.Add("rddnol"); ;
dictionary.Add("rndle");
dictionary.Add("rlead");

// this assignment should be denied leaving the CurrentJumble property pointing to an empty string
simpleJumble.CurrentJumble = "rn dal@#$@$ae";
simpleJumble.WordDictionary = dictionary;
bool didCountSucceed = simpleJumble.CountMatchingWords();
Assert.AreEqual(false, didCountSucceed, "The CountMatchingWords method failed to recognize malformed jumble 'rn dal@#$@$ae'");
}

[Test]
public void SimpleNegativeTestCountMatchingWordsSpaceInWord()
{
List dictionary = new List();
dictionary.Add("ace");
dictionary.Add("are");
dictionary.Add("dak");
dictionary.Add("ross");
dictionary.Add("rosy");
dictionary.Add("ry nd");
dictionary.Add("rddnol"); ;
dictionary.Add("rndle");
dictionary.Add("rlead");

simpleJumble.CurrentJumble = "naetcr";
simpleJumble.WordDictionary = dictionary;
bool didCountSucceed = simpleJumble.CountMatchingWords();
Assert.AreEqual(false, didCountSucceed, "The CountMatchingWords method failed to recognize malformed word 'ry nd'");
}

[Test]
public void SimpleNegativeTestCountMatchingWordsCommaEndedJumble()
{
List dictionary = new List();
dictionary.Add("ace");
dictionary.Add("are");
dictionary.Add("dak");
dictionary.Add("ronss");
dictionary.Add("roeesy");
dictionary.Add("ryndw");
dictionary.Add("rddsnol"); ;
dictionary.Add("rgdlfe");
dictionary.Add("rleqad");

// this assignment should be denied leaving the CurrentJumble property pointing to an empty string
simpleJumble.CurrentJumble = "rdle,";
simpleJumble.WordDictionary = dictionary;
bool didCountSucceed = simpleJumble.CountMatchingWords();
Assert.AreEqual(true, didCountSucceed, "The CountMatchingWords method failed to remove comma at the end of jumble 'rndle,'");
}
#endregion

Written by Arsalan A.

July 7, 2009 at 10:24 am

Posted in 1

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) &amp;&amp; (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
&gt; allSets = new List
&gt;();
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) &amp;&amp; (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.

Written by Arsalan A.

July 7, 2009 at 9:32 am

Posted in 1