Published Tuesday 8. April 2014If you have looked at my book log recently, you may have noticed a drastic drop in the number of books I have been reading starting mid-2012. There are two reasons for this, one of them being Project Euler.
Project Euler is a math/programming puzzle web site. I can't remember where I read about it first — perhaps it was in an article on Slashdot? (Edit: Actually, yes, I think it was in this article — which also nails down the date I joined Project Euler: The 3rd of October 2012.) Anyway, the idea is this: Every weekend (more or less) a new problem is published. The problem is usually mathematical in nature, but almost always requires some programming to solve. When you have found the correct answer to the problem (most of the time in the form of a number), you submit it to the site and gain access to a forum where you can discuss the problem and the solution. I have always been interested in math and programming, so I got hooked right away. At first it was easy: The early problems are simple, and even if you can't find the best algorithm, you can just brute-force the result and gain access to the problem forum, where you can read about better ways to solve the puzzle. For the later problems, this is rarely possible. You must find a good algorithm, or forever stay locked out of the forum, which can be very frustrating if you just must know how to solve a particular puzzle.
The first problem where I got stuck was problem 143: "Investigating the Torricelli point of a triangle". I never really appreciated geometry — I have always been of the opinion that geometry problems can be reduced to algebra/calculus problems (which may or may not be true, but I acknowledge that some problems are easier to solve using geometry), so geometry never interested me. At first, I skipped many of the geometry problems at Project Euler, but at some point I revisited them and noticed that they were all just hidden algebra / number theory problems, which I find much more interesting. This is a general theme in the puzzles; the problem as described is often a "cover" for an underlying problem — usually in number theory or combinatorics, two of my favorite subjects in mathematics.
I have been stuck in many other problems, but when I return to a problem that I have not thought about for a while, I often find that I can look at it in a new way, and get new ideas for how to proceed.
I have learned a lot from the puzzles; I have learned about new data structures, new algorithms, new math. Either by figuring it out myself, or by reading about it on the net — researching a problem online is encouraged, as long as you don't just copy a solution found elsewhere. Some of the methods/subjects that I have discovered (or rediscovered) in my research for the puzzles are:
- The Euler phi function (of course)
- The Möbius function and the Möbius inversion formula
- Pythagorean triples
- Fast matrix exponentiation
- The inclusion-exclusion principle
- Parametrization of Diophantine equations
- Finite State Machines
- Game theory / Nimbers / The Sprague–Grundy theorem
- The Union-Find data structure
- Fenwick trees
- The Hook length formula
I can't tell you how much time I have spent on Project Euler in total, but it's measured in weeks rather than hours. Why spend money on books and movies when you can get literally weeks of entertainment for free? I realize that Project Euler is not what everybody would call entertainment, but for me it's better than movies. Even though I work as a programmer, I don't get many assignments that challenge me in the way that the puzzles of Project Euler do, so I guess it's also a way of keeping my math skills sharp.
Here is my Project Euler badge:
Oh, and in case you are wondering: The other reason — and probably the main one — for the drop in the number of books I have been reading is that I met my girlfriend (Edit: She is now my wife, since the 4th of July 2015) in June 2012.