I first started Project Euler in June of 2009. It's 2 yrs 9 months, the age of my son, when I finally completed all the problems available on Project Euler. After my "I Am Legend" with holes and Twenty20 articles, it's due for a new article. In this, I am going to talk about my journey to the last mile to get to 100% along with other details related to the Project Euler website.
On Fastest Solvers
Project Euler started tracking the 20 fastest solvers of each problem starting Problem 277. As a few of us felt that it's too few to track, it has been extended to 50 solvers starting Problem 304. As much as I enjoy solving these problems, I also like to pour over all the publicly available data on Project Euler. For example, Problem 338 is the one that took the longest number of days to reach 50 solvers (74 days, 21 hours, 54 minutes, 26 seconds). Based on all that data I looked at, I think there are about 10 people who probably can solve any given problem in less than a day often in just a few hours if the problem is complex and minutes otherwise. Most of the others, including myself, while are able to eventually crack the problems (remember, when Veterans was introduced it was mentioned that it's no longer about quantity since anyone who solved 300 problems would be able to solve them all), they seem to do well in certain type of problems over the others.
On Problem Categories
The problems on Project Euler mostly belong to the following categories
Number Theory (most common category)
Probability
Trigonometry
Combinatorics
Game Theory (introduced after the first 300 problems)
Other topics encountered in computer science and other advanced studies
It should be noted that even problems that are not related to number theory sometime require some insight into
manipulating numbers to solve the problems. Based on the time it took me to solve the problems it was clear to me
that I did well on the number theory problems.
On the redesigned website (2011)
I think the introduction of Veterans in 2010 was just temporary to fix a problem related to cheating. The 2011
season ended with Problem 344, which is among one of the toughest problems. At the beginning of the 2011 - 2012
season, the website was redesigned and Colin Hughes who started and maintains the website has done an awesome job.
The levels now are for every 25 problems instead of 50 except for the latest (highest at any moment) level which is for 50 problems.
Also, a new awards system has been introduced with a total of 21 awards. I already had 19 awards when this system was introduced. Missing were the Perfection award (completing all problems) and Gold Medal (being the 1st for any problem). At present there are more with Perfection award than with Gold medal award. However, I wonder if in the long run Perfection award is going to be more difficult than the Gold medal award.
Perfection Award
Project Euler publishes one problem every week. Occasionally two a week and very rarely multiple problems. So, every year, there are likely to be more than 52 problems. However, there is a summer break for a few months. As a result, each year, there are about 50 problems. When I joined Project Euler there were 250 problems. Right now there are 376 problems. One of the awards is called Perfection award and is given to those who complete all the problems at least once. I say at least once because, if someone completes 100% and then stops, that person still has the award even if there are newer problems which haven't been solved. As these problems are not easy to solve, I would say there are probably less than 50 people who got the Perfection award. In fact, as of this writing, there are only 12 people who solved all the 376 problems and that's 0.006%
As time passes, it's going to be more difficult for people to get this award as the complexity of the problems is increasing and the sheer volume of problems is going to take a long long time to solve unless a person is exceptionally talented.
On getting the Perfection Award
On last Saturday, just before problem 376 was published, I finally managed to get the Perfection award. I even took a screenshot of the award :). Interestingly, I came to know that exact day that the best batsman of India, Sachin Tendulkar made his 100th century. While what I did is no where close to what he did in terms of probability, I was just happy in my own way that I finally managed to get there. And I was the first Indian to do it!
At one point, I was down to the following ten
163 Cross-hatched triangles
202 Laserbeam
208 Robot Walks
252 Convex Holes
253 Tidying up
270 Cutting Squares
275 Balanced Sculptures
280 Ant and seeds
289 Eulerian Cycles
298 Selective Amnesia
Finally, I was down to the following three
163 Cross-hatched triangles (2)
289 Eulerian Cycles (1)
314 The Mouse on the Moon (3)
It's clear from the above lists on what I am not strong at. That is, solving problems not purely related to number theory.
I will be frank, I hated problem 163 and at one point I even told a few friends that I will probably not be unhappy if I don't ever get to solve it. Till I solved it, I felt that it's a mundane task to carefully list down all the various cases. But once I solved it, as is the case with many other problems, it was all clear. It's time and again that 'Aha' moment but it's easier said than done to get those moments.
When I finally solved problem 314, it's a big surprise to me that my strategy worked and that too without having to do any iterations.
The largest amount of time I spent and code I wrote so far is for Problem 289, the one that got me the Perfection award. I read so much material to solve this problem that in the end, it was my instinct on how to solve it all along that worked out.
Another thing I need to admit is, the introduction of fastest solvers has also made me a bit sloppy in figuring out the best solution. I have violated the one minute rule on a few occasions. For some of them, I probably could not have done any better than that.
Ponder This, That And The Other
The purpose of writing these articles is not just to make a point I did it. A few months back one of the Project Euler member sent me an email. I won't mention who it is (and if he is reading this, hopefully you are fine with me quoting one of your sentences). He said "Your articles was the last key in the chain of changes that contributed for evolving my perspective towards life." That was really touching to me. I replied back "I am honored and humbled that my little diary of articles have touched someone's life in a positive way."
As my son is growing up, I see his learning process and it's very interesting. He was able to read and write English alphabet before he was two and half years! But when I tried to teach him to do addition, that's a different story :).
I am interested not just in thinking but the thought process. What makes a person to be able to deal with complexity, think fast, code fast?
While doing my Masters, I was a teaching assistant for an introduction to programming course which helped me see how various students understand a subject differently even when taught by the same person and I belong to the school of thought that when a student doesn't get it, it's the teacher's fault. There is always a different way to explain and understand a complex topic in a way that one can understand it the best.
Project Euler in some ways is about better understanding a topic. There are times when I would think I understood it enough but realize some shortcoming in my ability to reason when solving a specific problem which forces me to go back to the basics.
After solving so many Project Euler problems, I can quantitatively conclude that I am not fast in solving problems but I can deal with complexity. For example, in the public forum one of the admins gave a set of problems that took long time to fill up the first 50 solvers. I looked at them and found that I happened to be in each and every one of them including Problem 373. I was pleasantly surprised when I saw that.
Advice to other aspiring Project Eulerians
If you live in the US, you would have seen the ad "It's so easy even a caveman can do it". I am no caveman and Project Euler is no easy task. However, I am not a mathematician or a computer science major. I am an Engineer with a lot of interest in Maths growing up. I do have the additional advantage that I learned programming from my 1st year of BTech and I took the Introduction to Algorithms undergrad course while doing Masters.
But frankly, what helped me is my determination, persistence and patience. And the willingness to read complex topics if necessary acquiring knowledge that helped me read those topics. Problem 368 is a best example where from the time it was posted to the time I solved (close to 8 hrs 15 minutes), I read a research paper, understood it to the extent necessary to solve the problem, coded it and submitted the answer. A few years back it would probably have taken more time. This is an opportunity I wouldn't have otherwise got and I have to thank Project Euler administrators and all the people who contribute such exciting and challenging problems.
This is probably going to be my last post related to Project Euler (unless may be if I ever manage to get a Gold medal :)). If anyone is interested in discussing their Project Euler journey, I am all ears as long as I am not asked how to solve a problem or hints to solve a problem. I can be contacted at siva at dirisala dot net.