C H a o W

Rational for C#

2008-07-26T18:00:00.005+07:00

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

2008-07-18T22:37:00.006+07:00

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

2008-07-12T01:07:00.002+07:00

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

2008-06-24T23:15:00.005+07:00

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

2008-06-14T10:18:00.003+07:00

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

2008-05-28T21:23:00.004+07:00

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

2008-05-15T22:03:00.003+07:00

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

2008-04-24T09:21:00.004+07:00

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

2008-04-05T16:31:00.003+07:00

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

2008-03-27T11:21:00.004+07:00

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

2008-03-20T13:28:00.003+07:00

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.

Constraint Programming Part IV - LINQ

2008-03-06T15:44:00.003+07:00

LINQ is a set of operators to query enumerable data. To query even numbers from set of 1 to 10, you may write:

var even = from x in 1.To(10)
           where x % 2 == 0
           select x;
//even = {2, 4, 6, 8, 10}

With using of LINQ, you can also do constraint programming. You can use "from" operator to join next member. You can append constraint by using "where" operator. And you can declare new variables by using "let" operator.

As an example, if you want to solve SEND + MORE = MONEY. Each letter represents a digit and there is no duplicated number among the letters. To solve this question, you may write:

var solutions = from d in 0.To(9)
                from e in 0.To(9).Except(new[] { d })
                from y in 0.To(9).Except(new[] { d, e })
                where (d + e) % 10 == y

                from n in 0.To(9).Except(new[] { d, e, y })
                from r in 0.To(9).Except(new[] { d, e, y, n })
                let nd = n * 10 + d
                let re = r * 10 + e
                let ey = e * 10 + y
                where (nd + re) % 100 == ey

                from o in 0.To(9).Except(new[] { d, e, y, n, r })
                let end = e * 100 + nd
                let ore = o * 100 + re
                let ney = n * 100 + ey
                where (end + ore) % 1000 == ney

                from s in 1.To(9).Except(new[] { d, e, y, n, r, o })
                from m in 1.To(9).Except(new[] { d, e, y, n, r, o, s })
                where s * 1000 + end + m * 1000 + ore == m * 10000 + o * 1000 + ney
               select new { s, e, n, d, m, o, r, y };
solutions.ForEach(Console.WriteLine);
//{ s = 9, e = 5, n = 6, d = 7, m = 1, o = 0, r = 8, y = 2 }

The code above solves from last digit to the first digit. To translate the code, first block is to process last digit. D, E, and Y is a number in 0 to 9. Except method makes all letters are not duplicated. And there is a contraint that, D + E last digit must be Y. Upto this point, all solutions that D + E, last digit is not Y, will be filtered out.

Second block is to process last 2 digits, N and R is a number in 0 to 9 with no duplication. And now 3 variables are declared ND, RE, and EY. ND represents 2 digit number N and D, and the same for RE and EY. And there is a constraint ND + RE, last 2 digits must be EY.

Third block, is the same as second block, but is to precess last 3 digit. O is a number in 0 to 9 with no duplication. END + ORE, last 3 digits must be NEY.

Fourth block is to find the solution. S and M is a number in 1 to 9, first digit cannot be 0. And SEND + MORE must be equal to MONEY. Then select the result.

Now compare LINQ code with using arranger class.

Func<int, int, int, int, int> mix = (a, b, c, d) => a * 1000 + b * 100 + c * 10 + d;
int D = 0, E = 1, Y = 2, N = 3, R = 4, O = 5, S = 6, M = 7;
var sol = 0.To(9).Arrange(8);
sol.ArrangementModel = ArrangementModel.Permutation;
sol.AppendConstraint(set => set.Length == Y, set => y => (set[D] + set[E]) % 10 == y);

sol.AppendConstraint(set => set.Length == R, set => r => (mix(0, 0, set[N], set[D]) + mix(0, 0, r, set[E])) % 100 == mix(0, 0, set[E], set[Y]));
sol.AppendConstraint(set => set.Length == O, set => o => (mix(0, set[E], set[N], set[D]) + mix(0, o, set[R], set[E])) % 1000 == mix(0, set[N], set[E], set[Y]));

sol.AppendConstraint(set => set.Length == S, set => s => s != 0);
sol.AppendConstraint(set => set.Length == M, set => m => m != 0);
sol.AppendConstraint(set => set.Length == M, set => m => mix(set[S], set[E], set[N], set[D]) + mix(m, set[O], set[R], set[E]) == m * 10000 + mix(set[O], set[N], set[E], set[Y]));

sol.SelectResults(set => new { s = set[S], e = set[E], n = set[N], d = set[D], m = set[M], o = set[O], r = set[R], y = set[Y] })
    .ForEach(Console.WriteLine);
//{ s = 9, e = 5, n = 6, d = 7, m = 1, o = 0, r = 8, y = 2 }

The code is much more confusing. To translate code above, mix function is function to join digits together. Arragement model is permutation, because each letter cannot be duplicated. First constraint, processed when get Y, D + E, last digit is Y.

Second constraint, processed when get R, ND + RE, last 2 digits must be EY. Third constraint, processed when get O, END + ORE, last 3 digits must be NEY.

Fouth and fifth constraint, processed when get S and M, S and M must not equal to 0. Last constraint, processed when get the last member M. SEND + MORE must be equal to MONEY.

To solve a constraint satisfaction problem, sometimes, when each constraint is applied to only one member, solving the problem using LINQ is better. But if constraints are applied to all members like 8 queens or sudoku, using Arranger class is better.

Next, we will solve problem with using LINQ and arranger in combination. The problem is Einstein's puzzle.

Constraint Programming Part III - Sudoku

2008-02-29T16:37:00.003+07:00

Sudoku is a puzzle with the objective to fill number 1 to 9 into 9x9 table, with the constraints that, each row, each column, and each 3x3 block, cannot contain duplicated members.

(image from wikipedia)

Source for Sudoku class you can download from here. The source of Sudoku table is array of integer, named "table".

int[] table

The size of array is 81, index 0-8 represents each cell in the first row, 9-17 for the second row, and so on. Following functions are to convert index to row, column, and grid number.

static int getRow(int x) {
    return x / 9;
}
static int getCol(int x) {
    return x % 9;
}
static int getGrid(int x) {
    return (getRow(x) / 3) * 3 + (getCol(x) / 3);
}

And this function is to test whether 2 input arguments are in the same row, or column or grid.

static bool Conflict(int x, int y) {
    return (getRow(x) == getRow(y)) ||
           (getCol(x) == getCol(y)) ||
           (getGrid(x) == getGrid(y));
}

