Vasu Balakrishnan’s Blog

Archive for May 2009

C# Yield Keyword

leave a comment »

According to MSDN “Used in an iterator block to provide value to the enumerator object or to signal the end of iteration”. But there is much more to this keyword, which I found is not explained well (at least to me) in the documentation. You’ll see that yield keyword is sort of foundation to LINQ concepts and introduces the notion of lazy evaluation (which people familiar with Functional Programming know).

Yield allows one enumerable function to be implemented in terms of another. It avoids lot of code that we had to write in order to expose a custom enumerator. This was introduced in C# 2.0 and back then I was able to write the code below

public class MyCollection<T>
{
    private List<T> Items;

    ...

    public IEnumerable<T> FindAll(Predicate<T> pPredicate)
    {
        foreach (T lItem in Items)
        {
            if (pPredicate.Invoke(lItem))
                yield return lItem;
        }
    }
}

I didn’t pay attention to this until I started to use LINQ / Functional Programming concepts. The reason is yield return exhibits a lazy evaluation / deferred execution behaviors. I didn’t get it at first. For this I had to understand the behavior of the IEnumerator.

Enumerators are used to read data in a collection. Initially, the enumerator is positioned before the first element. You must call MoveNext to advance the enumerator and retrieve the value using Current property. MoveNext tells you whether you’ve hit the end of collection by returning false.

When you use yield keyword, the compiler internally creates an Enumerator class that keeps the state of current iteration. When you are iterating a collection that is implemented using yield return, you’re moving from item to item in the Enumerator using MovingNext method. That’s the key right here for the lazy evaluation.

When the code encounters a yield return statement, it gets the item from the enumerator and returns it to the caller. Any other code following the yield statement is not executed and the next item is not processed, until the caller requests for the next item. This is where lazy evaluation comes into picture. You don’t have to enumerate all the items in the collection, and you do so only if the caller asks for it.  Also, when a method has a yield statement, the execution of method doesn’t begin until the calling method first iterates over the resulting IEnumerable. This is known as Deferred Execution. With these, you can chain iterators without actually enumerating anything until you actually need them.

This is the foundation block for LINQ. LINQ Operators like Select, Where, etc are implemented as iterators that are created with yield statement.

For further reading, I would recommend these articles

Written by nbvasu

May 20, 2009 at 3:35 pm

Posted in C#

Project Euler #30

leave a comment »

Problem: Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Answer: 443839

Solution:

My first pass was to check all numbers between 2 and 1 million. Then I realized that I could reduce the range. The max value for a digit is 9^5 (59049) and the max number could be 59049 times number of digits. This is more of a brute force. I’m sure there is a better way to get down the max range. I’ve reused my ToDigits extension method.

var x =  Enumerable.Range(2, 295245)
          .Where(pArg => pArg.ToDigits().Sum(pArg1 => Math.Pow(pArg1, 5)) == pArg)
          .Select(pArg => pArg);
var lAnswer = x.Sum();

 

Time: 930 ms

Written by nbvasu

May 19, 2009 at 10:47 pm

Posted in C#, Euler

Project Euler #11

leave a comment »

 

Problem: What is the greatest product of four numbers on the same straight line in the 20 by 20 grid?

Answer: 70600674

Solution:

I decided to use Microsoft.FSharp.Math.Matrix to solve this puzzle. It exposes methods to get slices of the matrix and it was easy to use with one caveat which I’ll talk about in a little while.

First I’d read the input grid and load them into the above Matrix object. You can create the matrix from a Sequence. So I decided to generate an IEnumerable<IEnumerable<double>>.

var lDoubles = ReadLines("FunctionalProgramming.Problem11.txt")
    .Select(pArg => pArg.Split(" ".ToCharArray(), StringSplitOptions.RemoveEmptyEntries)
                        .Select(pArg1 => Convert.ToDouble(pArg1)));

var lMatrix = MatrixModule.of_seq(lDoubles);

 

Now that we have the matrix loaded, we need to compute product of 4 adjacent numbers in any direction. I created an extension  method that would return a sequence of 4 adjacent numbers in a given direction. I can then re-use this method for different directions.

public static IEnumerable<Matrix<T>> GetRegion<T>(this Matrix<T> pMatrix,
                                                  int pRowStartId,
                                                  int pColStartId,
                                                  int pRowSize,
                                                  int pColSize)
{
    for (int i = pRowStartId; i <= pMatrix.NumRows - pRowSize; i++)
    {
        for (int j = pColStartId; j <= pMatrix.NumCols - pColSize; j++)
        {
            yield return MatrixModule.Generic.getRegion(pMatrix, i, j, 
                                                        pRowSize, pColSize);
        }
    }
}

 

To get a sequence of 4 adjacent numbers

  • left to right, I use GetRegion(0, 0, 1, 4) and get the RowVector object.
  • top to down, I use GetRegion(0, 0, 4, 1) and get the Vector object
  • Along the primary diagonal, I use GetRegion(0, 0, 4, 4) and get the Diagonal object.

