Sunday, June 27, 2010

Project Euler solution # 1

I had an interest in doing some programming puzzles for the usual reasons: to practise and improve my logic skills, to explore new programming languages, and for simply to have...fun. The Python Challenge seemed appropriate when I started learning Python. I enjoyed doing the first few.

I then took a stab at one of the more popular puzzle websites, Project Euler (pronounced oil-er not you-ler which I incorrectly thought it to be.) This site not only encourages identifying efficient algorithms via your programming language of choice to solve the problems but strongly emphasizes math requiring more and more research as you advance to later problems.

Starting off with problem # 1:

Add all the natural numbers below one thousand that are multiples of 3 or 5.

Here is my first run, brute force attempt at the solution using Python:
divisors = [3, 5]
multiples = []
for i in range(1, 1000):
    del multiples[:]
    for divisor in divisors:
        if i % float(divisor) == 0:
            multiples.append(divisor)
    if multiples:
        print i,' is a multiple of ',', '.join([str(multiple) for multiple in multiples])

The earlier code solved the problem but, shortly after churning it out, I discovered that it did not offer the expected format of the answer. Therefore, re-worked the code to do so:
multiples = []
for i in range(1, 1000):
    if i % 3 == 0 or i % 5 == 0:
        multiples.append(i)

print sum(multiples)           

While this returns the correct value of 233168, the structure of the code could have some pythonic polish added to it. A dab of list comprehensions does the job:
print sum([x for x in range(1, 1000) if x % 3 == 0 or x % 5 ==0])

In the spirit of one reason why I'm doing these puzzles, here is a solution in C:
main()
{
  int sumOfMultiples = 0;
  int i;
  for(i = 1; i < 1000; i++)
    {
      if (i % 3 == 0 || i % 5 == 0){
          sumOfMultiples += i;         
      }
    }
  printf ("%i \n", sumOfMultiples);
}   

2 comments:

Unknown said...

I strongly disagree with the second poster. ;)

About a month ago a couple of us went through a few of these problems at lunch time in Ruby, I know I found the experience very enlightening - especially when we got to the point of learning to craft the code as a Ruby-ist would.

Ray Vega said...

I could not decide whether or not I agreed with the 2nd poster (very persuasive arguments!) so the best way to ease my mind was just removed it. :-) Seriously, yours might be the first non-spam comment I've gotten in well over a year. (I'm considering restricting comments since it seems to have gotten progressively worse as of late.)

That's cool you been trying out these problems with Ruby. Hope you had some fun with it.