400 Problems in Four Years

My proudest accomplishment as an undergraduate student is the 400+ Project Euler problems I solved. In this blog post, I will do some data analysis on my progress over time, and talk about how I got to where I am today. In December 2014, I wrote a blog post about reaching my first Project Euler milestone: 200 problems solved. A lot has changed since then, and many of the techniques I used to reach 200 weren't very useful in getting to 400, as the problems became more challenging.


The above plots show my progress over time. The first one simply shows the number of problems solved on a given date, and the second one breaks down my solved problems by difficulty (a recently added feature on Project Euler that tells you how challenging a problem is). I was over halfway done with undergrad when I reached 200 problems solved, so I never really thought I would get to 400 by the time I graduated, especially since the problems became significantly harder and my courses became more time consuming.

I reached a bit of a roadblock around 175-200 problems, and I was solving problems at a much lower rate that I had been accustomed to. My biggest problem at that time was that I was working on all of the problems alone, and I when I got stuck on a particular problem I became demotivated. Recently, I have been working together with other people to solve the harder problems. That is my best advice if you have become stuck in the same way I did on Project Euler. Find some like-minded people that have comparable experience to you, and work together to solve the problems. I often find that when working together with one other person, we can solve a problem that neither of us would have gotten alone (or at least solve it much faster than either of us could do alone).

Many of the solutions to Project Euler problems rely on similar ideas. Here's a list of things that came in very handy when going from 200-400 problems for me. To see how I got from 0-200, you should check out my last blog post on this topic.

• Chinese Remainder Theorem (useful for dealing with problems that ask for answer mod some composite number, among other things)
• State space representation (pretty general, but important nonetheless)
• Finding recurrence relations (many counting problems can be solved with linear recurrence relations)
• Evaluating recurrence relations/efficient matrix exponentiation (there are fast methods for evaluating a recurrence relation for large inputs, as long as you keep track of the value mod some value)
• Solving diophantine equations by looking at divisibility properties (many problems can be reduced to finding positive integer solutions to some equation)
• Sprague Grundy Theorem (for combinatoric game theory problems)
• Inclusion Exclusion Principle (need to be comfortable using it in a variety of non-trivial contexts)
• Setting up Linear Systems (a few problems can be elegantly solved with linear algebra)

These are many of the things that you need to grasp well to solve the harder Project Euler problems. Other than the things I stated above, another piece of advice I have is to learn Haskell. I can often gain a lot of intuition about a particular problem by writing up a quick brute force Haskell program. I do this most often with number theory problems, which are easy to brute force, but hard to find efficient solutions for. With Haskell's expressive language and rich library, I can often write brute force programs in a matter of minutes in Haskell when it would take at least an hour in languages like python and java. Haskell is not the only language that you should learn, though. If you learn a few different languages, you can choose the best language for the problem you are trying to solve. Another final piece of advice I have is that you should learn how to write efficient C code. Many of the problems I solved broke the informal 'one minute rule', which states that all Project Euler problems can (and should?) be solved in under a minute of computation. A non-trivial (although not too large) portion of my solutions take longer than one minute to run. I learned the basics of optimizing C code in my computer architecture class and from one of my friends who does lot's of optimization stuff for his Ph.D. research, and occasionally parallelized my code and fired up an AWS instance when I was in need of more computing resources.

One final thing I want to look at before I conclude this blog post is two memorable problems.  The first two problems that come to mind are Problem 328 and Problem 499 - both of which took over a week to solve.  I remember during each of those weeks, I was obsessing over these problems so much that I lost sleep, got behind on my homework, and couldn't keep the problems out of my mind.  I solved both of these problems before the difficulty rating system was added to the website, but it turns out these problems have a difficulty rating of 95% and 100% respectively -- the two hardest problems I've solved.  Now that every archived problem is labeled with a difficulty, I tend to stay away from problems that have a difficulty rating above 80% since I don't think I can afford to go through another week like that again, although every once in a while I will try if I'm working with another person.

Anyway, that's all I have for this blog post.  Hopefully you can use my advice to solve more Project Euler problems.  Otherwise, I hope you enjoy the nice animation I created showing my progress over time.