Project Euler Level 1

I have been interested in puzzles since I was little. After learning programming I would search out puzzles that could be solved by coding. Few years back while I was pursuing my B.Sc. I encountered Project Euler:

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

I got hooked on solving these problems. Sometime along the line I gave up due to exams or some other commitments. Now that I have started learning Python, I was again hunting for puzzles that I could solve with my Python coding skills. This is how I encountered Project Euler for the second time. I managed to pick up from where I had left duing my B.Sc. Today I managed to reach level 1. While its not much of an achievement considering a lot of people before me have successfully done it, but nonetheless it feels great.

I tried to solve most of the problems in Python. But sometimes ended up using good old C. Sometimes I would just use Java or C++ for the rich template libraries that these languages have. Some of the solutions lent themselves to Matlab and (surprise, surprise) Calc (open office version of MS Excel). Only 2 could be solved by analytical reasoning alone.

Lets see how many I can solve. But its great fun to develop a solution and in the process explore some of the unknown language features and libraries.

Feynman's answers to Lateral Thinking puzzles

Late physicist Richard P. Feynman was well known for answering questions in a typical manner unique to him. Here are a few humorous takes on what he would have replied to the so called "lateral thinking" questions that are asked routinely at software company interviews these days.

Here are two examples of the quirky answers that he might have given to these trick questions:

• Why are manhole covers round?
• 3 switches are placed in one room and there are 3 corresponding bulbs. in another. Which switch lights which bulb?

What is amusing is that all the answers are all valid but differs from what the interviewer wants to hear. So the interviewer can neither refute the answers nor be satisfied by them.

A reader gave me this link in which Feynman is answering the question "Why do magnets attract or repel each other?". This is also a classic example of the fact that any fool can ask questions which the wisest man cannot answer.

Algorithm for finding square-root

It always intrigued me how one could find the square-root of a number. In school I was taught a digit-by-digit method to calculate square-root. I did implement it using BASIC in Std IX, but the solution did not seem elegant enough. By Std XI I had actually figured out the Bisection method by myself and used it to find any root of a number. This again was implemented in C++ (... and I still have the code !).

Then in my B.Sc. I was formally introduced to the Newton-Raphson method and I have been using that ever since. At about this time only a classmate told me of the logarithm based method, which (if Wikipedia is to be believed) is the method of choice for most implementation of sqrt().

Recently I have been going through the MIT open course, Structure and Interpretation of Computer Programs. While watching the original 1981 videos, I came across this brilliant algorithm which was supposedly invented by the Babylonians around 2000 years back. It is also often attributed to Heron of Alexandria, who was also a great inventor (the link to his biography in Wikipedia has a section on his inventions ... looks impressive to me).

Heron's Algorithm can be derived from the Newton-Raphson method and can be considered to be a special case of that. The brilliance however lies in the fact that it precedes Newton-Raphson by 1600+ years. The algorithm is very simple:

1. Guess a solution for sqrt(x), say g
2. Check whether the current value of guess is "good enough" (square roots can be irrational, so exact value is often not achievable)
3. If the guess is not "good enough", compute the new guess by updating  g=(g+x/g)/2
4. Go back to step 2

You know from my last post that I have recently been learning Python. So here is a python implementation of the above algorithm.

Once again, please let me know if you find any bugs in the implementation. I am a Python newbie and your suggestions can help me improve.

My first Python program

I heard of Python in my final year of B.Tech. at CU. Since then I have tried many times to pick up the language. Unfortunately most of the efforts have not gone far mostly due to lack of a particular problem to attack.

This time however it went differently. First I came across this brilliant and simple way (Monte Carlo technique for computing Pi) to compute the value of Pi from some CS magazine that I ran across in Dept of CSA [1]. Then I wanted to implement it. Matlab and C would have been the perfect choice for writing this simple code, but I just had enough time for trying it out in Python.

Here is the result of that (after 50mins involving mostly Google and the Python website):


Maybe I could have improved the code a lot had I been an "evolved Python programmer". But I am pretty happy with the initial results that I got. The great thing is that with iteration count 100K or so the program almost always computes upto 3.14 correctly.

[1] Maybe Communications of the ACM, some issue of 2010, however the link given before also explains the same technique

Weird Idea

I have a trolley with small plants.

When I feel mischievous, I often take out the trolley to the verandah. Then I watch it from a distance. After a some bee find the flowers on the small plants. He goes back to the hive to inform the other bees.When he is gone I take the trolley away.

I love watching the swarm of bees coming to my verandah for no reason. I imagine they must be cursing the first bee. I just love embarrassing the first bee.