"I Am Legend" with holes

published: 2010/03/29. tags: puzzles, project euler

"I Am Legend" with holes

"Everything has its beauty, but not everyone sees it." ~ Confucius

On Solving Puzzles

Since childhood, I always had fascination for puzzles. When I was in early teens, I once gave a math puzzle to an adult who I knew could solve it. But instead, he said, "I don't care about these puzzles". I wondered if I would become the same as I grew older. Luckily, I still cherish good puzzles. I do agree that the time one can spend while working and as a father of an infant is definitely not as much as a teenager or a college student can spend. But I think interest, drive and motivation can come a long way to overcome some of the hurdles.

On Project Euler

Someone introduced me to the IBM's "Ponder This" puzzles. Each month a new puzzle is published along with the solution to the previous month's puzzle. So, you only have a month's time to solve it. It's not always possible to solve these puzzles that too within a month's time when there are other things that are important or need immediate attention. Coupled with that, the complexity of some of these puzzles certainly don't permit a person like me to tackle them within a month's time. I noticed that there was one person who had been solving each of these IBM puzzles month after month. When searching about this person, I stumbled upon Project Euler.

As soon as I registered with Project Euler and got familiar with their simple but very elegant user interface, I realized that these problems can be solved at my own pace as there is no pressure about the answers getting disclosed at the end of the month.

Initially I didn't bother to read the "about" page of Project Euler. I just started solving from the first problem and the initial problems were so simple, I used to write command line perl scripts to solve them. Finally I reached a stage where command line scripts were no longer sufficient. Along the way, I read the "about" section and learned that the goal should be to solve these puzzles such that the program runs within a minute.

On Problem Difficulty

I also found that the puzzles can be ordered by either the id (chronological order) or their difficulty where difficulty is reflected based on the number of people who solved a puzzle. Ordering by difficulty is usually not accurate for the most recent problems, but it seems to be fairly accurate for the older problems. It takes about a week or two for the recent problems to stabilize and settle around their final difficulty level, especially so for the real hard problems. Of course, that doesn't mean a person who solved a more difficult problem will solve all other problems that were less difficult than it. This is because, the problems cover various branches of mathematics and computer science. Hence, those familiar with a specific topic can solve that problem more quickly even though overall it might be more difficult. I started sorting them by difficulty and solving in that order.

It took me just 4 days to complete Level 1 by solving 50 puzzles. But I did realize that with each passing level the problems are going to get more and more difficult and I won't be able to solve that many. I expected to reach Level 4 with some hard work.

On the Levels of Knowledge & Intelligence at Project Euler

For those not familiar with Project Euler and it's levels, let me explain. There are essentially 6 Levels. After solving 25 problems, one can enter Level 1. After solving 50, Level 2. Level 3 requires 100 and is considered Novice. Level 4 is Intermediate and requires completing 150. Level 5 is Expert and can be reached after solving 200 problems. Then comes the last and final level (as of this writing) and this 6th Level is called Legend and is bestowed to those who complete 250 problems.

Even though each level has 50 problems (except 1st level), there is a vast difference between a person who just reached a level to a person who is about to move to the next level. The difficulty actually increases with each additional problem solved. However, I didn't find this to be uniform. Instead, I would be pondering on problems for a while, experimenting and having partial success and while they are in the back seat, a sudden flash of genius helps solve them. Perhaps, it's psychological, but solving one such revisited puzzle paves way to solving additional puzzles within a short span.

On Confidence

After reaching Level 2 by solving 50 problems in 4 days, I spent another 3 weeks to complete 50 more puzzles and reached Level 3. I could see that the complexity of the problems increasing. I still used Perl mostly, but moved from command line scripts to scripts written in files. I also started keeping track of my solutions to each puzzle.

At this stage, I felt that I would probably reach Level 4, which is Intermediate and that's it.

I spent another month and reached Level 4 completing a total of 150 problems. Along the way, may be only a few solutions would have violated the 1 minute rule. However, for some problems, I noticed that the difference in execution of a program written in Perl vs C using the same algorithm is as much as a factor of 10. So, for a few cases, I didn't mind violating the 1 minute rule when written in Perl. My reason to pick Perl is that it allows rapid prototyping and data structures are easy with Perl. Java is my most familiar territory. However, my roots are in C/C++. So, after I saw people using STL for data structures, I experimented with them a little bit and started solving puzzles in C++. I found that after reaching Level 4, more problems required a compiled language like C++ to be within the 1 minute rule (only to discover some very clever algorithms in the private forums from some true Legends). I have also seen a few people using PARI/GP and providing very terse code. That's when I started familiarizing PARI/GP myself and now I use either Perl or PARI/GP for quick prototyping and C++ for speed and occasionally Java if I need complex data structures or big integers.

I initially thought I might have to learn a lot to reach higher levels. But I managed to reach Level 4 with very minimal reading. Except for a few concepts like Euler Phi and Fermat's Little Theorem, I managed to solve most problems with my prior knowledge. I now set a goal of Level 5 to feel good that I am an Expert.

On being an Expert

