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 Symbol | Narnian Word |
I | cat |
V | fish |
X | pig |
L | ant |
C | dog |
D | lion |
M | elephant |
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
Symbol | Value |
I | 1 |
V | 5 |
X | 10 |
L | 50 |
C | 100 |
D | 500 |
M | 1000 |
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
[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
- 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
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
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
{
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
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)
{
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;
}
}
}
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
.
public class ParsedStatement : ParsedBase, IParsedLine
{
public string Process()
{
var result = string.Empty;
if(IsAliasStatement)
{
ProcessAliasStatement();
}
else if(IsCommodityStatement)
{
ProcessCommodityStatement();
}
else
{
result = new ParsedError().Process();
}
return result.Trim();
}
Commodity Cache
Post processing of the Input Statement, cache the Unit price of the CommodityManager
Indexer
public class CommodityManager
{
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
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)