Rational for C#

Rational is ratio of 2 integers. It represents fractions of an integer. Most of the time if you deal with rational number, you can use real number (float) instead. But real number has an drawback. It cannot maintain proportion of 2 integers for number with repeating decimal. For example,

(1/20)² + (1/15)² - (1/12)²
= (1/400) + (1/225) - (1/144)
= (9/3600) + (16/3600) - (25/3600)
= 0

Now testing with real number:

double x = Math.Pow(1.0 / 20.0, 2.0);
double y = Math.Pow(1.0 / 15.0, 2.0);
double z = Math.Pow(1.0 / 12.0, 2.0);
Console.WriteLine(x + y - z);
//8.67361737988404E-19

Result is not zero as expected. To use rational, you can download from here. Rational class is required BigInteger in SilverLight package. You can construct rational several ways.

Rational a = new Rational(1, 20);
Rational b = (Rational)1 / 15;
Rational c = 1m / 12m;
Console.WriteLine(a.Power(2) + b.Power(2) - c.Power(2));
//0

You can construct rational using new keyword, first argument is numerator, and second argument is denominator. Second method is to cast from integer. Last method is to guess from decimal. Please noted that guessing rational from decimal may lose accuracy, such as:

Rational r = 1000001m / 600001m;
Console.WriteLine(r.ToString());
//5/3

You can see that it keeps 5/3 instead of 1000001/600001. If you need accuracy, construct rational or casting from integer are better solutions.

The Rational class always keep rational in reduced form, such as:

Rational r = (Rational)5 / 10;
Console.WriteLine(r.ToString());
//1/2

It keeps 1/2 instead of 5/10. This will make all same proportions such as 1/2, 3/6, 5/10 are all equivalent.

This Rational class supports infinity, negative zero, and not a number (NaN). This will make all arithmetic operations are equal to real number, such as:

//1/0 makes infinity
Rational inf = (Rational)1 / 0;
Console.WriteLine(inf);
//Infinity

//Invert of negative zero makes negative infinity
Rational nzero = (Rational)0 / -1;
Console.WriteLine(1 / nzero);
//-Infinity

//infinity - infinity = nan
Rational nan = inf - inf;
Console.WriteLine(nan);
//NaN

Let's test rational with an easy question from projecteuler.net.
Find numerator of the fraction immediately to left of 3/7 with denominator <= 1000000

Rational r = (Rational)3 / 7;
r -= (Rational)1 / 999999;
Console.WriteLine(r.Numerator);
//428570

Next topic is to create continued fractions from square root and generate sequence of rational.

Infinity, Negative Zero, and Not a Number

Mathematics always go beyond its own current dimension. Natural numbers was created, but it does not satisfy existence of zero and negative numbers. Integer was then created, but what happened if we scale integer into smaller numbers. Rational was then create, but it cannot represents number liked root of 2. Real numbers was then created, but some create Complex numbers to satisfy root of -1, and some create Extended real, to satisfy division of zero.

Extended real is very interesting, it doesn't comply with number system as following:

Infinity + 1 = Infinity
1 = Infinity - Infinity
1 = 0 ???

Therefore, infinity is not existed and division by zero is undefined. But extended real try to create its own rules by introducing non-number liked Infinity, Negative Infinity, Negative Zero, and Not a number.

Infinity can be created by 1/0. Some basic properties of infinity are:

1.0 / 0.0 = Inf
1.0 / Inf = 0.0
1.0 + Inf = Inf
Inf - Inf = NaN
Inf * 0.0 = NaN
Inf * -1.0 = -Inf

Infinity in extended real has its own sign. It can be positive or negative. Negative infinity can be created by -1/0. Some basic properties of negative infinity are:

-1.0 / 0.0 = -Inf
1.0 / -Inf = -0.0
1.0 / -0.0 = -Inf
1.0 + -Inf = -Inf
-Inf * -1.0 = Inf

Zero in extended real also has its own sign. It can be negative. Negative zero can be create by -0. Some basic properties of negative zero are:

-(0.0) = -0.0
-0.0 * -1.0 = 0.0
-0.0 * -0.0 = 0.0
-0.0 * 0.0 = -0.0
-0.0 + -0.0 = -0.0
-0.0 + 0.0 = 0.0
-1.0 % 1.0 = -0.0

All undefined numbers are Not a Number (NaN). All arithmatic operation with NaN result to NaN, therefore extended real has no arithmatic error. NaN can be created from:

0.0 / 0.0 = NaN
Inf - Inf = NaN
Inf * 0.0 = NaN
1.0 % 0.0 = NaN
Inf % 1.0 = NaN
Sqrt(-1.0) = NaN

Arithmatic comparisons for extended real are as follows:

