How to solve Project Euler problems

I commented before on what I consider one of the best resources to learn programming: Project Euler (PE).

In this post, I will share my recommendations to solve PE problems based on my experience after solving 100+ problems on the site.

Who could this be useful for?

I’m new to programming and don’t have special knowledge in mathematics. That means these recommendations will be best suited for people in a similar situation. My only resource to give these recommendations is the experience I’ve gained after solving problems on PE for about 6 months.

While I offer no magic recipe to solve PE problems, I hope these recommendations can be useful to other people. First, to avoid some common pitfalls (at least in my experience), but most importantly as a motivation to keep on solving PE problems despite how difficult some of them may seem at first glance.

Moving on with the recommendations.

0. Not a place to learn syntax

Firstly, I wouldn’t recommend PE for people who want to learn their first programming language. Instead, I’d recommend starting on a coding challenge site better suited for beginners first (something like edabit). Once you feel comfortable with the fundamentals (control flow statements, data structures, recursion), Project Euler is a great place to continue learning.

I experienced this myself when I started learning Python. After feeling comfortable with the basics of it (which I learned here), PE was a great resource to master what I was just starting to learn.

1. Read the problem statement

As evident as this may seem, be sure to completely understand what’s being asked in the problem before you attempt to solve it. This is particularly important for harder PE problems that have long statements and will require several re-reads before understanding what’s being asked.

On more than one occasion, I attempted to solve a problem without completely understanding it only to realize after several wrong attempts that I was trying to calculate something different!

2. Code on paper first

As tempting as it may be to jump straight into your code editor, you will obtain better results by scribbling a solution on analog mediums (paper, whiteboard) first. On one hand, when writing on paper, you don’t need to worry about programming syntax. You can start planning your solution in pseudo-code or plain math equations to focus just on the essence of the solution.

The second advantage is that you will write clearer and less buggy code if you have a clear structure beforehand. It’s a great win in the long-run.

On several occasions, I started coding to soon, having only a vague idea of what needed to be coded. More often than not, I produced buggy code that required a lot of refactoring to get a solution. Sometimes, I was even forced to erase it all and start from scratch on paper.

3. If it’s taking too long, refactor

Many problems on PE are in the form: Find X such that Y. With X being a number, a probability, etc, and Y a condition. For this kind of problem, the easiest approach is usually to iterate over all possible values of X until finding one that satisfies Y.

While there’s nothing wrong with this approach, keep in mind that many PE problems have been designed in such a way that iterating over all possibilities would take too long. Instead, try refining your conditions first to reduce the possibilities that need to be checked. Also, try optimizing your algorithm to avoid redundant or unnecessary calculations.

As a rule of thumb, if it’s taking more than a few minutes, it’s worthwhile studying different approaches or optimizing your algorithm first.

Personally, sometimes I just waited for a non-optimal algorithm to compute. Some of my solutions took hours. But in other situations, this wasn’t even an option, the algorithm wasn’t getting even close to the answer. Or maybe I just wanted a more intelligent approach. It feels very rewarding when you’re able to optimize your algorithm dramatically or you come up with a new idea that yields results efficiently. It’s one of the great opportunities that PE grants to learn programming.

4. Sometimes it’s not you, it’s maths

Project Euler isn’t named after one of the greatest mathematicians of all time for nothing. While PE is about coding, it’s no less about maths. Many of the problems on the site can be solved much easier by exploiting particular mathematical properties.

For instance, once I was struggling with finding the number of possible partitions for a given quantity of coins. While I was able to think of an algorithm to calculate it, my solution wasn’t efficient enough to get an answer. After some research on the underlying mathematical property in play for that problem, I found out that Euler (yes, the mathematician) had found out a handy recursive relation for that phenomenon. With that equation in hand, programming a solution was trivial.

So don’t feel defeated or cheating when you look for mathematical properties to help you solve some particular problems. In fact, I believe this is intended on PE. As far as I know, many of the problems are even submitted by mathematicians. They might have had those special properties in mind when they created that problem.

In my experience, Wikipedia is a great starting point when I need to do some math research for a problem. You can also look for similar problems in Math’s StackExchange. If everything else fails, you can ask for help on the math’s StackExchange. Just be sure to properly document your problem and how are you approaching it.

5. Floating-point arithmetic

I remember once that I was 100% sure about having programmed a correct solution. Yet when I submitted the answer on the site, it was incorrect. I couldn’t find any error at all and the program gave correct answers to test values.

As a final resort, I ended up comparing my answer with online solutions. Then I found out that while my solution was correct for small numbers, as the values increased, rounding effect imprecisions that were normally insignificant accumulated to yield wrong results. After changing the program to counter the loss of precision for larger numbers, I finally got the correct answer.

While this might be commonplace in languages such as C, I thought that Python’s dynamic typing took care of those problems by itself. But don’t be so sure. For Python, there’s a special numeric type when you need extra precision: Decimal. Be especially wary when dealing with very large numbers or long decimal sequences.

For an explanation on the reasons behind this errors, you can see this guide.

6. Patience makes genius

One of the greatest mathematical problems of all time is Fermat’s Theorem. Ever since it was first postulated, during the 17th century, it captivated mathematician’s minds. Despite its appeal and its apparent simplicity, it was not until the end of the 20th century that it was finally proved by Andrew Wiles.

Solving this problem took Wiles 7 years. He described his resolution process as a series of states where he passed from having no clue about what to do, followed by more and more clarity, to finally understanding. But then a new state of being clueless followed to repeat the process again. He described it as “exploring a whole mansion where each room was initially completely dark”. When a “room” was finally explored and he could see in it, he proceeded to the next room to find it pitch dark again.

Similarly, I’ve found myself in front of a blank piece of paper without any idea to solve a problem. Or even reading and reading the statement of a problem without being able to understand it. That’s all right. The important part is being able to persist through that state and keep trying. Little by little, vague ideas to solve the problem will arise until, eventually, you are able to see it clearly. Just have patience and perseverance.

7. Take a break

If everything else fails and you feel completely stuck, just take a break. You will come back with new and fresh ideas. At the same time, you can come up with great ideas just by distancing yourself from the problem. It’s like the problem becoming a background process that your brain continues to assimilate while you’re doing something else. Sometimes the solution will suddenly pop in your brain while you’re washing the dishes or just relaxing.