Infinite Sequence Part II - GenericSequence

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