The progress was slow but there. I also started tracking more closely my ranking within the country statistics provided by Project Euler. I remember reaching to the first page for India when I solved just 60+ problems and as of this writing, it requires solving 78 problems to be on the first page (BTW, I had some hard time with Problem 78). Around the time I reached Level 4, I got a private message from a fellow Indian saying that he mostly saw students on Project Euler and not a professional like me. I learned about the private messaging feature and also that I could subscribe so that I get an email notification for each new problem that's being published.

I kept going at it steadily. With the help of PARI/GP I managed to work on the number theory related problems more easily by trying out various algorithms that involve factoring numbers.

Finally, after 2 months and a week, I solved 200 problems and became the so called Expert.

That's it. I realized I had spent more time on Project Euler than I probably should be. I thought I should take a break from it for a few weeks, if not months, and cherish my latest achievement. Besides, it's not like I am going to become a legend, it's reserved only for those less than 150 people who got it. So, why bother? Those were the thoughts that ran in my mind.

On being a Legend

It's hard not to check email for a few weeks. Similarly, it was difficult for me to not check back on Project Euler. Especially after getting the weekly emails about the latest problem. So, I again got dragged into attempting the Project Euler problems. The progress had been even more painfully slow than to reach Level 5. I even got stuck trying to solve just one problem for 10 days (which I refused to put aside), the longest time I spent on a problem till I reached the 5th level. Of course, those 10 days include all my other main activities such as going to work and taking care of our baby.

In about the time I spent reaching Level 5, I could only solve half the number of problems required to reach Level 6. Finally, after 4 months and a week since reaching Level 5, I ended up as a Legend. Part of the reason it becomes easy to reach Level 6 for people like me is that each week a new problem is posted and not all those problems are as complex.

A good friend of mine told and I realized it myself is that I seem to be doing problems related to Number theory more easily than other areas like Probability and Geometry. So, while I am currently in the Legend status, I have my own holes. I hope to fill them up by some day. From the public forums, it appears that the age range of people on Project Euler is from 15/16 yrs to 80s. So, I still have a lot of time :). And age should never be a limitation to gain knowledge, isn't it? To summarize, here is the timeline of my milestones for each level

Reached Level 2 , solving 50 problems, in 4 days
Reached Level 3 , solving 50 more problems (100 total), in 3 more weeks
Reached Level 4 , solving 50 more problems (150 total), in 1 more month
Reached Level 5 , solving 50 more problems (200 total), in 2 more months and a week
Reached Level 6 , solving 50 more problems (250 total), in 4 more months and a week

So, it appears that the difficulty of the problems is exponential (at least for me).

Personal Note: I slept at 1 am on a Friday night after reaching Level 2 and at 3 am my wife woke me up and said "I think my water broke". So, the reason for completing Level 2 in 3 weeks is a combination of complexity and taking care of our days old baby. Otherwise, it would havce been more closer to 2 weeks.

On being a Legend Of the Legends

Right now there is no such level in Project Euler. However, there is a special category called Eulers which is given to people who solved 13 of the latest 25 problems. But with more problems the probability to solve 250 problems will increase. So, either the number of problems should be increased or the number of levels should be increased. If either of them happen or not, I think, there should also be another special category to reflect people who solved all the problems. As of this writing, there are only 39 of such people out of the 160 Legends. There are 168 Eulers.

Ponder This

Yes, it all started with IBM's Ponder This. But this is about pondering my journey to the Legend Level at Project Euler. Here is some advice to others who want to go on this path.

Interest and desire to work on the problems is a pre-requisite
Confidence is very important to enter higher levels
If stuck, move on to something else and revisit it at a later stage (I did this with Problem 241 which helped me reach my Legend status)
Do read the private forums after solving a problem and learn from the true Legends on various approaches they have taken (Concepts in Problem 195 helped me solve Problem 279)
Don't hesitate to search the web for the related research material. While there are some who proved some fundamental concepts themselves and solved the problems, for most of us mortals it's ok to rely on the shoulders of some great Legends. For example, Brahmagupta Identity. However, it's important to distinguish what is acceptable research and what's not. Searching directly for a specific Project Euler problem is not right. But researching for a related topic is ok (Problem 167 and 282 are just a few examples)
Whenever reading a new topic, think for a moment if it can solve any of the problems you have left out in the past. (I managed to solve Problem 192 like this)
Sometimes knowing a particular identity or formula can really help solve a problem. If nothing helps, try to device one yourself from fundamentals. (I did this for Problem 281)
Prototype and solve it for smaller values, identify what's causing the performance bottleneck and find ways to fix that (Problem 223 is one such I did this)
Stop thinking in numbers and visualize it physically if possible (Problems 126 and 148)
Don't forget silly/stupid coding bugs or logic bugs. I had wasted hours on a few problems due to silly mistakes (Problems 250 and 282)
Read the problem again. A few times I thought I knew what the problem asked, but missed out some subtle points
In case there are related problems, understand the right way of solving from the private forums to solve the more advanced problems.(I solved Problem 272 based on the right approach posted in Problem 271)
If everything fails, well, just move on with the hope that one day you can solve it. Don't go about searching for a solution on the web. I have seen some people posting their solutions online as part of their blogs. I hope people stop doing this. I currently have around 30 problems which I haven't solved yet and I hope to find a solution myself. Some I know, it's a matter of having more time, while for the others it's likely I need to learn more concepts or understand the concepts better.

If you want to discuss about your Project Euler experience, you can send me an email.