Inf > 1.0
1.0 > 0.0
0.0 == -0.0
0.0 > -1.0
-1.0 > -Inf
-Inf > NaN
NaN != NaN

NaN doesn't equal to itself, to check NaN use double.Equals(x, NaN) instead. Extended real is IEEE standard and it is called "floating point". In C#, 2 types for floating point are provided, float and double. Float is single precision, its maximum precision is around 1.4E-45. Double is much precise, its maximum precision is up to around 4.94E-324.

Next post, I will introduce type with unbounded precision.

Dynamic Programming Part III - Partition Function

Partition Function is function to find distinct ways to sum natural numbers to a target number. Such as 4 can be partitioned to 5 distinct ways:

4
3+1
2+2
2+1+1
1+1+1+1

Consider above summation and find overlapping function, we can notice that we can deduct 1 to 4 from target number. If the result is 0, it is the solution. If result is greater than 0, we must do further deduction. And this is the formula of partition function:



Where m is maximum number to deduct, n is the remaining. Whenever n is 0, means it is a solutions. But if n is less than 0, there is no solution for remaining less than 0. We can write above function into following code:

Func<int, int, int> p = null;
p = (m, n) => 1.To(m).Sum(i => p(i, n - i));
p = p.When((m, n) => n == 0, (m, n) => 1);
p = p.When((m, n) => n < 0, (m, n) => 0);
p = p.Memoize();

We can find the partition function of 100 by using following code:

Console.WriteLine(p(100, 100));
//190569292

We can adapt above function to find partition function using a specific set of number. Such as changing £2 to any number of coins (1p, 2p, 5p, 10p, 20p, 50p, 1£, and 2£). Following is the formula.



Where s(i) is the value of a specific item in the set. And now m is the upper bound of the set. We can solve number of solutions of changing for £2 with following code:

int[] s = null;
Func<int, int, int> p = null;
p = (m, n) => 0.To(m).Sum(i => p(i, n - s[i]));
p = p.When((m, n) => n == 0, (m, n) => 1);
p = p.When((m, n) => n < 0, (m, n) => 0);
p = p.Memoize();

s = new[] { 1, 2, 5, 10, 20, 50, 100, 200 };
Console.WriteLine(p(s.Length - 1, 200));
//73682

Next, we can also find the first target number, partitioned by prime numbers, and has over 5000 solutions.

s = new Prime().TakeWhile(x => x <= 100).Cast<int>().ToArray();
Console.WriteLine(1.To(100).First(i => p(s.Length - 1, i) >= 5000));
//71

This post is the end of dynamic programming series. The challenging part of dynamic programming is to find overlapping substructure. Once you find the substructure, your computation of the functions will be extremely fast. Next post is about number which is real number.

Dynamic Programming Part II - Routes

This post is about to give you basic examples and how to solve dynamic programming. A classic dynamic programming example is to find number of routes over a rectangular grid.

Here is example of 2x2 grid, there are 6 routes from top-left to bottom-right (without backtracking).


(pic from projecteuler.net)

Then, how many routes for 20x20 grid? To solve this question with dynamic programming, you must first define the sub-structure. For every point on grid, there is 2 alternative routes, to move down, and to move right. Therefore, current function is a point (m,n), and sub-structure is point on the bottom (m,n-1) and point on the right (m-1,n). Number of routes for point (m,n) equal to point (m,n-1) plus point (m-1,n).

(m,n)-----(m-1,n)
  |
  |
  |
(m,n-1)

if (m,n-1) has 3 routes to destination,
and (m-1,n) also has 3 routes to destination,
then (m,n) will has 6 (3+3) routes to destination

Except point on bottom most, and on the right most, there is only one sub-structure.

(m,0)-----(m-1,0)

then (m,0) = (m-1,0)

and

(0,n)
  |
  |
  |
(0,n-1)

then (0,n) = (0,n-1)

Finally, on the bottom-right most, it is the destination. The route count for itself is equal to 1. And here is the formula:



And you can write it with C# with following code:

Func<long, long, long> func = null;
func = (m, n) => func(m - 1, n) + func(m, n - 1);
func = func.When((m, n) => n == 0, (m, n) => func(m - 1, 0));
func = func.When((m, n) => m == 0, (m, n) => func(0, n - 1));
func = func.When((m, n) => m == 0 && n == 0, (m, n) => 1);
func = func.Memoize();
Console.WriteLine(func(20, 20));
//137846528820

To make it more harder, let's say that each point has different costs, how can we find the route with minimum cost? The logic is the same, but the formula is different. For a specific point on the grid, we will choose route that is lower cost.

(m,n)-----(m-1,n)
  |
  |
  |
(m,n-1)

