Roman Numerals

Roman numerals is a numeral system used in ancient Rome. However, today we still use Roman numerals mostly for number-lists, places' year, and on the watches. Here are the letters, which represent a number.

"I" is for 1
"V" is for 5
"X" is for 10
"L" is for 50
"C" is for 100
"D" is for 500
"M" is for 1000

Rule for reading Roman numerals is simple, just sum up value of each letter. However, there is an exception for reduce form. If value of the letter on the left is less than value of the letter on the right, that is reduce form. That letter must deduct from the sum instead of addition. Such as "XLIX", first X is less than L, and I is less than second X. We can write it as -10 + 50 - 1 + 10 = 49.

Rule for writing Roman numerals is also simple. Just deduct from sum by using largest value letter as possible. And you cannot using the letters for 4 times consecutively, in this case, you must write the reduce form. For example 19, Roman number should be "XVIIII" (10 + 5 + 1 + 1 + 1 + 1). But we cannot using I for 4 times consecutively, therefore "VIIII", must be written in reduce form as "IX". As a result, 19 can be written as "XIX".

Now, for coding.

public class Roman {
    int _value;

    public int Value {
        get { return _value; }
    }

    public Roman(int value) {
        if (value < 1 || value > 4999)
            throw new ArgumentOutOfRangeException("value", "value should be between 1 and 4999");
        _value = value;
    }

    public static implicit operator Roman(int x) {
        return new Roman(x);
    }
    public static Roman Parse(string roman) {
        var letter = "IVXLCDM";
        var num = new[] { 1, 5, 10, 50, 100, 500, 1000 };
        var dict = num.WithIndex(letter);

        int value, last = 0, sum = 0;
        foreach (char c in roman) {
            if (!dict.TryGetValue(c, out value))
                throw new ArgumentException("roman contains invalid characters", "roman");
            if (last < value)
                sum -= last;
            else
                sum += last;
            last = value;
        }
        sum += last;
        return new Roman(sum);
    }
    public override string ToString() {
        string numStr = _value.ToString("0000");
        string one = "MCXI";
        string[] five = { "MMM", "D", "L", "V" };
        StringBuilder sb = new StringBuilder();

        numStr.ForEach((c, i) => {
            if (c < '4')
                sb.Append(one[i], (int)(c - '0'));
            else if (c == '4')
                sb.Append(one[i]).Append(five[i]);
            else if (c < '9')
                sb.Append(five[i]).Append(one[i], (int)(c - '5'));
            else //9
                sb.Append(one[i]).Append(one[i - 1]);
        });
        return sb.ToString();
    }
}

If you notice, Parse method uses index injection from previous post, to transform 2 set of array into a dictionary.

To create a Roman number, just assign from integer.

Roman r = 19;

To read Roman number, use Parse method.

Roman r = Roman.Parse("XIX");

To write Roman number, use ToString method.

Console.WriteLine(r.ToString());
//XIX

To get value from Roman number, use Value property.

Console.WriteLine(r.Value);
//19

More example from CodeGolf. Roman to decimal number.

Roman r = Roman.Parse("MCDXL");
Console.WriteLine(r.Value);
//1440

Next article, start a new series topic "Dynamic Programming".

Extension Methods for Enumerable Part II - Index injection and index extraction

In enumerable type, index is useful to identify a member. In C# 3.0, some methods for enumerable provide index parameter such as Select and Where. But most of methods are still not provide index, such as GroupBy and OrderBy.

One of the easy way to inject index into enumerable is to use Closure. For example, if you want to order "ABCDEFG" alternately you may write.

int i = 0;
var e = "ABCDEFG".OrderBy(c => i++ % 2);
Console.WriteLine(e.ListMembers());
//A C E G B D F

To inject an index, you may declare a variable (i) and use this variable as an index in the delegate. You must also put incremental operator (++) to index variable to make index increase every iteration.

Anyway, using of Closure also has drawback. The index variable will not be cleared after enumeration. When you enumerate again index variable will be incorrect. For example:

int i = 0;
var e = "ABCDEFG".OrderBy(c => i++ % 2);
Console.WriteLine(e.ListMembers());
//A C E G B D F
Console.WriteLine(e.ListMembers());
//B D F A C E G

As you can see, the third command and the forth command are the same. But the result is not the same. Because, after run the third command, i value is equal to 7. Then when you call the forth command, the index will be started at index 7 and so on. Finally, the result will not be the same for the second time.

