Trading With World of Narnians

• Download source code - 318.7 KB

Introduction

The Narnians stay in a hypothetical world called Narnia. The Narnians do not speak English. Also, they have got a different Numeral System. On Earth we understand Arabic Numerals and to some extent Roman Numerals. Narnian's numbering system is close to Roman Numerals. However, some kind of Language Processing is required to map the Narnian Numerals to Roman Numerals.  

The solution to Trading With World of Narnians demonstrates

• Object Oriented Design for Language Parsing and Cache Management. The below design patterns are primarily leveraged in the OO solution
• Chain of Responsibility
• Strategy
• The OO implementation also leverages Functional Programming using LINQ.
• Inversion of Control (IoC), Dependency Injection are leveraged using PRISM 4.1 / UnityContainer
• Tagging Constraints as Attributes on Enum Values 

Background 

4 Humans - Peter, Susan, Edmund and Lucy - go from Earth to Narnia and stay there for a while during the episode of The Lion, the Witch and the Wardrobe. Their stay in Narnia made them realize some Business / Trade opportunities with the Narnians.  

However, trading with the Narnians required them to convert Numbers and Units. They decided to outsource a Software Program to Me.

This piece of Software should help the Humans to trade with the Narnians. The Software should be able to Process the Statements keyed in. When a Question is keyed into the Software, the Software should respond with an Answer Statement. 

Narnian Numerals vs. Roman Numerals Mapping

A set of 7 Narnian Words Map to the 7  Roman Symbols 

Roman Numeral Symbols And Constraints 

The numbers used for Narnian transactions follows similar convention to the Roman Numerals. Roman numerals are based on seven symbols: 

Source: http://en.wikipedia.org/wiki/Roman_numerals 

Numbers are formed by combining symbols together and adding the values. So II is two ones, i.e. 2, and XIII is a ten and three ones, i.e. 13. There is no zero in this system, so 207, for example, is CCVII, using the symbols for two hundreds, a five and two ones. 1066 is MLXVI, one thousand, fifty and ten, a five and a one.

Symbols are placed from left to right in order of value, starting with the largest. However, in a few specific cases, to avoid four characters being repeated in succession (such as IIII or XXXX) these can be reduced using subtractive notation as follows:

• The numeral I can be placed before V and X to make 4 units (IV) and 9 units (IX) respectively
• X can be placed before L and C to make 40 (XL) and 90 (XC) respectively
• C can be placed before D and M to make 400 and 900 according to the same pattern

An example using the above rules would be 1904: this is composed of 1 (one thousand), 9 (nine hundreds), 0 (zero tens), and 4 (four units). To write the Roman numeral, each of the non-zero digits should be treated separately. Thus 1,000 = M, 900 = CM, and 4 = IV. Therefore, 1904 is MCMIV. This reflects typical modern usage rather than a universally accepted convention: historically Roman numerals were often written less consistently. 

A common exception to the practice of placing a smaller value before a larger in order to reduce the number of characters, is the use of IIII instead of IV for 4. 

Input to your program consists of Statements and Questions. The Program should handle exceptions. 

How to Process a Narnian Input?

Sample Statement - cat cat Brass is 10 Credits  

• cat cat converted to Roman Numerals Means II 
• II converted to Arabic Numerals Means 2
• Now a Processed Statement would look like - 2 Brass is 10 Credits 
• Interpreting further - 1 Brass is 10 / 2 = 5 Credits. ie. 1 Unit of Brass Costs 5 Credits   

Sample Question -   how many Credits is cat fish Brass ?   

• cat fish converted to Roman Numerals Means IV   
• IV converted to Arabic Numerals Means 4 
• Now a Processed Question would look like - how may Credits is 4 Brass ? 
• From the above Statement, we know 1 Unit of Brass Costs 5 Credits. Therefore, 4 Units of Brass will Cost 5 x 4 = 20 Credits  

Sample Input / Output of the Program   

Test input

• cat is I 
• fish is V 
• pig is X 
• ant is L
• cat cat Brass is 10 Credits 
• cat fish Copper is 4000 Credits
• pig pig Aluminum is 2000 Credits
• how much is pig ant cat ?
• how many Credits is cat fish Brass ?
• how many Credits is cat fish Copper ?
• how many Credits is cat fish Aluminum?
• how much would be the cost to get Aslan on to the earth ?

Test Output

• pig ant cat is 41
• cat fish Brass is 20 Credits
• cat fish Copper is 4000 Credits
• cat fish Aluminum is 400 Credits
• Exception - unable to parse

Using the code