Before start constraint programming, extract the known positions, and known values from Sudoku table.

int[] position = 0.To(80).OrderByDescending(x => table[x] > 0).ToArray();
int[] valued = table.Where(x => x > 0).ToArray();

Position is array of index of known values. All known value indexes will move to the front. This will make arranger class processes known values before unknown value. And now start constraint programming.

var solutions = 1.To(9).Arrange(81);

This is instantiation of arrager class to arrange 1-9 for the size of 81. And next append the constraint.

solutions.AppendConstraint(set => set.Length < valued.Length,
    set => cell => cell == valued[set.Length]
);

This AppendConstraint command is different from AppendConstraint command in previous post. This AppendConstraint command takes 2 arguments. First argument is argument to condition when the constraint should be applied. Second argument is constraint body. Above command can be translated that, when number of members in set less than number of known value, new member value must equal to known value. And next is constraint for Sudoku.

solutions.AppendConstraint(set => set.Length >= valued.Length,
    set => cell => !set.Any((x, i) => x == cell && Conflict(position[i], position[set.Length]))
);

Above command can be translated that, when number of members greater than or equal to number of known values, new member cannot make any both duplicated in value and conflict in position.

Now the command is completed. Next is to rearrange index into normal position.

var solution = solutions.FirstOrDefault();
if (solution == null)
    return null;
int idx = 0;
return new Sudoku(solution.OrderBy(x => position[idx++]).ToArray());

Test the class.

int[] table = { 5, 3, 0, 0, 7, 0, 0, 0, 0,
                6, 0, 0, 1, 9, 5, 0, 0, 0,
                0, 9, 8, 0, 0, 0, 0, 6, 0,
                8, 0, 0, 0, 6, 0, 0, 0, 3,
                4, 0, 0, 8, 0, 3, 0, 0, 1,
                7, 0, 0, 0, 2, 0, 0, 0, 6,
                0, 6, 0, 0, 0, 0, 2, 8, 0,
                0, 0, 0, 4, 1, 9, 0, 0, 5,
                0, 0, 0, 0, 8, 0, 0, 7, 9};
Console.WriteLine(new Sudoku(table).ToSolvedSudoku());

//5, 3, 4, 6, 7, 8, 9, 1, 2
//6, 7, 2, 1, 9, 5, 3, 4, 8
//1, 9, 8, 3, 4, 2, 5, 6, 7
//8, 5, 9, 7, 6, 1, 4, 2, 3
//4, 2, 6, 8, 5, 3, 7, 9, 1
//7, 1, 3, 9, 2, 4, 8, 5, 6
//9, 6, 1, 5, 3, 7, 2, 8, 4
//2, 8, 7, 4, 1, 9, 6, 3, 5
//3, 4, 5, 2, 8, 6, 1, 7, 9

The Sudoku is now solve! Next we will do constraint programming using only LinQ.

Constraint Programming Part II - 8 Queens Puzzle

2008-02-20T14:20:00.009+07:00

To download class used in this article, download Arranger class. Please note that, Arranger class is also use code in Extension methods for delegate types article.

After put the classes into your project, create more extension methods.

public static Arranger<T, T[]> Arrange<T>(this IEnumerable<T> source, int length) {
    return new Arranger<T, T[]>(source, new T[0],
        (current, item, i) => current.Append(item),
        current => current.Length == length);
}
public static Arranger<T1, T2> Arrange<T1, T2>(this IEnumerable<T1> source, T2 seed, Func<T2, T1, int, T2> func, Func<T2, bool> yield) {
    return new Arranger<T1, T2>(source, seed, func, yield);
}

Basic use of this class is easy, you can write just one line of code.

"ABC".Arrange(2).ForEach(x => Console.WriteLine(x.ListMembers()));
//A A
//A B
//A C
//B A
//B B
//B C
//C A
//C B
//C C

As result, the class generates all possible solutions to arrange A, B and C with length of 2. We can call this arrangement as PermutationWithRepetition. This model is suited with problems that each member's position is matter and each member can be duplicated to each other. Example of this model is English word. The word "Hello", letter H - e - l - l - o were chosen. Position is matter because if we change to "Helol", the word is changed to be meaningless. PermutationWithRepetition is the default model.

Now try next model, Permutation. We can set model from the property ArrangementModel.

var solutions = "ABC".Arrange(2);
solutions.ArrangementModel = ArrangementModel.Permutation;
solutions.ForEach(x => Console.WriteLine(x.ListMembers()));
//A B
//A C
//B A
//B C
//C A
//C B

You can see that duplicated members are eliminated. Permutation is suited with problems that position is matter and each member cannot appear twice. Example is playing jigsaw puzzle. Position is important to build every piece of jigsaw to be a picture. But you cannot use a piece of jigsaw twice.

Next model CombinationWithRepetition

var solutions = "ABC".Arrange(2);
solutions.ArrangementModel = ArrangementModel.CombinationWithRepetition;
solutions.ForEach(x => Console.WriteLine(x.ListMembers()));
//A A
//A B
//A C
//B B
//B C
//C C

When compare with PermutationWithRepetition, CombinationWithRepetition show only distinct result. This model is suited with problems that position is not matter, and each member can be duplicated. Example is changing for money. You can change 50 cents, 25 cents and 25 cents for 1 dollars. Position is not matter {50c, 25c, 25c} is equal to {25c, 25c, 50c}.

Last model, Combination

var solutions = "ABC".Arrange(2);
solutions.ArrangementModel = ArrangementModel.Combination;
solutions.ForEach(x => Console.WriteLine(x.ListMembers()));
//A B
//A C
//B C

When compare with CombinationWithRepetition, duplicated members is eliminated. This model is suited with problems that position is not matter, and each member cannot appear twice. Example is playing cards. You may get card Ace of clubs and Jack clubs. Position is not matter, {A club, J club} is equal to {J club, A club}. And you cannot have the same card in a hand.

Beside models, you can append constraint to the arranger.

var solutions = "ABC".Arrange(2);
solutions.AppendConstraint(set => c => c != 'B');
solutions.ForEach(x => Console.WriteLine(x.ListMembers()));
//A A
//A C
//C A
//C C

AppendConstraint limits the options while arranger chooses each member. You may notice that the function pass into AppendConstraint has 2 lambda operator (=>). It is partial function application. "Set" argument is set of members that arranger has already chosen, "c" argument is member to be chosen. Example above, the solution has a constraint that member to be chosen cannot be B. Therefore, there is no B in the results.

With ArrangementModel and AppendConstraint, now we can construct 8 queens puzzle solutions.