Anyway, this issue can be solved by make the class persistent.

int i = 0;
var e = "ABCDEFG".OrderBy(c => i++ % 2).ToArray();
Console.WriteLine(e.ListMembers());
//A C E G B D F
Console.WriteLine(e.ListMembers());
//A C E G B D F

Above example, we call ToArray after OrderBy method, and make e variable persistent. The result for e will be the same everytime.

Another solution for index injection is to create extension methods.

public static Dictionary<int, T> WithIndex<T>(this IEnumerable<T> source) {
    return source.WithIndex(0.To(int.MaxValue), EqualityComparer<int>.Default);
}
public static Dictionary<T1, T2> WithIndex<T1, T2>(this IEnumerable<T2> source, IEnumerable<T1> index) {
    return source.WithIndex(index, EqualityComparer<T1>.Default);
}
public static Dictionary<T1, T2> WithIndex<T1, T2>(this IEnumerable<T2> source, IEnumerable<T1> index, IEqualityComparer<T1> comparer) {
    Dictionary<T1, T2> dict = new Dictionary<T1, T2>(comparer);
    using (IEnumerator<T2> source_enum = source.GetEnumerator()) {
        using (IEnumerator<T1> index_enum = index.GetEnumerator()) {
            while (source_enum.MoveNext()) {
                if (!index_enum.MoveNext())
                    throw new ArgumentException("index cannot has less length than source", "index");
                dict.Add(index_enum.Current, source_enum.Current);
            }
        }
    }
    return dict;
}

You just call above method before enumeration. The result you get is a dictionary. Key is index, and Value is object. Then after enumeration, you may call Select method to remove index from the object. For example:

var e = from c in "ABCDEFG".WithIndex()
        orderby c.Key % 2
        select c.Value;
Console.WriteLine(e.ListMembers());
//A C E G B D F
Console.WriteLine(e.ListMembers());
//A C E G B D F

You can also pass any kind of index into WithIndex method. The index's length must be greater than or equal to source's length.

For example, you have source and position. And you want to sort source by position. In this case, you can assign position as an index of the source.

var e = from x in source.WithIndex(position)
        orderby x.Key
        select x.Value;

Index extraction is index from specific item in the enumerable. Here is the extension methods:

public static int IndexOf<T>(this IEnumerable<T> source, T item) {
    return source.IndexOf(item, EqualityComparer<T>.Default);
}
public static int IndexOf<T>(this IEnumerable<T> source, T item, IEqualityComparer<T> comparer) {
    IList<T> list = source as IList<T>;
    if (list != null)
        return list.IndexOf(item);

    int i = 0;
    foreach (T x in source) {
        if (comparer.Equals(x, item))
            return i;
    }
    return -1;
}

The example for IndexOf is from CodeGolf. The question is Reverse game. You will get list of numbers randomly. And you must tell how many numbers from the left to reverse. And target is to arrage the numbers.

int[] list = new[] { 8, 9, 4, 5, 1, 3, 6, 2, 7 };

Action<int> reverse = i => {
    if (i > 1) {
        Console.WriteLine("reverse: {0}", i);
        list = list.Take(i).Reverse().Concat(list.Skip(i)).ToArray();
        Console.WriteLine(list.ListMembers());
    }
};

list.Length.DownTo(1).ForEach(x => {
    if (x != list[x - 1]) {
        reverse(list.IndexOf(x) + 1);
        reverse(x);
    }
});
//8 9 4 5 1 3 6 2 7
//reverse: 2
//9 8 4 5 1 3 6 2 7
//reverse: 9
//7 2 6 3 1 5 4 8 9
//reverse: 7
//4 5 1 3 6 2 7 8 9
//reverse: 5
//6 3 1 5 4 2 7 8 9
//reverse: 6
//2 4 5 1 3 6 7 8 9
//reverse: 3
//5 4 2 1 3 6 7 8 9
//reverse: 5
//3 1 2 4 5 6 7 8 9
//reverse: 3
//2 1 3 4 5 6 7 8 9
//reverse: 2
//1 2 3 4 5 6 7 8 9

Above example, you need IndexOf to identify position of the next number you want to reverse in the list. Then you reverse that number to the left, and then you reverse again to move the number to appropriate position.

Next, we will go to Roman Numerals.