February 22nd, 2010 | 
Author: As always, you can find my source code at CodePlex.
Problem 11 has given me all kinds of trouble. So much so that I haven’t actually solved it. I’ve tried 2 or 3 different methods, I’ve Google it, I’ve tried cheating, I’ve tried guessing. Nothing is working for me. I gave up after many, many tries. I’m so sure that I’m doing it right, but I must be missing one minor thing somewhere.
Problem 12 was kinda fun. The meat of the problem is figuring out the factors of a given number. Once I had that (which was easy to brute force, and a little tricky to slim down), the rest is just a couple of for-loops. I used the given example as a single test case.
Problem 13 involves very, very large numbers. Larger than 32-bits can represent. So, since I was still using .NET 3.5 at the time, I scratched out a very rudimentary “BigInt” class that only performed addition on itself. It was just as much a pain in the neck as it was 10 years in Introduction to C++ class, except this time I only implemented one operator. Once I switched the Project Euler solution over to VS2010 and .NET 4, I went back and switched this solution to use the BigInteger class, which, by the way, is new to .NET (obviously) and lives in System.Numerics. Anyway, once you have your own BigInt or BigInteger (or some language like Ruby that handles all that nonsense for you), Problem 13 is a piece of cake: just do some adding up and some parsing. I wrote a couple of tests that used long.MaxValue—I left them in, even though it’s generally quite silly to test a class built into the framework.
If you guys have any ideas for Problem 11, I would love a fresh set of eyes.
Tags:
I just wrote up a brute force attack on 11 and it worked.
Write a method which turns the grid into an enumeration of 4-int tuples. Then use IEnumerable.Max(t => t.Item1 * t.Item2 * t.Item3 * t.Item4) to find the biggest product.
Matt,
My thoughts on problem 11 is that it basically revolves around having a function that can find the maximum product of an array of 20 (or fewer) numbers. I’ll call this function maxProductOfRow.
Once you have that function, the entire algorithm would just be:
-Calculate maximum product for rows(1..20)
-Calculate maximum product for columns(1..20)
-Calculate maximum product for diagonals(1..64)
While you’re doing that, you keep track of the current maximum product and keep replacing it when you find a new one with its location.
The function maxProductOfRow would look something as follows, I think:
maxProductOfRow(array diagonal[0..19])
{
int currentMax = 0; — Index of the first element of our "current maximum"
int maxProduct = 0; — Actual value of product
stack possibleCandidates;
while ((currentMax + 4) 20)
{
if (diagonal[currentMax + 4] > diagonal[currentMax])
{
currentMax++;
}
else
{
possibleCandidates.push(currentMax);
currentMax++;
}
}
foreach (possibleCandidate)
{
int product = 0;
int candidate = possibleCandidate.pop();
product = diagonal[candidate] * diagonal[candidate+1] * diagonal[candidate+2] * diagonal[candidate + 3];
if (maxProduct product)
{
maxProduct = product;
currentMax = candidate;
}
}
return currentMax, maxProduct; — Structure or globals or something to save off both
}
All it really does is brute force the row, but does some selective skipping over sections like [1,2,5,7,9,15]. 1*2*5*7 is clearly less than 2*5*7*9, which is clearly less than 5*7*9*15, so we don’t need to actually compute those products. It can also probably be optimized in the event you find a 0, you can totally skip the 3 nearest to the 0 since their products will all come out to 0, too.
That is how I would approach the problem, at least.
My method of attack is very similar to both of you guys, but I just don’t get the right answer, so it must be something really stupid that I’m doing wrong (like a typo or a misplaced operator or something). At code&coffee this morning, I thought about solving the problem in Excel just to get the right answer and then work backwards…
You’ve probably solved this, but for anyone else who came here in search of information about this problem…
I used a brute forcing method to solve this. It takes only a fraction of a second to run. The code was more or less the same I used for a Blocks game that had to detect vertical, horizontal, and diagonal matches of three or more in a row.
Basically the code was:
for each row
for each item in row
for each vector: ((1,0), (1,1), (0,1), (-1,1))
Then just iterate through every item on every row, adding the (x,y) values to its coordinates four times, catching the numbers on those coordinates. If the for-loop hits a border with less than four items, abort and switch to the next vector. In python this was a simple deal with the enumerate() function to get the necessary coordinate data.