var sol = 0.To(7).Arrange(8);
sol.ArrangementModel = ArrangementModel.Permutation;
sol.AppendConstraint(set => q =>
    set.All((x, i) => (set.Length - i != Math.Abs(x - q)))
);

0.To(7) is input source represents column index 0 (A) to column index 7 (H) to put a queen. Arrange(8) is to create solutions of 8 queens. ArrangementModel.Permutation means each queens cannot be in the same column index. And AppendConstraint limits that the new queen cannot put diagonal to queens that already in the set.

With just 3 statements, code is finished. Now output the results.

Console.WriteLine(" A B C D E F G H");
sol.First().ForEach((q, i) =>
    Console.WriteLine("{0} " + "_ ".Repeat(q) + "Q " + "_ ".Repeat(7 - q), i + 1)
);
Console.WriteLine();
Console.WriteLine("Total solutions: {0}", sol.Count());
// A B C D E F G H
//1 Q _ _ _ _ _ _ _
//2 _ _ _ _ Q _ _ _
//3 _ _ _ _ _ _ _ Q
//4 _ _ _ _ _ Q _ _
//5 _ _ Q _ _ _ _ _
//6 _ _ _ _ _ _ Q _
//7 _ Q _ _ _ _ _ _
//8 _ _ _ Q _ _ _ _
//
//Total solutions: 92

Next post, solve harder problem which is Sudoku.

Constraint Programming Part I - Introduction

2008-02-05T20:43:00.000+07:00

Constraint programming is programming for searching the solutions by specifying the constraints of a problem, and then generating the satisfied solutions. Constraint programming is unlike Brute-force search, which Brute-force generates all possible solutions and then tests all solutions for the answer. Constraint programming can reduce a huge time to search by discarding large set of unsatisfied solutions.

A solution is a combination set of finite domains. And a satisfied solution is the solution that satisfies all constraints. For instance, in Sudoku, a solution is a set of 1 to 9 with size of 9 rows and 9 columns. Satisfied solutions are values of all cells in each column, each row, and each 3 x 3 grid must be unique.

Constraint programming can solve solutions by "guess-and-check", this can be done by technics called backtracking and local consistency.

BackTracking is recursive algorithm to guess a value, and check if the value is satisfied the constraints. If the value is satisfied, it will recurse and guess a value for next item. The recursion will be done until solution is valid. If no solution is valid, it will rollback and guess next value, and continue searching for valid solutions again.

Local consistency is algorithm to cut off number of items in a domain. This will reduce time and space to search. Moreover, local consistency is also checker for satisfied solutions.

For instance, for 4-queens problem, you have to place 4 queens on 4 x 4 board, with the constraint that all 4 queens must not eat each other. In this problem, there are 4 variables, which are queens for row 1, 2, 3, 4. And there are 4 items in a finite domain, which are column A, B, C, D. And there are 2 constraints, all queens cannot be in the same column, and all queens cannot place diagonally to previous queens.

To start, constraint programming will pick value for the first queen, which is column A.

A B C D
1 Q . . .
2 . . _ _
3 . _ . _
4 . _ _ .

With local consistency, it enforces that in second row, you cannot place queen on column A and B. In third row, you cannot place queen on column A and C, and for forth row, you cannot place queen on column A and D.

Next, constraint programming will pick value for the second queen, which is column C.

A B C D
1 Q . . .
2 . . Q .
3 . . . .
4 . _ . .

You can see that, when we place second queen on column C, we cannot continue place queen on third row. Therefore, the solution is failed. Constraint programming will backtrack and try pick next value for the second queen, which is column D.

A B C D
1 Q . . .
2 . . . Q
3 . _ . .
4 . . _ .

Next, for the third queen.

A B C D
1 Q . . .
2 . . . Q
3 . Q . .
4 . . . .

Again, we cannot continue place queen for the forth row. Constraint programming will backtrack. The third row has only one option. Backtracking will perform again to the second row, unfortunately, second row used all available options. Then, we have to backtrack to the first row. Next value for the first row is column B.

A B C D
1 . Q . .
2 . . . _
3 _ . _ .
4 _ . _ _

Next, for second row.

A B C D
1 . Q . .
2 . . . Q
3 _ . . .
4 _ . _ .

Next, for third row.

A B C D
1 . Q . .
2 . . . Q
3 Q . . .
4 . . _ .

Next, for the last row.

A B C D
1 . Q . .
2 . . . Q
3 Q . . .
4 . . Q .

No conflict, solution is completed! Constraint programming can continue find whether there are any other solutions.

Next, we will start programming, and solve 8 queens problem.

Extension Methods for String

2008-01-25T00:09:00.000+07:00

This post continues on extension methods, now for string. String is the most common type in all programming languages. It is a human-readable text for any kind of information. These are some more extension methods, which may make you to present your data easier.

public static string Join(this IEnumerable<string> source, string separator) {
    string[] value = source as string[];
    if (value != null)
        return string.Join(separator, value);

    return string.Join(separator, source.ToArray());
}
public static string Reverse(this string text) {
    int len = text.Length;
    char[] charArray = new char[len--];
    for (int i = 0; len >= 0; i++, len--)
        charArray[i] = text[len];
    return new string(charArray);
}
public static string Repeat(this string source, int num) {
    if (num <= 0)
        return string.Empty;

    StringBuilder sb = new StringBuilder(source.Length * num);

    num.Times(x => sb.Append(source));
    return sb.ToString();
}

Join method is the same as String.Join, but this is for enumerable of string. Below is example.

var result = new[] { "Hello", "World!" }.Join(", ");
//result = "Hello, World!"

Reverse method is to reverse the character order of a string. Below is example.

var result = "Hello, World!".Reverse();
// result = "!dlroW ,olleH"

Repeat method is to duplicate a string for specific number of times. Below is example.

var result = "Hello, World!".Repeat(3);
// result = "Hello, World!Hello, World!Hello, World!"

Some more useful methods used to transform enumerable of objects to a string, which I always use when debugging. Following is the code.

public static string ListMembers<T>(this IEnumerable<T> source, string format, string separator) {
    return source.Select(s => string.Format(format, s)).Join(separator);
}
public static string ListMembers<T>(this IEnumerable<T> source) {
    return source.Select(s => s.ToString()).Join(" ");
}

ListMembers method can be used as ToString method. It transforms every object to string and join them together. Below is example.

var result = new[] { 1, 2, 3, 4, 5 }.ListMembers();
//result = "1 2 3 4 5"

