Extension Methods for String

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

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

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

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

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 :)