To get product of 4 adjacent elements, I use VectorModule.prod method. So for every 4 adjacent numbers from the above sequence I calculate the product and take the Max.

var lRowMax = lMatrix.GetRegion(0, 0, 1, 4).Select(pArg => VectorModule.prod(pArg.ToRowVector().Transpose)).Max();
var lColMax = lMatrix.GetRegion(0, 0, 4, 1).Select(pArg => VectorModule.prod(pArg.ToVector())).Max();
var lDiagMax = lMatrix.GetRegion(0, 0, 4, 4).Select(pArg => VectorModule.prod(pArg.Diagonal)).Max();
var lMax = Math.Max(Math.Max(lRowMax, lColMax), lDiagMax);

 

There is only one thing left. I didn’t traverse along the secondary diagonal (along north-east). There is no built in methods within Matrix object to do so. I’d to create another matrix but reverse the rows. Once I did that, I’d to reuse the same logic as above to get the max value along the secondary diagonal

var lMatrix1 = MatrixModule.of_seq(lDoubles.Select(pArg => pArg).Reverse());
lRowMax = lMatrix1.GetRegion(0, 0, 1, 4).Select(pArg => VectorModule.prod(pArg.ToRowVector().Transpose)).Max();
lColMax = lMatrix1.GetRegion(0, 0, 4, 1).Select(pArg => VectorModule.prod(pArg.ToVector())).Max();
lDiagMax = lMatrix1.GetRegion(0, 0, 4, 4).Select(pArg => VectorModule.prod(pArg.Diagonal)).Max();
lMax = Math.Max(lMax, Math.Max(Math.Max(lRowMax, lColMax), lDiagMax));

 

Time: 119 ms

Written by nbvasu

May 19, 2009 at 10:16 pm

Posted in C#, Euler

Project Euler #8

leave a comment »

 

Problem: Discover the largest product of five consecutive digits in the 1000-digit number.

Answer: 40824

Solution: First I created a helper routine GetNCharacters that would give me a list of N character length string. First I get a list of 5 consecutive characters, and for each item in that list I aggregate the individual character to get the product. See how I reuse the same helper routine inside.

private static IEnumerable<string> GetNCharacters(string pString, int pNumChars)
{
    for (int lStart = 0; lStart <= pString.Length - pNumChars; lStart++)
    {
        yield return pString.Substring(lStart, pNumChars);
    }
}

var lQuery = GetNCharacters(ReadFile("Problem8.txt"), 5)
                .Select(pArg => GetNCharacters(pArg, 1)
                                    .Aggregate(1, (pSeed, pId) => pSeed * pId[0].ToNumber()));
var lAnswer = lQuery.Max();

Time: 11 ms

Written by nbvasu

May 15, 2009 at 4:30 pm

Posted in C#, Euler

Project Euler #36

leave a comment »

 

Problem: Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2.

Answer: 872187

Solution: I’m using String Reverse to figure out if its a palindrome. I’m not sure if there is a better way to do it.

var lQuery =    from lNumber in Enumerable.Range(1, 1000000)
                let lBase10 = lNumber.ToString()
                let lBase10Rev = new string(lBase10.Reverse().ToArray())
                let lBase2 = Convert.ToString(lNumber, 2)
                let lBase2Rev = new string(lBase2.Reverse().ToArray())
                where lBase10 == lBase10Rev
                && lBase2 == lBase2Rev
                select lNumber;
var lAnswer = lQuery.Sum();

Time: 6417 ms

Written by nbvasu

May 15, 2009 at 3:41 pm

Posted in C#, Euler, General

Project Euler #16

leave a comment »

Problem: What is the sum of the digits of the number 21000?

Answer: 1366

Solution: I’d to use F# BigInt and my ToDigits() extension method from the previous post.

var lNum = BigInt.Pow(new BigInt(2), BigInt.FromInt32(1000));
var lAnswer = lNum.ToDigits().Sum();

Time: 12 ms

Written by nbvasu

May 15, 2009 at 3:20 pm

Posted in C#, Euler, General

Project Euler #13

leave a comment »

 

Problem : Find the first ten digits of the sum of one-hundred 50-digit numbers.

Answer: 5537376230

Solution:

Thanks to this article, I got a good tip for reading file contents line by line, the Functional way. Since these were big numbers I used F# BigInt to solve the problem

var lContent = ReadLines("Problem13.txt")
                    .Select(pArg => BigInt.Parse(pArg));

var lAnswer = lContent.Aggregate(BigInt.Zero, 
                                (pSeed, pId) => pSeed + pId).ToString().Substring(0, 10);

Time: 25 ms

Written by nbvasu

May 15, 2009 at 3:14 pm

Posted in C#, Euler, General