mgroves

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.