Twenty20

published: 2011/07/09. tags: project euler, fastest solvers

Twenty20

It's always possible to learn something new

It's been a little over two years since I started Project Euler. Along the way, I reached the current highest level, Veterans. I already wrote about my experience of reaching the Legend level sometime back. At the time I reached the Legend status, I had about 30 or so unsolved problems. By the time I reached the Veterans, that number has reduced further down to 12. The latest season (2010-2011) just ended at 344 problems, I only have one unsolved problem for the season and a total of 6.

The purpose of this article is to go over my journey further since I touched that 250 to reach the Legend status.

On the Veterans Level

Unlike the previous levels, the Veterans level focuses on speed. After a person reaches this level, it is no longer about quantity but speed. It is assumed that a person who managed to reach this level can more or less solve all the problems eventually. So, the members in this group are differentiated based on speed. The first 20 solvers are tracked and listed for each problem. Also, the veterans are listed based on their date of registration and not based on when they became veterans or their name. Part of the reason for changing it to this model is to discourage cheating. I think for some people it is so important they are in par or above their friends that they would do whatever it takes to show 100%. But for Veterans, it's no longer possible to see how many problems they actually completed. It's possible to only know that they completed at least 300. Because of this, even the profile page has been made private. So, why exactly all these types of changes done for the latest level? It is to discourage cheating.

On cheating on Project Euler

What exactly is considered cheating? Some one asked this question in the forum and also there is a poll. It may sound like a stupid question but actually not. For example,

Is using a programming language that has many built-in libraries considered cheating? May be because you used a built in prime number generator instead of writing on your own.
Is learning something from the private forums that helps solve a previously unsolved problem considered cheating?
Is looking up the web for relevant theory considered cheating?

If any of them is considered cheating, I did a fair share of it. I was 2nd for Problem 304 because I used PARI/GP and it's built-in functions. I managed to solve Problem 258 based on a private forum post in Problem 304. I did a lot of online research for Problem 341 and Problem 344.

Is collaborating with others to solve considered cheating?

Actually some people want to collaborate to solve these problems. This is understandable, a lot of complex projects in real life (software or otherwise) are achieved by collaboration. But at the same time, the type of complexity in Project Euler is different. Surprisingly, the length of the code to solve the problem itself is never really large. Most of them can be solved with 100 lines of C code and rarely more than a few hundred. So, the complexity is really to do with understanding of the basic concepts and applying them in the right way. Take Problem 344 for example. One would realize after solving, that it's a combination of similar problems for which solutions are available online and a bit of clever dynamic programming. The later part, once figured out, is not really complex in terms of the number of lines of code. But if this part is collaborated and the answer is obtained, then IMHO the real thrill of solving it is lost. But if one were to say that it's worth it as it helps one learn something complex. Fine, as long as the person doesn't submit the answer and increase the solved problems count. But the problem for some is that they want to access the private forums which are accessible only when a problem's answer is submitted.

I think rather than worrying about who is cheating and not, it's better for each person to focus on what they want out of Project Euler. For me, I like Project Euler because

The problems are as precise as can be framed with diagrams and examples where appropriate. I wish IBM's Ponder This did the same.
I get to see the discussions of the great minds in the private forums.
It's one thing that's completely in my hand. Unlike at work or real life where there is always this complaint about "it's not in my hands" or "if I were incharge of this", when solving the problems on Project Euler, each of us do have complete control on how far we want to go.
Always learn something new. I didn't know about Combinatorial Game Theory.

On Speed

I admit I am not one of those few people on Project Euler who can solve any problem that comes along their way. There are a few people who solved two completely unrelated problems that came on the same day in under 30 minutes while I struggled to solve them even after a few days. There are a few reasons why I usually am not in the top 20.

Time of the problem. The problems usually start Saturday morning 5am PST and subsequent weeks they move by 3 hrs. As I am not an early bird, I definitely miss out 5 and 8 am PST problems.
Toddler son. For the 11am, 5pm and 8pm problems, it usually depends on whether my son wants me to work on the computer or wants me to play with him. If he takes his afternoon nap, I can work on the 2pm PST problem or the other problems that were posted earlier. So, 11pm and 2am PST problems are the only ones that are ideal for me. Though sometimes I am too sleepy to work on the 2am problem.
Boundary conditions. As you can see, I am shamelessly putting the blame on my son :). The reality is I am simply not cut to solve problems fast. I mess up all those boundary conditions.
Background. I have an Engineering background with a strong emphasis on software. I don't have a formal computer science background and my math is limited to what I learned till 12th grade and the first 2 yrs of Engineering. So, I usually don't sit and try to do a rigorous analysis unless it's really really required.
Verbose. My code tends to be too verbose and I try to write code as if I am building a large framework with several unit tests along the way.