Next post, go to interesting topic about finding solutions by specifying constraints. It is called Constraint Programming.

Extension Methods for Enumerable

2008-01-18T16:11:00.000+07:00

Visual Studio 2008 provides many extension method for enumerable, extension method in this post is additional extension that I wrote while developing programs.

public static IEnumerable<T> Repeat<T>(this IEnumerable<T> source, int num) {
    for (int x = 0; x < num; x++) {
        using (IEnumerator<T> source_enum = source.GetEnumerator()) {
            while (source_enum.MoveNext())
                yield return source_enum.Current;
        }
    }
}
public static IEnumerable<T> AsEnumerable<T>(T item) {
    yield return item;
}

Repeat method is to reiterate enumerable for specific amount of times. This method is unlike built-in Repeat method of VS 2008. The built-in Repeat method repeats a single item, but this Repeat method repeats an enumerable.

var result = new[] { 1, 2, 3 }.Repeat(3);
//result = {1, 2, 3, 1, 2, 3, 1, 2, 3}

Example above makes the repeat of array {1, 2, 3} for 3 times.

AsEnumerable method makes single item to an enumerable of single element. This method is unlike built-in AsEnumerable method of VS 2008. The built-in AsEnumerable method just cast an enumerable to IEnumerable interface. This AsEnumerable method is not casting, but wrap single item with enumerable.

var result = new[] { 1, 2, 3 }.Concat(Enumerable2.AsEnumerable(4));
//result = {1, 2, 3, 4}

Example above array of {1, 2, 3} is able to concatenate with enumerable of 4.

Some more functions:

public static bool All<T>(this IEnumerable<T> source, Func<T, int, bool> predicate) {
    int i = 0;

    foreach (T item in source) {
        if (!predicate(item, i++))
            return false;
    }
    return true;
}
public static bool Any<T>(this IEnumerable<T> source, Func<T, int, bool> predicate) {
    int i = 0;

    foreach (T item in source) {
        if (predicate(item, i++))
            return true;
    }
    return false;
}

Both All and Any methods are the same with built-in All/Any methods, but the different is these methods provide index used in predicate function.

var result = new[] { 0, 1, 2 }.All((x, i) => x == i);
//result = true

var result2 = new[] { 2, 1, 0 }.Any((x, i) => x == i);
//result2 = true

Example above, All method tests every element's value is equal to index, which is true. Any method tests any element's value is equal to index, it is true because number 1's value is equal to index.

Last 2 functions, these functions are not extension of enumerable, but they are related to enumerable.

public static IEnumerable<T> Enum<T>() {
    return System.Enum.GetValues(typeof(T)).Cast<T>();
}
public static T[] Append<T>(this T[] source, T item) {
    int len = source.Length;
    T[] ret = new T[len + 1];
    source.CopyTo(ret, 0);
    ret[len] = item;
    return ret;
}

Enum method creates enumerable from enum.

var result = Enumerable2.Enum<DayOfWeek>();
//result = {Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday}

Example above, Enum method creates enumerable of DayOfWeek type. Values range from Sunday to Saturday.

Append method appends an item to an array.

var result = new[] { 1, 2, 3 }.Append(4);
//result = {1, 2, 3, 4}

Example above 4 is appended to array of {1, 2, 3} and results to new array of {1, 2, 3, 4}.

Next post is still be on more Extension Methods.

Extension Methods for Delegate Types

2008-01-12T16:23:00.001+07:00

The great resource, that I highly recommend you to read is Wesdyer's blog. His blog contains much information about Functional Programming in C#. Articles you should read that relate to this post are Function Memoization and Partial Function Application.

Put this code onto your extension class (source: Wesdyer's blog).

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

Function Memoization is technic to speed up repeating calculation by storing arguments and result.

Compare this simple fibonacci function

Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
Console.WriteLine(fib(38));
//39088169
//2.35 seconds

with memoized fibonacci

Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
fib = fib.Memoize();
Console.WriteLine(fib(38));
//39088169
//0.01 second

Memoized function performs much faster. Just add only 1 line of code.

Partial Function Application is to define an argument of a function and create another function with remaining argument.

Here is an example.

Func<int, int, int> gcd = null;
gcd = (x, y) => (y == 0) ? x : gcd(y, x % y);
Func<int, int> gcdBy20 = gcd.Partial(20);
var max = 1.To(15).Max(gcdBy20);
//max = 10

First, we declare Greatest Common Divisor (GCD) function. Then, we partial it and create new gcdBy20 function. This function takes only one argument and return greatest common divisor with 20. To use, we generate numbers 1 to 15, and find which value has maximum gcdBy20.

Now more extension methods by me.

public static Func<T1, T2, TResult> Memoize<T1, T2, TResult>(this Func<T1, T2, TResult> func) {
    var dict = new Dictionary<T1, Func<T2, TResult>>();
    return (arg1, arg2) => {
        Func<T2, TResult> value;
        if (!dict.TryGetValue(arg1, out value)) {
            value = func.Partial(arg1).Memoize();
            dict.Add(arg1, value);
        }
        return value(arg2);
    };
}
public static Func<T, bool> And<T>(this Func<T, bool> predicate1, Func<T, bool> predicate2) {
    return arg => predicate1(arg) && predicate2(arg);
}
public static Func<T, bool> Or<T>(this Func<T, bool> predicate1, Func<T, bool> predicate2) {
    return arg => predicate1(arg) || predicate2(arg);
}
public static Func<T, TResult> When<T, TResult>(this Func<T, TResult> func, Func<T, bool> predicate, Func<T, TResult> alternative) {
    return arg => predicate(arg) ? alternative(arg) : func(arg);
}
public static Func<T1, T2, TResult> When<T1, T2, TResult>(this Func<T1, T2, TResult> func, Func<T1, T2, bool> predicate, Func<T1, T2, TResult> alternative) {
    return (arg1, arg2) => predicate(arg1, arg2) ? alternative(arg1, arg2) : func(arg1, arg2);
}

Memoize function memorizes the result of function with 2 arguments. The first memoize function is able to memorize only 1 argument. If you notice, you can see that this Memoize function uses both Partial and previous Memoize functionality to memorize.

And/Or functions are simple. They takes a predicate and produce another predicate with And/Or logic.

Func<int, bool> predicate = x => x % 2 == 0;
predicate = predicate.And(x => x % 3 == 0);
predicate = predicate.And(x => x % 4 == 0);
var value = 1.To(20).Where(predicate);
//value = {12}

Example above, we create predicate function which find whether x is divisible by 2 And 3 And 4. Then generate numbers 1 to 20, and filter which numbers pass the predicate.

"When" function provides conditional to evaluate alternative expression if condition is met.

Func<int, int> fact = null;
fact = x => fact(x - 1) * x;
fact = fact.When(x => x == 0, x => 1);
Console.WriteLine(fact(10));
//3628800

Factorial function equal to factorial of x - 1 multiply by x. But "When" function creates alternation instruction, when x equal to 0, result will equal to 1.

A little bit more extension methods

public static Func<T, bool> PredicateAll<T>(this IEnumerable<Func<T, bool>> source) {
    using (var source_enum = source.GetEnumerator()) {
        if (!source_enum.MoveNext())
            return x => true;

        Func<T, bool> result = source_enum.Current;
        while (source_enum.MoveNext())
            result = result.And(source_enum.Current);
        return result;
    }
}
public static Func<T, bool> PredicateAny<T>(this IEnumerable<Func<T, bool>> source) {
    using (var source_enum = source.GetEnumerator()) {
        if (!source_enum.MoveNext())
            return x => false;

        Func<T, bool> result = source_enum.Current;
        while (source_enum.MoveNext())
            result = result.Or(source_enum.Current);
      return result;
    }
}

PredicateAll transforms list of predicates to a predicate that will be true if all predicates are true. On the other hand, PredicateAny create predicate that will be false if all predicates false.

List<Func<int, bool>> predicateList = new List<Func<int, bool>>();
predicateList.Add(x => x % 2 == 0);
predicateList.Add(x => x % 3 == 0);
predicateList.Add(x => x % 4 == 0);
var predicateAll = predicateList.PredicateAll();
var predicateAny = predicateList.PredicateAny();

var result = 1.To(20).Where(predicateAll);
//result = {12}
var result2 = 1.To(20).Where(predicateAny);
//result2 = {2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20}

Example above, predicateAll returns true only numbers that is divisible by 2, and 3, and 4 which is 12. predicateAny returns true for any numbers that is divisible by 2, or 3, or 4 which are 2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20.

Next post continue on extension methods.

Infinite Sequence Part V - Pythagorean Triple

2008-01-09T09:54:00.002+07:00

Most of the time, if we think of sequence, it should be natural numbers. But this time, we change to geometry. An interesting geometry is Pythagorean triple. Pythagorean triple consists of 3 integer values which can be constructed a right triangle. A primitive Pythagorean triple is triple that all values in triple are coprime. Example of primitive Pythagorean triples are:

( 3, 4, 5) ( 5, 12, 13) ( 7, 24, 25)
( 8, 15, 17) ( 9, 40, 41) (11, 60, 61)
(12, 35, 37) (13, 84, 85) (16, 63, 65)

To generate a Pythagorean triple is easy, just pick 2 integer m and n where m > n. This is the formula to create Pythagorean triple.

Side a = m² - n²
Side b = 2mn
Side c = m² + n²

Such as number is 2 and 1.

Side a = 2² - 1²   = 3
Side b = 2 * 2 * 1 = 4
Side c = 2² + 1²   = 5

Now we get (3, 4, 5) triple.

This is the class that represent Pythagorean triple.

//Fix: 2008-02-29 - Make class immutable
public class PythagoreanTriple {
    int _seed1;
    int _seed2;
    int _size;
    int _sideA;
    int _sideB;
    int _sideC;

    public int Seed1 {
        get { return _seed1; }
    }
    public int Seed2 {
        get { return _seed2; }
    }
    public int Size {
        get { return _size; }
    }
    public int SideA {
        get { return _sideA; }
    }
    public int SideB {
        get { return _sideB; }
    }
    public int SideC {
        get { return _sideC; }
    }
    public int Perimeter {
        get { return _sideA + _sideB + _sideC; }
    }

    public PythagoreanTriple() : this(1, 1, 1) { }
    public PythagoreanTriple(int seed1, int seed2) : this(seed1, seed2, 1) { }
    public PythagoreanTriple(int seed1, int seed2, int size) {
        _seed1 = seed1;
        _seed2 = seed2;
        _size = size;
        calculateTriple();
    }

    void calculateTriple() {
        int seed1pow2 = _seed1 * _seed1 * _size;
        int seed2pow2 = _seed2 * _seed2 * _size;

        _sideA = seed1pow2 - seed2pow2;
        _sideB = 2 * _seed1 * _seed2 * _size;
        _sideC = seed1pow2 + seed2pow2;
    }
    public override bool Equals(object obj) {
        PythagoreanTriple p = obj as PythagoreanTriple;
        if (p == null)
            return false;
        return _seed1 == p._seed1 && _seed2 == p._seed2 && _size == p._size;
    }
    public override int GetHashCode() {
        return _sideA;
    }
    public override string ToString() {
        return string.Format("({0}, {1}, {2})", _sideA, _sideB, _sideC);
    }
}

SideA, SideB, SideC represent 3 numbers of Pythagorean triple. Seed1 and Seed2 represent 2 input numbers to calculate the triple. And Size is multiplier of each side. For instance, if Size is 2, SideA, SideB, SideC are double.

To generate primitive Pythagorean triple, Seed1 and Seed2 must be coprime, Seed1+Seed2 must be odd value, and Size must be 1. To find whether 2 integers are coprime, that 2 integers must have Greatest Common Divisor (GCD) equals to 1. This is the formula to calculate GCD.

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

Put this function into your extension class.

Now start creating Pythagorean sequence. Just put this few lines of code to create class.

public class Pythagorean : BaseSequence<PythagoreanTriple> {
    protected override IEnumerable<PythagoreanTriple> Enumerate() {
        for (int m = 2; ; m++) {
            for (int n = (m % 2 == 0) ? 1 : 2; n < m; n += 2) {
                if (Math2.Gcd(m, n) == 1)
                    yield return new PythagoreanTriple(m, n);
            }
        }
    }
}

You can notice that if m is even, n starting number is odd, and vice versa. And n is incresed by 2 every turn. This makes m+n always be odd number. And before creating new triple, we check that m and n is coprime. Therefore, this class will generate sequence of only primitive Pythagorean triple.

To create non-primitive Pythagorean triple, you can set Size of PythagoreanTriple to any positive integer. To calculate Size, you can find from dividing target SideC with current SideC, or dividing target Perimeter with current Perimeter.

Here is example from projecteuler.net
Find product abc of Pythagorean triplet, for which a + b + c = 1000.

var p = new Pythagorean().First(x => 1000 % x.Perimeter == 0);
p = new PythagoreanTriple(p.Seed1, p.Seed2, 1000 / p.Perimeter);
Console.WriteLine(p.SideA * p.SideB * p.SideC);
//31875000

Example above, we find first Pythagorean triple which its perimeter can be the divisor of 1000. Then, we create new Pythagorean triple from the triple we just found with size 1000/perimeter. Finally, print result sideA * sideB * sideC.

If p is the perimeter of a right angle triangle, {a, b, c}, which value, for p ≤ 1000, has the most solutions?

int[] list = new int[1000];
int maxSeed1 = (int)Math.Sqrt(500); //maxSeed1 = Sqrt(targetPerimeter/2)

new Pythagorean().TakeWhile(p => p.Seed1 <= maxSeed1).ForEach(p => {
    for (int i = p.Perimeter; i < 1000; i += p.Perimeter)
        list[i]++;
});
Console.WriteLine(0.To(999).OrderByDescending(x => list[x]).First());
//840

This problem, we must find how many items in the sequence we should generate. We should generate until last triple which its perimeter <= 1000. To find last seed1 value that its perimeter = 1000, use formula Sqrt(targetPerimeter/2). Now, for each triple we generate, mark in the list that which number its perimeter can be. And then sort the list, to find which number has the highest mark.

This post is an end of infinite sequence series. Next, we will go to totally different extension methods topic, which is extension methods for delegate types.

Infinite Sequence Part IV - Prime

2008-01-04T22:51:00.010+07:00

Countinue from last post, Fibonacci, which is considerable a simple sequence, because it uses only 2 preceding numbers to generate next number. This post, we move on to harder sequence which next number has to generate from all preceding numbers. The sequence is Prime.

Prime is natural number which there is only 2 natural number divisors. The numbers are 1 and itself. Prime below 100 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

The technique to store prime that I used is Sieve of Eratosthenes. I had optimized it by skip all even numbers. Memory usage for storing prime is adaptable. Initial capacity is 1,024 odd numbers and it can be extended to 1,073,741,824 odd numbers which cover all interger values.

Here is the code for class to store prime:

public class PrimeStore {
    const int defaultCapacity = 1024;
    BitArray _store;
    int _lastIndex;

    public PrimeStore() {
        _store = new BitArray(defaultCapacity, true);
    }
    public PrimeStore(int capacity) {
        _store = new BitArray(capacity, true);
    }

    public bool IsPrime(int num) {
        if (num < 2)
            return false;
        if (num == 2)
            return true;
        if ((num & 1) == 0)
            return false;

        int index = (num - 3) >> 1;
        testPrime(index);
        return _store.Get(index);
    }
    void testPrime(int index) {
        if (index <= _lastIndex)
            return;

        ensureCapacity(index);

        for (int prime; _lastIndex < index; _lastIndex++) {
            if (_store.Get(_lastIndex)) {
                prime = (_lastIndex << 1) + 3;
                applyPrime(prime, _lastIndex);
            }
        }
    }
    void ensureCapacity(int index) {
        int lastIndex = _store.Count - 1;
        if (index <= lastIndex)
            return;

        int newCapacity = _store.Count;
        while (index >= newCapacity)
            newCapacity = newCapacity * 2;

        int newSize = newCapacity / 32;
        int[] array = new int[newSize];
        _store.CopyTo(array, 0);
        for (int i = _store.Count / 32; i < newSize; i++)
            array[i] = -1;
        _store = new BitArray(array);

        for (int i = 0, prime, num; i < _lastIndex; i++) {
            if (_store.Get(i)) {
                prime = (i << 1) + 3;
                num = lastIndex - i;
                applyPrime(prime, num - (num % prime) + i);
            }
        }
    }
    void applyPrime(int prime, int index) {
        index += prime;
        int capacity = _store.Count;
        for (; index < capacity && index > 0; index += prime)
            _store.Set(index, false);
    }
}

Usage of PrimeStore class is easy. Just pass a number to IsPrime method.

bool isPrime = new PrimeStore().IsPrime(34567);

But our objective is not just for test a prime number. We will generate prime sequence. Our prime sequence will use PrimeStore to store prime numbers. Any prime numbers beyond PrimeStore's capacity will be calculated by testing there is no prime divisor for that numbers.

To limit growth of PrimeStore, I also defined MaxStoredValue. Default value is 65,536. Generating prime below MaxStoredValue is fast. Generating prime beyond MaxStoredValue but below MaxStoredValue^2 is acceptable speed. Generating prime beyond MaxStoredValue^2 is considerable slow. Default value is suited with general prime generation.

Here is the prime sequence code:

public class Prime : BaseSequence<long> {
    PrimeStore _primeStore;
    const long maxStoredValue = 2147483647L;

    public Prime() {
        _primeStore = new PrimeStore();
    }
    public Prime(int capacity) {
        _primeStore = new PrimeStore(capacity);
    }

    protected override IEnumerable<long> Enumerate() {
        yield return 2L;

        long value = 3L;
        yield return value;

        while (true) {
            do
                value += 2L;
            while (!Contains(value));
            yield return value;
        }
    }
    public bool Contains(long value) {
        if (value < maxStoredValue)
            return _primeStore.IsPrime((int)value);

        return Factors(value).First() == value;
    }
    public IEnumerable<long> Factors(long value) {
        if (value < 2L)
            yield break;

        using (IEnumerator<long> enumerator = Enumerate().GetEnumerator()) {
            enumerator.MoveNext();

            long factor = enumerator.Current;
            long pow = factor * factor;
            long num = value;
            long mod, num2;

            while (num >= pow) {
                num2 = Math.DivRem(num, factor, out mod);
                if (mod == 0L) {
                    num = num2;
                    yield return factor;
                } else {
                    enumerator.MoveNext();
                    factor = enumerator.Current;
                    pow = factor * factor;
                }
            }
            yield return num;
        }
    }
}

Other methods beside generating prime sequence are Contains method and Factors method. Contains method is to test whether a number is prime. And Factors method is to enumerate prime factors for a number.

As usual, test prime sequence with projecteuler.net.
Find the largest prime factor of 317584931803.

Console.WriteLine(new Prime().Factors(317584931803).Max());
//3919

Find the 10001^st prime.

Console.WriteLine(new Prime().ElementAt(10000));
//(10000 is index of position 10001st)
//104743

Even creating a prime sequence has many details, but using of prime sequence is simple and fast.

Next we will create sequence which is not the number. Continue next post :)

