Vasu Balakrishnan’s Blog

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

Advertisements

Written by nbvasu

May 19, 2009 at 10:16 pm

Posted in C#, Euler

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: