Project Euler #30

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

Project Euler #11

 

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