Infinite Sequence Part III - Fibonacci

2007-12-29T15:13:00.001+07:00

Last post, I had described about how to create based class for infinite sequence, and create a simple generic sequence. This post, we will move on to Fibonacci sequence.

Each Fibonacci number is the sum of 2 preceding number. First and second Fibonacci numbers are 0 and 1. Third Fibonacci number is the sum of First and Second (0+1) equal to 1. And forth Fibonacci number is the sum of Second and Third number (1+1) equal to 2. First 20 Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181.

Now let's start coding Fibonacci.

public class Fibonacci : BaseSequence<BigInteger> {
    protected override IEnumerable<BigInteger> Enumerate() {
        BigInteger value = BigInteger.Zero;
        BigInteger value2 = BigInteger.One;

        yield return value;
        yield return value2;
        while (true) {
            value += value2;
            yield return value;
            value2 += value;
            yield return value2;
        }
    }
}

Just few lines of code, Fibonacci sequence is finished! Value and value2 return value alternately. Value variable return value in odd position. And value2 return value in even position.

Test Fibonacci sequence with projecteuler.net questions.
Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed one million.

Console.WriteLine(
    new Fibonacci().TakeWhile(x => x < 1000000).Where(x => x % 2 == 0).Sum()
);
//1089154

What is the first term in the Fibonacci sequence to contain 1000 digits?

