Alecs' Blog Did you ever go clear..

All Project Euler Problems Solved

Project Euler continues to be fun. First reached 100% when there were 240 problems. And have successfully guarded that honor since =). (As of this writing, there are now 245 problems). Well, not that easy. Recent problems tend to be more difficult IMNSHO. In the process, you learn new stuff, refresh your old knowledge and gradually become a better problem-solver.

In the no-spoiler tradition of Project Euler (oh, they say "If you cant solve it, you cant solve it. Dont ask."), i would not disclose any direct answer or code. Instead, I'd love to share some of my experience and give some general advice for newcomers:

  1. Learn maths. You dont have to be a mathematician to solve Project Euler problems but the more math knowledge you have, the easier it would be. And in fact, the math required is not that 'deep' since Project Euler is not a pure math puzzle. It's more like a programming challenge based on some math background. So other than depth, try broadening the breadth of your math knowledge. Get interested in more math topics and learn to appreciate the beauty of the diverse math world. What Is Mathematics is a very good book to read. And btw, seems Project Euler devs more like these 3 fields than others: Number Theory, Combinatorics and Probability.

  2. Learn algorithms. If judged only by the algorithms required, Project Euler problems are not as difficult as ACM/ICPC problems. Dynamic Programming might be Project Euler's favorite algorithm. Graph algorithms like bfs, dfs or shortest path are also good to know. And whats more important, learn algorithm runtime-and-space analysis. IOW, have a good estimate on how long your code will run and how much memory it will consume.

  3. Know your tools/langs and sharpen your coding skills. Some problems can be easier solved by using a particular lib or programming language than other. Some heavy brute force might need you to cut the cost as much as possible. Better some knowledge of a few different langs (procedure, object, functional, script, etc.) with 1 or 2 very-good-at.

  4. Dont fear the problems. "Only Thing We Have to Fear Is Fear Itself". There's no fun if the problems are not difficult. And different ppl have different knowledge backgrounds and expertise. So a problem easy for others might look very difficult to you. Learn the new math on-the-road. Often than not, there's a mention of the needed math background in the problem description. You can search and study it. And sometimes, there is no such magic or elegant solution at all. Please dont be a perfectionist and never be shy to get your hands dirty to try on small cases. You'll find some patterns that'd enlighten you very much.

  5. Think outside the box. If you get stuck, try thinking of another different approach, sometimes totally different. Try to view the problem in other perspective. Be open-minded and learn to be 'creative' and 'smart'. Hints: some geometry problems in fact turn out not to be geometric at all. Cut all tedious lines, circles, sine and cosine; think of abstract combinatoric items.

Project Euler problem is a mixture of math, algo and coding. Solving them is a mixture of joy and pain, trail and fail, fun and frustration, love and hate.

Here are all my solutions to Project Euler. Of course, I wont spoil the real fun and you have to solve the problem yourself thus know the answer to see my code, not vice versa. The site is on top of Google app engine and currently very primitive (poor ui but please dont say 'ugly'). I'm not into web dev very much. You can see the code on github.

20 May 2009

Fork me on GitHub