• The solution to address the above problem is implemented in C# .NET
• The solution is built with Visual Studio 2012, .NET Framework 3.5. Solution file - .\TradeWithNarnia\TradeWithNarnia.sln
• The solution contains two projects
• TradeWithNarnia - This project implements core logic
• TradeWithNarniaTest - This project implements NUnit Tests on TradeWithNarnia

/// <summary>
/// Test Fixture to get the given input in the problem statement tested
/// </summary>
[TestFixture]
public class TestGivenInput
{
private KeyValuePair<string, string>[] inputOutputPairs = new []
  {
    new KeyValuePair<string, string>("cat is I", string.Empty), 
    new KeyValuePair<string, string>("fish is V", string.Empty),
    new KeyValuePair<string, string>("pig is X", string.Empty),
    new KeyValuePair<string, string>("ant is L", string.Empty),
    new KeyValuePair<string, string>("cat cat Brass is 10 Credits", string.Empty),
    new KeyValuePair<string, string>("cat fish Copper is 4000 Credits", string.Empty),
    new KeyValuePair<string, string>("pig pig Aluminium is 2000 Credits", string.Empty),
    new KeyValuePair<string, string>("how much is pig ant cat ?", "pig ant cat is 41"),
    new KeyValuePair<string, string>("how many Credits is cat fish Brass ?", 
        "cat fish Brass is 20 Credits"),
    new KeyValuePair<string, string>("how many Credits is cat fish Copper ?", 
        "cat fish Copper is 4000 Credits"),
    new KeyValuePair<string, string>("how many Credits is cat fish Aluminium ?", 
        "cat fish Aluminium is 400 Credits"),
    new KeyValuePair<string, string>("how much would be the cost to " + 
        "get Aslan on to the earth ?", "Exception - unable to parse"),
  };


[Test]
public void ExecuteTest1()
{
  TradeWithNarnia.Helper.UnityContainerHelper.Initialize();

  var singleLineProcessor = new SingleLineProcessor();
  foreach (var inputOutpuPair in inputOutputPairs)
  {
    string output = singleLineProcessor.Process(new SingleLineText(inputOutpuPair.Key));
    Assert.True(inputOutpuPair.Value.Equals(output), 
      "Expected output: " + inputOutpuPair.Value + " Actual output: " + output);
  }
}

• External Dependencies
• Prism 4.1
• The project leverages Prism 4.1 framework as it uses the UnityContainer for Dependency Injection.
• These dependencies can be downloaded from: http://www.microsoft.com/en-in/download/details.aspx?id=28950
• NUnit
• The test project has a dependency on NUnit framework 2.6.2.12296
• NUnit dependency can be downloaded from: http://launchpad.net/nunitv2/2.6.2/2.6.2/+download/NUnit-2.6.2.zip
• Unit Tests
• TestGivenInput - Use NUnit to run TestGivenInput Test cases. These test cases assert the given sample output with the problem statement against the actual output of the program.
• TestRomanNumberValidator - Tests the given constains for a Roman number viz. Number of repetitions, Marginally Smaller number to precede bigger number for subtraction
• TestPriceConverter - Tests Price conversion from Roman Number to Arabic Number for various inputs

Points of Interest

On the Fly Parsing with LINQ

/// <summary>
/// Default implementation of IParsedWords that implements parsing for TradeWithNarnia problem
/// </summary>
public class ParsedWordsImpl : IParsedWords
{
    private IEnumerable<string> _words = new List<string>();

    [Dependency]
    public AliasManager AliasMgr { get; set; }

    private IEnumerable<string> LeftHalfWords
    {
      get
      {
        return _words.TakeWhile(word => !WordConstants.IN_THE_MIDDLE_WORDS.Contains(word)).ToList();
      }
    }

Tag Enum Values with Constraints, Apply Constraints with Reflection

Apply the below constraint on Roman Symbol I

• I can only be Subtracted from V and X
• I can have a maximum 3 repetitions

/// <summary>
/// Enum that represents each RomanNumber with their Constraints specified as attributes
/// </summary>
public enum RomanSymbol
{
    [RomanSymbolConstraint(CanBeSubtractedFrom = new[] { V, X }, MaxRepetition = 3)]
    I = 1,

    V = 5,

    [RomanSymbolConstraint(CanBeSubtractedFrom = new [] { L, C }, MaxRepetition = 3)]
    X = 10,

    L = 50,

    [RomanSymbolConstraint(CanBeSubtractedFrom = new [] { D, M }, MaxRepetition = 3)]
    C = 100,

    D = 500,