Inspite of all the valid and lame reasons I gave above, I did manage to be in the top 20 a few times. This happens mostly for those few problems that don't get solved by 20 people in the first 1 day. For example, Problem 328 took me 3 days, 10 hours, 32 minutes and 24 seconds and I still managed to be the 17th person to solve it. It's really frustrating sometimes when I miss out to be in the top 20 by just a few submissions especially for tough problems. This happened multiple times for me and I felt the pinch mostly for Problem 331 (22nd I think) and Problem 344 (23rd). As per the public forums, they are supposed to track more than top 20 people in the future. But what should be that number? In my opinion, it should not be a fixed number, but depend on the complexity of the problem. For problems where there are more than 50 solutions within a day, tracking more than 20 doesn't really matter. But if it takes a few days to fill up the top 20, then perhaps going even up to top 50 may be good.

On Yet Another Speed

One of the goals when solving the Project Euler problems is to come up with a solution, not just fast, but that runs fast. I noticed that ever since the Veterans level has been introduced and the emphasis was given to the first 20 solvers, there have been submissions where the solutions were sub-optimal. Just to be clear, these people who submitted such solutions are actually very capable. But because of the race to be in the top 20 fastest solvers, they first provide the answer and sometimes go back and optimize or come up with an even clever solution.

The emphasis on the speed of the program has always been there. It's expected that the programs typically take no more than 1 minute to solve the problem. Of course, which programming language is used has a definite impact. Also, though the goal is to do it within a minute, there are times I come up with a solution for a complex problem that runs in a few seconds in a -O3 optimized C++ code only to find a sub-second solution even in an interpreted language. It makes me wonder that all those benchmarking that are published comparing programming languages is almost useless since time and again I have noticed that a very clever algorithm outsmarting the heavily optimized executable by a large difference. I must admit, I make use of the convenience of PARI/GP usually for number theory related problems and matrix operations and as a result end up with solutions that sometimes don't meet the one minute rule. I am fine with this because I kind of know that the underlying algorithm is very good and if implemented in a different programming language it would run fast (Problem 280, for example was done in PARI/GP and slow).

On Twenty20

If there are only 20 fastest solvers, then why am I calling this article Twenty20? Yeah, I am a cricket fan, but that's not the reason for calling this Twenty20. While the number of problems solved is no longer available for Veterans, the distribution of how many people solved how many problems is available in the public forum posted periodically. I was the 94th person to reach the Veterans level and at that time I still had 12 unsolved problems. At present the count is down to 6 unsolved problems for me. Also, the difficulty of some of the problems in this season seems to be lot more than the previous problems. As a result, based on the distribution of solvers, at the end of the latest season, I am in the top 20 people. So, while I barely manage to be in to top 20 for speed, I seem to be in the top 20 based on the total number of problems solved. But probably this is not accurate because

Some very smart people suddenly seem to stop working on Project Euler
Some smart students may be busy with studies and exams
Not everyone has the desire to solve the problems all the time. I am sure there is life outside spending time on this wonderful project that suddenly takes precedence

Ponder That

Tackling more complex problems definitely increases confidence helping to solve or at least not to despair even more complex problems.
Even for Veterans, there is always something new to learn. Based on the initial problems for the season (300 to 310) I learned Combinatorial Game Theory.
Solving complex problems makes one understand a subject even better. For example, I have solved a few problems without really digging deep into Marcov Chains. But finally when I had to solve a specific Problem in the last season, that really got me into learning a lot about this subject. Similarly, just when I thought I learned a new theory based on the initial set of problems, the last problem for the season, Problem 344, really stumped me forcing me to go back and read all the related subject material once more.
Some people are a notch above. I think probably about 10 people or so on Project Euler are clearly a notch above all of us. Even though I get to share the same Veteran level with them, without any hesitation I can say that a few individuals are much more fast, smart, knowledgeable and intellegent than others. There were cases where it took me days to solve one of the two problems that came at the same time while there were a few who solved both those problems in less than half an hour! Similarly, there was one person who managed to score 200+ points on the Eulerians section which I think is outstanding. Then there are a few who are in their mid-teens and are probably smarter than many other experienced veterans.

Personal Benefits

Here are some of the benefits that I got along the journey for the last two levels

More and more confidence. When I started off on Project Euler, I wasn't sure I would reach Legends level because my academic background wasn't either computer science or mathematics. However, since I have been exposed to programming since 1991 and I had the pleasure of taking Introduction To Algorithms at MIT during my graduate studies, I do have some relevant background. So, as I put in more time thinking about these problems in solving them, my knowledge and confidence certainly have increased.
Some people think and act as if they are the smartest people in the world based on what they work on. But now I can tell with confidence, it's not what a person is working on but what the person can really work on that determines.
Determination and concentration. Even prior to working on Project Euler, I did have a lot of determination and concentration when required. Project Euler gives a chance to put those into practice more often.