mgroves

Problem 22 was pretty straightforward; the problem description lays out the algorithm. One elegant piece of Linq was: word.Sum(c => c - ('A' - 1)), which sums up each letter score of the word nice and compactly.

Problem 23 - given the upper and lower limits of all possible abundant sums, this problem was, again, straightforward given the algorithm description. The toughest part was getting it performant, which is why I used a lookup collection for the IsAbundant method. At this point, my MathHelper class is coming in very handy, so I may just release it as its own project one day (though I'm sure there are many other equally good Math libraries for .NET).

Problem 24 - I did solve this problem, but my solution was not fast enough. Once I got the answer, I looked to see how other Eulers were doing it. So, for this class, I have both my solution and the more correct, "Fast" solution in the code. I think later on, I eventually created a permutation class, so I may need to revisit this problem with that class.

Problem 25 - Another easy one with BigInteger. I used a KeyValuePair because I was curious to see the actual number in the sequence, not just the index.

Problem 26 - This one took a lot of research and thinking. I spent a lot time reading about Cyclic numbers and Primitive roots. The solution feels like kinda a cheat to me, but I really don't see any way around it since "No simple general formula to compute primitive roots modulo n is known". Fortunately, Wikipedia lists just enough of them for me to solve the problem.

Problem 27 - I came up with a handy Quadratic class for this problem. I think in this case, the problem sounds pretty complex, but I broke it down into individual parts the best I could, and everything fit pretty well together. This is also a good strategy if you are having performance issues, as it will be easier for a profiler to point out where exactly the bottleneck is (hint: it's almost never where you think).

As always, you can view my code at CodePlex – feel free to submit criticisms/comments/patches there, or use the framework for your own Project Euler solution.

I spent a lot of time thinking about problem 18.  I knew that a brute-force solution might work, but as the problem states, I would have to face a larger version later on, so it would be in my best interest to write a solution that could handle a larger set.  The trick to problem 18 (and 67) is to think from the bottom-up, instead of the top-down.  Given a three-number pyramid, it’s easy to see that the high sum path depends entirely on the larger of the two bottom numbers.  Once you know that, just work your way up the pyramid, two rows at a time.  The rest of the class is just parsing and setup code.

Problem 19 is stupidly easy using the DateTime class that .NET provides.  I mean, it was just so trivial it’s barely worth mentioning.

Problem 20 would take a lot more thinking and work, were it not for the BigInteger class in .NET 4.  Since I have that available, I just made a Factorial method and a method to parse out a string into digits and sum them up.

I was stuck on Problem 21 for a bit.  Note that I was getting to problem 21 soon after I finally got problem 11 solved.   The main block I had on problem 21 was that I was just overthinking it.  The answer was very simple once I just broke it up into a series of simple steps—a nice, elegant solution emerged.

I was at a “Code and Coffee” session when I solved problem 21.  I had time left, so I paired up to solved problem 22.  This solution was very concise to express with Linq.  The crux of the problem was figuring out a good way to get a score for each letter.  It turns out the syntax is very similar to C++ [c - (‘A’ – 1) was all it took to score a single letter].  Thanks to the power of Linq, a string can be viewed as a collection of characters, and thus the ‘Sum’ extension method works on it.

As always, you can view my code at CodePlex – feel free to submit criticisms/comments/patches there, or use the framework for your own Project Euler solution.

I’ve been cranking away at Euler problems lately.  It’s kinda addicting.

Problem 14 is about the Collatz Conjecture, which just so happens to be the subject of a recent xkcd comic:

But there’s nothing special about the sequence when solving this problem, really.  I did learn a neat trick after solving this problem: normally to check if a number was even, I would just look at its modulus of 2—if it’s 0 then it’s even.  But there’s a faster way to do it: do a bitwise ‘and’ with the number and 1, if the result is 0 then it’s even (and bitwise operations are certainly faster than division operations).  This trick isn’t exactly obvious to the code reader, so I put it into the MathHelper class as an “IsEven” method.

p>Problem 15 is about finding all possible paths through a grid.  I struggled a bit with this one.  I tried a recursive solution, but the answer never seemed to be right.  I kept getting this nagging feeling that there’s some pattern that I was missing, so I Googled about it and discovered that you can actually take Pascal’s triangle, turn it sideways, and lay it directly over a grid.  The corresponding corner value is the answer.  So, once again, I put a PascalTriangle method into MathHelper.

Problem 16 is yet another problem that’s easy to solve with a BigInteger class.  Performing an exponential operation on it is just like with regular numbers: using a “shift” operator is faster than performing actual multiplication.  Then it’s just a matter of going through every digit and getting the sum.

And finally, problem 17, which was fun.  I again tried a recursive solution, and then it was just a matter of defining the minimum amount of rules (one – nineteen, twenty, thirty, … ninety, and one thousand).  Writing tests made this problem a breeze.

That’s all for now.  Remember, you can check out the source code at CodePlex.  Also, check out my nifty new WinForms UI for running the tests.

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.

Just a quick Project Euler update.  Number 8 was pretty straightforward, I just went through and got each product and then found the max.  For Number 9, I created a Triplet class with an IsPythagorean method.  I then use three loops (nested) to go start from 1 and go up to a given n.  It’s not entirely brute force, because the 2nd number must be greater than the 1st, and the 3rd number can be calculated using the Pythagorean theorum.  Then, if that Triplet sums to the given n, I add it to a list, and return that list at the end.  The Triplet with the highest sum is the answer.  Since the problem says there is only one that sums to 1000, I simply return .Single() of the list.

Number 10 was yet another prime-numbers problem.  I used the IsPrime method from before, and simply looped from 1 to a million, and added the primes to a list.  Linq can be used then to sum up the list, and done.

As before, check out all the source on CodePlex.

#5 - What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

I did a slow, brute force algorithm, and a fast algorithm using Euclid's algorithm to get GCD/LCM. The slow method is to simply start guessing, incrementally, and seeing if the guess modulus of 1-20 is 0. The second method requires you to know that the least common multiple (LCM) of x,y,z is the same thing as LCM(x,LCM(y,z)). The LCM function is transitive (or whatever, I'm not a math guy). Therefore, you just loop from 2 to 20, and get the accumulative LCM. The LCM function can be written to be dependent on the greatest common denominator (GCD) function, which can be implemented efficiently using Euclid's algorithm.

At this point, I created a "MathHelper" static class to hold methods like GCD and LCM for future use (for Project Euler or otherwise).

#6 - Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

I wrote two methods: SumOfTheSquaresForNumbers1Through(n) and SquareOfTheSumForNumbers1Through(n), both implemented in a very straightforward way--no surprises or anything fancy here. Works very efficiently too.

#7 - What is the 10001st prime number?

I got in a bit of a rush here for some reason, so I cranked out a very brute force solution, just to "get the answer". I felt hollow right away, and decided to take a break after this problem. I read the solution notes which outlined a more efficient way to test if a number is prime or not. I added this implementation to the MathHelper class. Anyway, this problem made me slow down and rethink why I'm doing these problems: it's not to "just solve them" in some sort of competitive sense, and it's not to learn a bunch of mathy stuff either. The point, for me, is to practice my programming, test my own skills, and maybe learn new ways to think about program/method design.

Well, that's all for now. As always, check out the latest source at codeplex, which will almost surely be farther ahead than my blog.

I've finished some more Project Euler problems. Here's some notes:

Problem 3. So, I finally had to break down and write some unit tests for this one. I also had to brush up on what 'prime factors' are, because it's not exactly something I use every day. My solution involved recursion: find the lowest number that divides evenly, divide by it, and repeat using the dividend. If that number is ever itself, it's prime, which is an ending condition for the recursion.

At this point, I also refactored the structure of the project code. Each problem will still be in its own class, but each of those classes implements a common interface. This way, I can simply loop through all solved problems and output the answer without having to repeat formatting and stuff like that.

Problem 4. This one was fun, because it involves palindromes! I again used unit tests, because I knew I would have to watch out for off-by-one errors. I also created a string extension method to reverse the string. I could have created a "IsPalindrome" extension, but generally speaking, the use of such a method is pretty narrow, and thus doesn't really fit as an extension method. My first approach to this problem was to gradually reduce two integers from 999 on down until I got a palindrome from the product. This turned out to not work as expected, and I ended up with a brute force O(n²) algorithm instead. It runs pretty fast, but if the problem called for 4,5,6,etc digit numbers, it would start to get really slow.

As before, you can check out my ongoing source code on CodePlex.com.

Project Euler is an ongoing series of math/programming problems. I'm going to try to go through as many of these as I can this year, post the code for them, and talk about anything interesting that I learn in the process.

You can follow my progress by checking out a CodePlex repository for Project Euler that I've set up. If you have a Project Euler account, you should be able to see my progress on the mgroves Project Euler profile page.

The first problem was pretty easy: "Find the sum of all the multiples of 3 or 5 below 1000." To do this, I just loop through each number from 3 to 999, and take the modulus 3 and 5 of that number. If either modulus is 0, add it to a list. When done, sum up the list:

            for (int i = 3; i < x; i++)
            {
                if (((i%3) == 0) || ((i%5 == 0)))
                {
                    list.Add(i);
                }
            }

The second problem is slightly more difficult: Find the sum of all even numbers in the Fibbonaci sequence which do not exceed 4,000,000. My code takes a straightforward approach; I'm sure the math majors out there can think of a better way:

        public static IList FibonacciAllEvenValueTermsLessThan(int x)
        {
            var list = new List();
            int term1 = 1;
            int term2 = 2;
            list.Add(term2);
            while(term2 < x)
            {
                var newterm1 = term2;
                var newterm2 = term1 + term2;
                if((newterm2 % 2) == 0)
                {
                    list.Add(newterm2);
                }
                term1 = newterm1;
                term2 = newterm2;
            }
            return list;
        }

For both problems, I take the result and use the Linq Sum() extension method, because I'm a total Linq junky these days. I also started out using longs instead of ints, before I realized that, hey, 32-bit numbers go up to around 4 billion (2³²), not 4 million.