if total cost for point (m,n-1)=15
total cost for point (m-1,n)=20
point (m,n-1) has lower total cost,
then point (m,n)=15 + cost of point (m,n)

Here is the formula:



And this is code for C#:

int[,] cost = new int[,] {   {131, 673, 234, 103, 18},
                             {201,  96, 342, 965, 150},
                             {630, 803, 746, 422, 111},
                             {537, 699, 497, 121, 956},
                             {805, 732, 524,  37, 331}};
Func<int, int, int> func = null;
func = (m, n) => cost[m, n] + new[] { func(m - 1, n), func(m, n - 1) }.Min();
func = func.When((m, n) => n == 0, (m, n) => cost[m, n] + func(m - 1, 0));
func = func.When((m, n) => m == 0, (m, n) => cost[m, n] + func(0, n - 1));
func = func.When((m, n) => m == 0 && n == 0, (m, n) => cost[m, n]);
func = func.Memoize();
Console.WriteLine(func(4, 4));
//2427

Next article, harder example for dynamic programming.

Dynamic Programming Part I - Introduction

All combinatoric problems can be solved by Brute-force search. But if search space is very large, Brute-force search required very much time and performance to search for solutions. However, we can reduce search space by input the constraints, which is Constraint Programming. And another optimization is to find the pattern of search space, it is Dynamic Programming.

Problems which can be solved by Dynamic Programming, must contains 2 properties, which are

- Optimal Substructure
- Overlapping Subproblems

Optimal Substructure means, the sub-function must return the same solution everytime. For instance,

Start is a problem. The problem can be splitted into 3 sub-problems. Straight lines are known costs. Wavy lines are optimal costs of the sub-problems. If optimal costs is able to determine, the optimal solutions is also able to determine. The minimum cost for this problem is 25 (5 + 20). But if the optimal solutions on wavy lines cannot be determined, then there is no optimal substructure.

Overlapping Subproblems means, the main function must be splitted into sub-function, and all sub-functions should share the same function. For instance, for a Fibonacci number, it is equal to the sum of 2 previous Fibonacci numbers. We can write into function: F(n) = F(n - 1) + F(n - 2). And we must also define the end point of recursive function: F(0) = 0, F(1) = 1.



Dynamic Programming in practical makes use of
- Recursion
- Pattern Matching
- Memoization

Recursion is function that can be splitted into sub-function of itself. In C#, it doesn't support anonymous recursive function, we have to set it to null before make the recursion.

Func<long, long> fibo = null;
fibo = n => fibo(n - 1) + fibo(n - 2);

Pattern Matching is to check the input parameter, and reroute to the the appropriate function. For me, I used When method, this method can be found in delegate article, part I, and part II.

fibo = fibo.When(n => n == 1, n => 1);
fibo = fibo.When(n => n == 0, n => 0);

Memoization is technique to cache the result to speed up calculation. Because dynamic programming is optimal substructure, the sub-function can be determined. Memoization is very important to make dynamic programming processes faster. (Memoize method also can be found in delegate article, part I, and part II)

fibo = fibo.Memoize();

Now we can combine it all together.

Func<long, long> fibo = null;
fibo = n => fibo(n - 1) + fibo(n - 2);
fibo = fibo.When(n => n == 1, n => 1);
fibo = fibo.When(n => n == 0, n => 0);
fibo = fibo.Memoize();

Dynamic programming is now completed for Fibonacci function. To call function, is very simple.

Console.WriteLine(fibo(38));
//39088169

Next article, some more examples on dynamic programming.

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.

Extension Methods for Math

Math class provided by core library of .NET is very good. But most methods are for double type. Today we will create math methods for integer types which include int, long, and BigInteger.

Start with GCD (Greatest Common Divisor), which I used once in Pythagorean article.