    [RomanSymbolConstraint(MaxRepetition = 3)]
    M = 1000,
}  

Leverage an EnumHelper class to pull these attributes using Reflection

public static class EnumHelper
{
    /// <summary>
    /// Gets an attribute on an enum field value
    /// </summary>
    /// <typeparam name="T">The type of the attribute you want to retrieve</typeparam>
    /// <param name="enumVal">The enum value</param>
    /// <returns>The attribute of type T that exists on the enum value</returns>
    public static T GetAttributeOfType<T>(this Enum enumVal) where T : System.Attribute
    {
      var type = enumVal.GetType();
      var memInfo = type.GetMember(enumVal.ToString());
      var attributes = memInfo[0].GetCustomAttributes(typeof(T), false);
      if (attributes.Any())
      {
        return (T) attributes[0];
      }
      return null;
    }
}

Make sure the applied Enum Constraints are getting validated on Roman Numbers 

/// <summary>
/// Checks the validity of a given roman number
/// </summary>
public class RomanNumberValidator
{
    public static bool IsRomanNumberValid(IEnumerable<RomanSymbol> romanSymbols_)
    {
      bool isRomanNumberValid = true;
      RomanSymbol[] symbols = romanSymbols_.ToArray();

      for (int i = 0; i < symbols.Length; i++)
      {
        var attribute = symbols[i].GetAttributeOfType<RomanSymbolConstraintAttribute>();
        if (attribute != null)
        {
          // Check if the roman number can be subtracted from the next number
          if (attribute.CanBeSubtracted)
          {
            if (i < (symbols.Length - 1) && ((int)symbols[i] < (int)symbols[i + 1]))
            {
              if (attribute.CanBeSubtractedFrom.Contains(symbols[i + 1]) == false)
              {
                isRomanNumberValid = false;
              }
            }
          }

          // check if the roman number has the right number of repetitions
          if (attribute.CanRepeat)
          {
            string symbolName = Enum.GetName(symbols[i].GetType(), symbols[i]);
            string potentiallyInvalidSubstring = GetSubstring(symbolName, attribute.MaxRepetition + 1);
            if (GetRomanNumberAsString(romanSymbols_).Contains(potentiallyInvalidSubstring))
            {
              isRomanNumberValid = false;
            }
          }

        }
      }
      return isRomanNumberValid;
}

Chain of Responsibility

A StatementParser does not know to parse anything other than a statement. In case it encounters something else, it is going to delegate the Parsing responsibility to the instance of ErrorParser.

/// <summary>
/// Processes statements, populates Alias cache, Commodity cache
/// </summary>
public class ParsedStatement : ParsedBase, IParsedLine
{
public string Process()
{
  var result = string.Empty;
  if(IsAliasStatement)
  {
    ProcessAliasStatement();
  }
  else if(IsCommodityStatement)
  {
    ProcessCommodityStatement();
  }
  else
  {
    // Unable to process as a statement, Redirect to Error highlighting
    result = new ParsedError().Process();
  }

  return result.Trim();
}

Commodity Cache

Post processing of the Input Statement, cache the Unit price of the CommodityManager Indexer 

/// <summary>
/// Maintains a cache of commodities
/// </summary>
public class CommodityManager
{
  /// <summary>
  /// key : value => "brass" : Commodity("Brass", 5)
  /// </summary>
  private Dictionary<string, Commodity> _commodityCache = new Dictionary<string, Commodity>();

  public Commodity this[string commodityName_]
  {
    get
    {
      return _commodityCache.ContainsKey(commodityName_.ToLower()) ? _commodityCache[commodityName_.ToLower()] : null;
    }
    set
    {
      _commodityCache.Add(value.Name.ToLower(), value);
    }
  }
} 

Dependency Injection with UnityContainer

/// <summary>
/// Base class for processing various types of parsed lines viz. Question, Statement, Error
/// Contains dependency injected properties and utility methods
/// </summary>
public class ParsedBase
{
    [Dependency]
    public IParsedWords ParsedWords { get; set; }

    [Dependency]
    public AliasManager AliasMgr { get; set; }

    [Dependency]
    public CommodityManager CommodityMgr { get; set; }

    [Dependency]
    public PriceConverter PriceCnvtr { get; set; }

Desired Improvements

• Unit Test for each possible path of execution to get 100% code coverage
• Collection instances of type Array / Lists to be updated to IEnumerable
• Caching can be done inside ParsedWordsImpl to save some CPU cycle
• SingleLineProcessor could expose a static API for processing
• Word constants could be read from a config file, instead of an Array, Set can be used
• Alias Manager / Commodity Manager could potentially implement an interface to facilitate Unit Testing
• Logging could have been leveraged
• Corner cases for language processing eg. no space between last word and '?'
• Leverage constituency-based parse tree or Dependency-based parse tree for language processing
• Dependency injection via constructor (rather than public properties)