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);
}