public static int Gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}
public static long Gcd(long a, long b) {
    while (b != 0L) {
        long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

And next one goes to LCM (Least Common Multiple).

public static int Lcm(int a, int b) {
    return (b / Gcd(a, b)) * a;
}
public static long Lcm(long a, long b) {
    return (b / Gcd(a, b)) * a;
}

Usage of these methods are easy, to find GCD and LCM of number 1 to 20.

Console.WriteLine(1.To(20).Aggregate(Math2.Gcd));
//1
Console.WriteLine(1.To(20).Aggregate(Math2.Lcm));
//232792560

Next is Integer Square Root. This method uses Newton's method to solve square root.

public static int Sqrt(this int num) {
    if (num < 0)
        throw new ArgumentOutOfRangeException("num", "num cannot be negative");

    int x = num;
    int y = (x + 1) / 2;
    while (y < x) {
        x = y;
        y = (x + (num / x)) / 2;
    }
    return x;
}
public static long Sqrt(this long num) {
    if (num < 0L)
        throw new ArgumentOutOfRangeException("num", "num cannot be negative");

    long x = num;
    long y = (x + 1L) / 2L;
    while (y < x) {
        x = y;
        y = (x + (num / x)) / 2L;
    }
    return x;
}

Usage is simple, to find square root of 2,000,000,000,000,000,000

Console.WriteLine(2000000000000000000.Sqrt());
//1414213562

Next is to find the Exponentiation

public static int Power(this int num, int pow) {
    if (pow < 0)
        throw new ArgumentOutOfRangeException("pow", "pow cannot be negative");

    int result = 1;
    while (pow != 0) {
        if ((pow & 1) == 1) {
            result *= num;
            if (pow == 1)
                return result;
        }
        num *= num;
        pow >>= 1;
    }
    return result;
}
public static long Power(this long num, long pow) {
    if (pow < 0L)
        throw new ArgumentOutOfRangeException("pow", "pow cannot be negative");

    long result = 1L;
    while (pow != 0L) {
        if ((pow & 1L) == 1L) {
            result *= num;
            if (pow == 1L)
                return result;
        }
        num *= num;
        pow >>= 1;
    }
    return result;
}

Usage is as simple as square root, to find 2nd power of 1,414,213,562.

Console.WriteLine(1414213562L.Power(2));
//1999999998944727844

When you use integer square root and power to a number, if result is not the same as that number, the number is not perfect square. In the example above, 2,000,000,000,000,000,000 is not perfect square.

Last one, Modular Exponentiation, is to perform power over a modulus.

public static int ModPow(this int num, int pow, int mod) {
    if (pow < 0)
        throw new ArgumentOutOfRangeException("pow", "pow cannot be negative");

    int result = 1;
    while (pow != 0) {
        if ((pow & 1) == 1) {
            result = (result * num) % mod;
            if (pow == 1L)
                return result;
        }
        num = (num * num) % mod;
        pow >>= 1;
    }
    return result;
}
public static long ModPow(this long num, long pow, long mod) {
    if (pow < 0L)
        throw new ArgumentOutOfRangeException("pow", "pow cannot be negative");

    long result = 1L;
    while (pow != 0L) {
        if ((pow & 1L) == 1L) {
            result = (result * num) % mod;
            if (pow == 1L)
                return result;
        }
        num = (num * num) % mod;
        pow >>= 1;
    }
    return result;
}

Example of modular exponentiation, to find last 5 digits of 10th power of 1,414,213,562.

Console.WriteLine(1414213562L.ModPow(10L, 100000L));
//60224

And below is the code for BigInteger

public static BigInteger Gcd(BigInteger a, BigInteger b) {
    while (!b.IsZero()) {
        BigInteger r = a % b;
        a = b;
        b = r;
    }
    return a;
}
public static BigInteger Lcm(BigInteger a, BigInteger b) {
    return (b / Gcd(a, b)) * a;
}
static readonly BigInteger two = 2;
public static BigInteger Sqrt(this BigInteger num) {
    if (num.IsNegative())
        throw new ArgumentException("num cannot be negative", "num");
    if (num.IsZero())
        return BigInteger.Zero;

    BigInteger x = num;
    BigInteger y = (x + BigInteger.One) / two;
    while (y < x) {
        x = y;
        y = (x + (num / x)) / two;
    }
    return x;
}

There is not Power and ModPow for BigInteger, because BigInteger already contains those methods.

Next article, is to find the ways to inject index into various enumerable methods.

Extension Methods for Delegate Types Part II - Passing anonymous type to generic function

How can you create function which its parameter or return type is anonymous type? You can't assign lambda expression to implicit local variable declaration.

//Compile error
var func = () => new { x = 1, y = 2 };

The c# compiler also does not accept type inference on instantiation, such as

//Compile error
var func = new Func(() => new { x = 1, y = 2 });

To create generic function, which accepts anonymous type, we must create method. Because for method, type inference is allowed.

Here is the code.

public static Func<TResult> CreateFunction<TResult>(Func<TResult> tResult) {
    return tResult;
}
public static Func<T, TResult> CreateFunction<T, TResult>(T t, Func<T, TResult> tResult) {
    return tResult;
}
public static Func<T1, T2, TResult> CreateFunction<T1, T2, TResult>(T1 t1, T2 t2, Func<T1, T2, TResult> tResult) {
    return tResult;
}
public static Func<T1, T2, T3, TResult> CreateFunction<T1, T2, T3, TResult>(T1 t1, T2 t2, T3 t3, Func<T1, T2, T3, TResult> tResult) {
    return tResult;
}
public static Func<T1, T2, T3, T4, TResult> CreateFunction<T1, T2, T3, T4, TResult>(T1 t1, T2 t2, T3 t3, T4 t4, Func<T1, T2, T3, T4, TResult> tResult) {
    return tResult;
}

To create the method just pass lambda expression to the argument.

var func = Function2.CreateFunction(() => new { x = 1, y = 2 });

You can also create function which its arguments and return type are anonymous type

var func = Function2.CreateFunction(
    new { Name = default(string), Age = default(int) },
    default(decimal),
    (person, salary) =>
        new {
            Name = person.Name,
            Age = person.Age,
            Salary = salary
        });
var p = func(new { Name = "Lisa", Age = 20 }, 1000000);
//p = { Name = Lisa, Age = 20, Salary = 1000000 }

Just pass the empty class to specify type of arguments. Above code is to create function which accept an anonymous type (Name: string, Age: int) and a decimal, the function returns another anonymous type (Name: string, Age: int, Salary: decimal).

As a bonus here are some more extension methods.

public static Func<T2, T3, TResult> Partial<T1, T2, T3, TResult>(this Func<T1, T2, T3, TResult> func, T1 arg1) {
    return (arg2, arg3) => func(arg1, arg2, arg3);
}
public static Func<T2, T3, T4, TResult> Partial<T1, T2, T3, T4, TResult>(this Func<T1, T2, T3, T4, TResult> func, T1 arg1) {
    return (arg2, arg3, arg4) => func(arg1, arg2, arg3, arg4);
}

public static Func<T1, T2, T3, TResult> Memoize<T1, T2, T3, TResult>(this Func<T1, T2, T3, TResult> func) {
    var dict = new Dictionary<T1, Func<T2, T3, TResult>>();
    return (arg1, arg2, arg3) => {
        Func<T2, T3, TResult> value;
        if (!dict.TryGetValue(arg1, out value)) {
            value = func.Partial(arg1).Memoize();
            dict.Add(arg1, value);
        }
        return value(arg2, arg3);
    };
}
public static Func<T1, T2, T3, T4, TResult> Memoize<T1, T2, T3, T4, TResult>(this Func<T1, T2, T3, T4, TResult> func) {
    var dict = new Dictionary<T1, Func<T2, T3, T4, TResult>>();
    return (arg1, arg2, arg3, arg4) => {
        Func<T2, T3, T4, TResult> value;
        if (!dict.TryGetValue(arg1, out value)) {
            value = func.Partial(arg1).Memoize();
            dict.Add(arg1, value);
        }
        return value(arg2, arg3, arg4);
    };
}

public static Func<T1, T2, T3, TResult> When<T1, T2, T3, TResult>(this Func<T1, T2, T3, TResult> func, Func<T1, T2, T3, bool> predicate, Func<T1, T2, T3, TResult> alternative) {
    return (arg1, arg2, arg3) => predicate(arg1, arg2, arg3) ? alternative(arg1, arg2, arg3) : func(arg1, arg2, arg3);
}
public static Func<T1, T2, T3, T4, TResult> When<T1, T2, T3, T4, TResult>(this Func<T1, T2, T3, T4, TResult> func, Func<T1, T2, T3, T4, bool> predicate, Func<T1, T2, T3, T4, TResult> alternative) {
    return (arg1, arg2, arg3, arg4) => predicate(arg1, arg2, arg3, arg4) ? alternative(arg1, arg2, arg3, arg4) : func(arg1, arg2, arg3, arg4);
}

These are Parial, Memoize, and When functions, which are the same as previous post. You can find detail of functions in previous post. The only difference of these functions and functions in previous post is, these functions accept 3 and 4 arguments.

Next post, extension methods for math.

Constraint Programming Part VI - River Crossing

River crossing is a puzzle, which its objective is to bring all people (father, mother, 2 sons, 2 daughters, police, and thief) crossing a river. With the constriants that:

- Not more than 2 persons can raft at a time
- Father cannot stay with daughter without mother
- Mother cannot stay with son without father
- Thief cannot stay with any body without police
- Only father, mother, and police can raft

You can play online game here.

To solve this puzzle with arranger class, first, let's declare the members.

[Flags]
public enum Cross {
    Thief = 1,
    Police = 2,
    Father = 4,
    Mother = 8,
    Son = 16,
    Son2 = 32,
    Daughter = 64,
    Daughter2 = 128,
}

Cross type is flag because, we want to consolidate any combinations of persons into a variable. We can declare allPeople represents all persons in Cross type.

var allPeople = Cross.Thief | Cross.Police | Cross.Father | Cross.Mother | Cross.Son | Cross.Son2 | Cross.Daughter | Cross.Daughter2;

And below function is to switch the presence of persons in combination.

Func<Cross, Cross> opp = x => x ^ allPeople;

To solve this puzzle, we might divid problem into 2 steps, combination of persons of each crossing, and combination of crossing which can solve the puzzle.

We can declare custom construction of Arranger class by using command e.Arrange(arg1, arg2, arg3). Where e is enumerable. Arg1 is local variable, if you need more than 1 variable, you can combine variables into an anonymous type new {var1, var2}. Arg2 is assignment of new local variable when a new member is added. Arg3 is condition to complete the solution.

To create Arranger class, represents combination of persons of each crossing:

var crossing = Enumerable2.Enum<Cross>().Arrange(

    //Seed - number of people, and people
    new { Length = 0, Value = (Cross)0 },

    //Func - add number of people, add people
    (current, item, i) => new { Length = current.Length + 1, Value = current.Value | item },

    //Yield - must contains police, father, or mother
    current => (current.Value & (Cross.Police | Cross.Father | Cross.Mother)) > 0
);

This is custom construction of Arranger class. Arg1 (local variable) is anonymous type of length (number of person) and value (combination of persons). Arg2 (assignment of local variable), current is variable before adding new member, item is new member, and i is index of new member. When new member is added, length is increased by 1, and value is included new member. Arg3, solution will be completed when value contains father, or mother, or police.

The Arranger class is not finished yet. We must add constraints to the class.

//no police-police, and police-thief is the same as thief-police
crossing.ArrangementModel = ArrangementModel.Combination;

//Answer can be 1 or 2 people on boat
crossing.ContinueOnYielded = true;

//Stop arranging when there are more than 2 people
crossing.AppendBreak(current => current.Length > 2);

//Thief must be with police
crossing.AppendConstraint(current => current.Value == Cross.Thief, current => item => item == Cross.Police);

//Father cannot be with daughter
crossing.AppendConstraint(current => current.Value == Cross.Father, current => item => item != Cross.Daughter && item != Cross.Daughter2);

//Mother cannot be with son
crossing.AppendConstraint(current => current.Value == Cross.Mother, current => item => item != Cross.Son && item != Cross.Son2);

This arrangement model is combination because, we don't care the position of persons in raft, "police-thief" is considered the same as "thief-police". And we cannot repeat a person in raft, such as "police-police" is impossible.

ContinueOnYield is the command to search more members when found a solution. Such as solutions to cross can be either "police", or "police-thief".

AppendBreak is command to stop searching. Above, we stop searching when number of members to cross is more than 2.

You can list all possible crossing combination.

crossing.SelectResults(c => c.Value).ForEach(c => Console.WriteLine(c));
//Thief, Police
//Police
//Police, Father
//Police, Mother
//Police, Son
//Police, Son2
//Police, Daughter
//Police, Daughter2
//Father
//Father, Mother
//Father, Son
//Father, Son2
//Mother
//Mother, Daughter
//Mother, Daughter2

If you enumerate Arranger instant directly, you will get enumeration of all possible combinations. But if you enumerate from SelectResults, you will get enumeration of the local variable of the possible combinations.

Now in step 2, we have to find combination of crossing.

var solutions = crossing.SelectResults(c => c.Value).Arrange(

    //Seed - list of people on target
    new Cross[] { 0 },

    //Func - add/subtract crossing people to/from target
    (list, item, i) => list.Append(list.Last() ^ item),

    //Yield - all people on target
    list => list.Last() == allPeople
);

In custom construction of Arranger class, arg1 (local variable) is the list of people on target land of each crossing. Arg2 (assignment) is to switch people on target land with the people who is crossing. Arg3 (solution) is people on target land must include all people.

Next is to append the break case.

//Thief cannot be with others without police
solutions.AppendBreak(list =>
    ((list.Last() & (Cross.Thief | Cross.Police)) == Cross.Thief) &&
    (list.Last() != Cross.Thief)
);
solutions.AppendBreak(list =>
    ((list.Last() & (Cross.Thief | Cross.Police)) == Cross.Police) &&
    (opp(list.Last()) != Cross.Thief)
);

//Son cannot be with mother without father
solutions.AppendBreak(list =>
    ((list.Last() & (Cross.Father | Cross.Mother)) == Cross.Mother) &&
    ((list.Last() & (Cross.Son | Cross.Son2)) > 0)
);
solutions.AppendBreak(list =>
    ((list.Last() & (Cross.Father | Cross.Mother)) == Cross.Father) &&
    ((opp(list.Last()) & (Cross.Son | Cross.Son2)) > 0)
);

//Daughter cannot be with father without mother
solutions.AppendBreak(list =>
    ((list.Last() & (Cross.Father | Cross.Mother)) == Cross.Father) &&
    ((list.Last() & (Cross.Daughter | Cross.Daughter2)) > 0)
);
solutions.AppendBreak(list =>
    ((list.Last() & (Cross.Father | Cross.Mother)) == Cross.Mother) &&
    ((opp(list.Last()) & (Cross.Daughter | Cross.Daughter2)) > 0)
);

We don't care who is crossing. But if the crossing makes conflict in constraints, we will stop searching. Above, we stop searching if thief be with any persons without police, father be with daughter without mother, and mother be with son without father.

Now add more constraints.

//Cannot cross back
solutions.AppendConstraint(list => list.Length % 2 == 0, list => item => !list.Any((x, i) => (i % 2 == 0) && (x == (list.Last() ^ item))));
solutions.AppendConstraint(list => list.Length % 2 == 1, list => item => !list.Any((x, i) => (i % 2 == 1) && (x == (list.Last() ^ item))));

//Must have people to cross
solutions.AppendConstraint(list => list.Length % 2 == 0, list => item => (list.Last() & item) == item);
solutions.AppendConstraint(list => list.Length % 2 == 1, list => item => (~list.Last() & item) == item);

We now add 2 constraints. First constraint is to prevent cycle crossing by checking if the crossing create duplicate combination of people on target land. Second constraint is to limit people who are crossing must be available on the side which the raft is on.

All constraints are assigned. Then we output the result.

solutions.SelectResults().First().ForEach(x => {
    Console.WriteLine(opp(x));
    Console.WriteLine(x);
    Console.WriteLine("=============================================================");
});
//Thief, Police, Father, Mother, Son, Son2, Daughter, Daughter2
//0
//=============================================================
//Father, Mother, Son, Son2, Daughter, Daughter2
//Thief, Police
//=============================================================
//Police, Father, Mother, Son, Son2, Daughter, Daughter2
//Thief
//=============================================================
//Father, Mother, Son2, Daughter, Daughter2
//Thief, Police, Son
//=============================================================
//Thief, Police, Father, Mother, Son2, Daughter, Daughter2
//Son
//=============================================================
//Thief, Police, Mother, Daughter, Daughter2
//Father, Son, Son2
//=============================================================
//Thief, Police, Father, Mother, Daughter, Daughter2
//Son, Son2
//=============================================================
//Thief, Police, Daughter, Daughter2
//Father, Mother, Son, Son2
//=============================================================
//Thief, Police, Mother, Daughter, Daughter2
//Father, Son, Son2
//=============================================================
//Mother, Daughter, Daughter2
//Thief, Police, Father, Son, Son2
//=============================================================
//Father, Mother, Daughter, Daughter2
//Thief, Police, Son, Son2
//=============================================================
//Daughter, Daughter2
//Thief, Police, Father, Mother, Son, Son2
//=============================================================
//Mother, Daughter, Daughter2
//Thief, Police, Father, Son, Son2
//=============================================================
//Daughter2
//Thief, Police, Father, Mother, Son, Son2, Daughter
//=============================================================
//Thief, Police, Daughter2
//Father, Mother, Son, Son2, Daughter
//=============================================================
//Thief
//Police, Father, Mother, Son, Son2, Daughter, Daughter2
//=============================================================
//Thief, Police
//Father, Mother, Son, Son2, Daughter, Daughter2
//=============================================================
//0
//Thief, Police, Father, Mother, Son, Son2, Daughter, Daughter2
//=============================================================

Next post, we will find more extension for delegate types.

Constraint Programming Part V - Einstein's Puzzle

There are 5 houses, which each house is different colors, different nationalities, different pets, different drinks, and different cigarettes.

And here are the constraints

• The British lives in the red house.
• The Swedish keeps dogs as pets.
• The Danish drinks tea.
• The green house is on the left of the white house.
• The green homeowner drinks coffee.
• The person who smokes Pall Mall rears birds.
• The owner of the yellow house smokes Dunhill.
• The man living in the center house drinks milk.
• The Norwegian lives in the first house.
• The man who smokes Blend lives next to the one who keeps cats.
• The man who keeps the horse lives next to the man who smokes Dunhill.
• The owner who smokes Bluemaster drinks beer.
• The German smokes prince.
• The Norwegian lives next to the blue house.
• The man who smokes Blend has a neighbor who drinks water.

Question is who own the fish?

You can try to solve yourself. Only 2% of people can solve this puzzle.

For solving by constraint programming, first, is to create the types.

public enum Nationality {
    British,
    Swedish,
    Danish,
    Norwegian,
    German,
}
public enum HouseColor {
    Red,
    Green,
    White,
    Yellow,
    Blue,
}
public enum Smoke {
    PallMall,
    DunHill,
    Blend,
    BlueMaster,
    Prince,
}
public enum Drink {
    Tea,
    Coffee,
    Milk,
    Beer,
    Water,
}
public enum Pet {
    Dog,
    Bird,
    Cat,
    Horse,
    Fish,
}

Then we split questions into 2 groups. First group is questions about properties of a single house. Second group is questions about properties between houses.

Here is the first group of questions.

- The British lives in the red house.
- The Swedish keeps dogs as pets.
- The Danish drinks tea.
- The green homeowner drinks coffee.
- The person who smokes Pall Mall rears birds.
- The owner of the yellow house smokes Dunhill.
- The owner who smokes Bluemaster drinks beer.
- The German smokes prince.

You can solve above properties by using linq.

var men = from n in Enumerable2.Enum<Nationality>()
          from c in Enumerable2.Enum<HouseColor>()
          where (n == Nationality.British) == (c == HouseColor.Red)
          from s in Enumerable2.Enum<Smoke>()
          where (n == Nationality.German) == (s == Smoke.Prince)
          where (c == HouseColor.Yellow) == (s == Smoke.DunHill)
          from d in Enumerable2.Enum<Drink>()
          where (n == Nationality.Danish) == (d == Drink.Tea)
          where (c == HouseColor.Green) == (d == Drink.Coffee)
          where (s == Smoke.BlueMaster) == (d == Drink.Beer)
          from p in Enumerable2.Enum<Pet>()
          where (n == Nationality.Swedish) == (p == Pet.Dog)
          where (s == Smoke.PallMall) == (p == Pet.Bird)
          select new {
              Nationality = n,
              HouseColor = c,
              Smoke = s,
              Drink = d,
              Pet = p
          };

By using above expression 5^5 combinations of properties are reduced to only 78 combinations of properties. You can get Count by

Console.WriteLine(men.Count());
//78

And for remaining constraints can be solved by Arranger class.

//Generate solution
var solutions = men.Arrange(5);

//New guy must not has same properties as persons in sequence
solutions.AppendConstraint(seq => seq.Any(),
    seq => man => seq.All(x =>
        x.Nationality != man.Nationality &&
        x.HouseColor != man.HouseColor &&
        x.Smoke != man.Smoke &&
        x.Drink != man.Drink &&
        x.Pet != man.Pet
    )
);

//Norwegian lives in the first house.
solutions.AppendConstraint(seq => seq.Length == 0,
    seq => man => man.Nationality == Nationality.Norwegian
);

//Guy who drinks milk lives in the third house
solutions.AppendConstraint(seq => seq.Length <= 2,
    seq => man => (seq.Length == 2) == (man.Drink == Drink.Milk)
);

//White house is next to green house
solutions.AppendConstraint(seq => seq.Any(),
    seq => man => (seq.Last().HouseColor == HouseColor.Green) == (man.HouseColor == HouseColor.White)
);

//Guy who pets cat is neighbor with guy who smokes Blend
solutions.AppendConstraint(seq => seq.Count(x => x.Pet == Pet.Cat || x.Smoke == Smoke.Blend) == 1,
    seq => man => (man.Pet == Pet.Cat) || (man.Smoke == Smoke.Blend)
);

//Guy who pets horse is neighbor with guy who smokes DunHill
solutions.AppendConstraint(seq => seq.Count(x => x.Pet == Pet.Horse || x.Smoke == Smoke.DunHill) == 1,
    seq => man => (man.Pet == Pet.Horse) || (man.Smoke == Smoke.DunHill)
);

//Norwegian is neighbor with guy lives in blue house
solutions.AppendConstraint(seq => seq.Count(x => x.Nationality == Nationality.Norwegian || x.HouseColor == HouseColor.Blue) == 1,
    seq => man => (man.Nationality == Nationality.Norwegian) || (man.HouseColor == HouseColor.Blue)
);

//Guy who drinks water is neighbor with guy who smokes Blend
solutions.AppendConstraint(seq => seq.Count(x => x.Drink == Drink.Water || x.Smoke == Smoke.Blend) == 1,
    seq => man => (man.Drink == Drink.Water) || (man.Smoke == Smoke.Blend)
);

And this is the answer.

solutions.First().ForEach(Console.WriteLine);
//{ Nationality = Norwegian, HouseColor = Yellow, Smoke = DunHill, Drink = Water, Pet = Cat }
//{ Nationality = Danish, HouseColor = Blue, Smoke = Blend, Drink = Tea, Pet = Horse }
//{ Nationality = British, HouseColor = Red, Smoke = PallMall, Drink = Milk, Pet = Bird }
//{ Nationality = German, HouseColor = Green, Smoke = Prince, Drink = Coffee, Pet = Fish }
//{ Nationality = Swedish, HouseColor = White, Smoke = BlueMaster, Drink = Beer, Pet = Dog }

Next is last part of constraint programming. We will learn to use Arranger class to solve questions with unknown length of solution. The question is river crossing.