Vasu Balakrishnan’s Blog

Archive for the ‘Euler’ Category

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

Advertisements

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

Project Euler #22

leave a comment »

 

Problem: What is the total of all the name scores in the file of first names?

Answer: 871198282

Solution: It was quite easy to implement with LINQ. This goes to show the power of LINQ and the readability of a Functional Program.

var lContent = ReadFile("Problem22.txt");
var lWords = lContent
    .Replace("\"", "")
    .Split(",".ToCharArray(), StringSplitOptions.RemoveEmptyEntries);

var lNumWords = lWords
    .OrderBy(pArg => pArg)
    .Select((pString, pIndex) =>
            (pIndex + 1) * pString.Sum(pCharArg => pCharArg.ToOrdinal())
    );

var lAnswer = lNumWords.Sum();

Time: 59 ms

Written by nbvasu

May 15, 2009 at 2:40 pm

Posted in C#, Euler, General