Console.WriteLine(
    new Fibonacci().TakeWhile(x => x.ToString(10).Length < 1000).Count()
);
//4782

Next post, we will go to much harder sequence, which is Prime sequence.

Infinite Sequence Part II - GenericSequence

2007-12-25T01:23:00.001+07:00

Last post, I had introduce about infinite sequence. Infinite sequence is list that has infinity items. This part I will show how to create class for infinite sequence. Now let's start coding.

Begin with creating the based class. Its based class name is BaseSequence and it is generic typed. This class represents based class of all sequences.

//Fix: 2008-03-08 - Cut off unused ..OrDefault methods
public abstract class BaseSequence<T> {
    protected abstract IEnumerable<T> Enumerate();

    public T ElementAt(int index) {
        return Enumerate().ElementAt(index);
    }
    public T First() {
        return Enumerate().First();
    }
    public T First(Func<T, bool> predicate) {
        return Enumerate().First(predicate);
    }
    public IEnumerable<T> Take(int count) {
       return Enumerate().Take(count);
    }
    public IEnumerable<T> TakeWhile(Func<T, bool> predicate) {
        return Enumerate().TakeWhile(predicate);
    }
    public IEnumerable<T> TakeWhile(Func<T, int, bool> predicate) {
        return Enumerate().TakeWhile(predicate);
    }
}

Enumerate method will enumerate items indefinitely. Therefore, we have to declare it as protected. And we also have to provide methods that is able to enumerate and break from loop for a certain criteria. ElementAt method get item for a specific index. First method get the first item. Take method get list of items for a specific criteria.

And now create an easy derived class called GenericSequence. This class lets user passes a function to generate next items. User can also pass seed value, in order to set the initial value.

public class GenericSequence<T> : BaseSequence<T> {
    Func<T, T> _func;
    T _seed;

    public GenericSequence(Func<T, T> func) {
        _seed = default(T);
        _func = func;
    }
    public GenericSequence(T seed, Func<T, T> func) {
        _seed = seed;
        _func = func;
    }

    protected override IEnumerable<T> Enumerate() {
        T value = _seed;

        yield return value;
        while (true) {
            value = _func(value);
            yield return value;
        }
    }
}

Now test the class with question from projecteuler.net again :)

Find the longest sequence using a starting number under one million.
Defined n = n/2 (n is even)
and n = 3n + 1 (n is odd)
Finish when n is 1

//y is even (y = y/2), y is odd (y = 3y + 1)
Func<long, long> sequenceFunc = y =>
    (y % 2 == 0) ? y / 2 : y * 3 + 1;

//Count sequence length
Func<int, int> countSequence = x =>
    new GenericSequence<long>(x, sequenceFunc)
    .TakeWhile(y => y > 1) //Take until y = 1
    .Count();               //Count the length

//Print out
Console.WriteLine(1.To(999999) //Test all values < 1 million
    .OrderByDescending(countSequence)   //sort by count length
    .First()                    //Get only highest count
);

Or in short

Console.WriteLine(1.To(999999).OrderByDescending(x =>
    new GenericSequence<long>(x, y =>
        (y % 2 == 0) ? y / 2 : y * 3 + 1
    ).TakeWhile(y => y > 1).Count()
).First());
//837799

We can completed the question in one statement, even it may looked complicated. Anyway, if you create many nested loops it is also complicated and even harder to read.

Next post, we will create Fibonacci sequence ;)

Infinite Sequence Part I - Introduction

2007-12-21T12:46:00.000+07:00

Sequence includes finite sequence and infinite sequence. Finite sequence is a set. There are many classes in .NET that represent set such as Array, List, & Collection. With classes, you can reuse its functionality. Such as you want to find whether an object is in a list you can write:

bool exists = list.Contains(obj);

Or if you want to enumerate for first 10 objects:

var newList = list.Take(10);

Infinite sequence is infinity-members of list. Basic sample of infinite sequence is Natural numbers (1,2,3,...), Odd numbers (1,3,5,...), & Even numbers (2,4,6,...). But how can you represent infinite sequence into class? Such as if I want to find whether is 4 in Odd numbers, can I write?:

bool exists = oddNumbers.Contains(4);
//false

Or take first 10 numbers in Odd sequence:

var tenOdd = oddNumbers.Take(10);
//{1,3,5,7,9,11,13,15,17,19}

Most of the time, if you deal with above questions, you may rather write:

bool isOdd = 4 % 2 == 1

and

for (int i = 1; i <= 19; i += 2)

That means you have to know functionality of the sequence in order to use it. And you have to rewrite the function everytime. Odd and Even numbers are simple. How about Fibonacci and Prime sequence? Their incremental is not linear. And to check members in the list is more complex.

Is it easier if we can check a number prime list the same as we check in simple List?

var isPrime = prime.Contains(34567);

And get the first 1000 Fibonacci value without having to write codes to generate Fibonacci value everytime.

var milFib = fib.Take(1000);

How can you represent infinite sequence into class?
Continue next post :)

BigInteger, an integer with unbounded length

2007-12-19T22:37:00.001+07:00

Usaully, when you think of number, Int32 almost covers all requirements. Its maximum value is 2,147,483,647. It almost never overflow. Int32 is not enough? That's very rare case. But you can using Int64 which its maximum value is 9,223,372,036,854,775,807 which considers an extreamly large number. Is it possible that an operation will make Int64 be overflown? It is possible. In mathematics and cryptography, large precision calculation is needed, and data length of an integer can be extended indefinitely.

Which type shall we use next to Int64? If your answer is Int128, the answer is wrong. Next class we gonna use has no length limitation. It is an integer with unbounded length. This type is called BigInteger.

BigInteger is not included in current C# package. But now you can find BigInteger in Silverlight package. Once you install Silverlight, BigInteger can be found in [drive]:\Program Files\Microsoft Silverlight\Microsoft.Scripting.dll under the namespace Microsoft.Scripting.Math.

Let's play around BigInteger (question from projecteuler.net) :)
Find the sum of digits in 100!

BigInteger bigInt = 1;
100.DownTo(2).ForEach(x => bigInt *= x);    //Factorial 100!
Console.WriteLine(bigInt.ToString(10).Sum(c => (int)(c - '0')));    //Sum of Digit
//648

More question :)
What is the sum of the digits of the number 2¹⁰⁰⁰?

BigInteger bi = 1;
1000.Times(x => bi *= 2);    //2¹⁰⁰⁰
Console.WriteLine(bi.ToString(10).Sum(c => (int)(c - '0')));    //Sum of Digit
//1366

Factorial of 100 and 2 power by 1000, Int64 is generally unable to handle above questions. But BigInteger can handle it easily and fast.

As a bonus, I had written some Extensions for BigInteger. First method is for getting sum of a list of BigInteger.

public static BigInteger Sum(this IEnumerable<BigInteger> source) {
    BigInteger num = BigInteger.Zero;
    foreach (BigInteger num2 in source)
        num += num2;
    return num;
}
public static BigInteger Sum<T>(this IEnumerable<T> source, Func<T,BigInteger> selector) {
    return source.Select(selector).Sum();
}

Usage:

var list = new BigInteger[] { 1, 2, 3 };
Console.WriteLine(list.Sum());
//6

Next method is for parsing string into BigInteger:

public static BigInteger Parse(string s) {
    using (System.IO.StringReader reader = new System.IO.StringReader(s)) {
        char[] buffer = new char[10];
        int startIndex = 0;
        uint[] multiplier = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };

        int count = reader.ReadBlock(buffer, 0, 9);
      BigInteger ret = int.Parse(new string(buffer, 0, count));
        if (ret.IsNegative())
            startIndex = 1;

        while (count == 9) {
            count = reader.ReadBlock(buffer, startIndex, 9);
            ret *= multiplier[count];
            ret += int.Parse(new string(buffer, 0, count + startIndex));
        }
        return ret;
    }
}
public static bool TryParse(string s, out BigInteger result) {
    try {
        result = Parse(s);
        return true;
    } catch {
        result = null;
        return false;
    }
}

Usage

BigInteger i = BigIntegerExtension.Parse("1234567890");
Console.WriteLine(i);
//1234567890

Next post, I will show you somethings bigger than BigInteger :)

How to use Extension Methods to extend C# language

2007-12-16T06:45:00.001+07:00

Start my first blog with coding!

Usually, when we want to extend a type, we need to create a new derived type. But creating a new derived type, sometimes it is not suitable. Sometimes the extensions are so small, sometimes types are sealed and unable to be extended. Another solution is you can create new static methods. But those methods are not become parts of the type. New Visual Studio 2008 has a new feature enables you to add new methods without having to derive a type and able to create new methods that will become a part of the type. This new feature called "Extension Methods".

Interesting point is, we can use "Extension Methods" to enhance built-in types like int or IEnumerable. And that could change style of coding which totally different from C# 2.0. Do you know Ruby? Ruby is a programming language that is short and easy. Let's make C# to be as easy as Ruby.

Start with foreach. When you enumerate items in a list you use:

foreach (Object item in list)

But not in Ruby, in Ruby we just write:

list.each{|item| ...}

How easy! To make code like Ruby, put this source on your extension class.

public static void ForEach<T>(this IEnumerable<T> source, Action<T> action) {
    foreach (T item in source)
        action(item);
}
public static void ForEach<T>(this IEnumerable<T> source, Action<T, int> action) {
    int i = 0;

    foreach (T item in source)
        action(item, i++);
}

After extension, you can write:

list.ForEach(item => ...);
list.ForEach((item,index)=> ...);

Here is the example:

string[] persons = new string[] {"Jack", "Lisa", "Ryan"};
persons.ForEach(person => Console.WriteLine("Hello {0}!", person));
//Hello Jack!
//Hello Lisa!
//Hello Ryan!

persons.ForEach((person, index) => Console.WriteLine("{0}. {1}", index + 1, person));
//1. Jack
//2. Lisa
//3. Ryan

Is that ok with you? If you like Ruby style go to next method. When we run number 0 to 2 (run 3 loop) we usaully write:

for (int i = 0; i <= 2; i++)

Ruby is much easily:

0..2

or

3.times{|x| ..}

Jealous? Put this source on your extension class:

public static IEnumerable<int> To(this int from, int to) {
    for (int x = from; x <= to; x++)
        yield return x;
}
public static IEnumerable<int> DownTo(this int from, int to) {
    for (int x = from; x >= to; x--)
        yield return x;
}
public static IEnumerable<int> StepTo(this int from, int to, int step) {
    if (step > 0) {
        for (int x = from; x <= to; x += step)
            yield return x;
    } else if (step < 0) {
      for (int x = from; x >= to; x += step)
            yield return x;
    } else {
        throw new ArgumentException("Step cannot be zero.", "step");
    }
}
public static void Times(this int num, Action<int> action) {
    for (int x = 0; x < num; x++)
        action(x);
}

Now you can write:

string[] persons = new string[] { "Jack", "Lisa", "Ryan" };
0.To(2).ForEach(i => Console.WriteLine(persons[i]));
//Jack
//Lisa
//Ryan

2.DownTo(0).ForEach(i => Console.WriteLine(persons[i]));
//Ryan
//Lisa
//Jack

0.StepTo(2, 2).ForEach(i => Console.WriteLine(persons[i]));
//Ryan
//Jack
//(run 0 to 2 with step 2)

3.Times(i => Console.WriteLine(persons[i]));
//Jack
//Lisa
//Ryan

Try practical use, with question from projecteuler.net.
Add all the natural numbers below 1000 that are multiples of 3 or 5.

Console.WriteLine(1.To(999).Where(x => (x % 3 == 0) || (x % 5 == 0)).Sum());
//233168

Now we can completed question above with only one line of code. If you use C# 2.0, you will never write code like this. There are more several methods that you can extend C# from Ruby (or any other languages). Make your code shorter, your life will be easier.