9 Dec 2009

Project Euler. A good distraction!




I am currently taking a break from coding the game. I have reached a point where my lack of artwork, sound FX, music is impacting development. In the new year my artist finishes her MA in animation and will commence providing me with concept designs and sprites to work with. So fear not! My commitment has not waned at all.

I realised that I needed some bite-sized programming projects to work on. I needed something fun and challenging to sink my teeth into. This is when I remembered the brilliant website http://projecteuler.net.

Project Euler is a website that contains a number of maths problems that can be solved via programming. So far I have solved 10 of the 267 problems. In doing so, it has reminded me how badly I suck at mathematics. Luckily I am focused and never give up until I have figured something out even if that takes me a lot longer than most.

Yesterday I solved problem 5.

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

### SPOILER ALERT ###
I will now explain how I solved it using Python. If you don't want to know the answer and wish to solve it yourself stop reading now. Do come back when you have finished it just to compare notes though.

First we need to define a win condition.

def checkFactors(value, factors):
    """Returns True if value is evenly divisible
by all numbers within factors.
"""
    if value == 0: ## Because 0 divided by any number in Python returns 0.
        return False
    for n in factors:
        if value%n != 0:
            return False
        elif value%n == 0:
            pass
    return True

All well and good, but we still need a way to pass values to the checkFactors function until we find the correct answer. The first step we could take is a brute force approach as outlined below:


def bruteForce(factors):
    answer = factors[-1]
    while True:
        divisible = []
        for number in factors:
            if checkFactors(answer, factors):
                return answer
        answer += 1


This technique works quite well for the example given in the problem. For the range 1-20 however it takes ages. I left it running, boiled the kettle, made coffee, had a chat with my girlfriend's dad about the paper and it still hadn't finished. Clearly there is room for improvement.

We can speed it up by increasing the variable answer by the maximum value in factors each round of the loop. We know that the number we are looking for has to be divisible by 20. So we can eliminate the next 19 possible values straight away.

def bruteForce(factors):
    answer = 0
    increase = factors[-1]
    while True:
        if checkFactors(answer, factors):
            return answer
        answer += increase

I timed this method and it took Python just over 38 seconds on my dual-core laptop with 2GB of RAM. While 38 seconds falls within the one minute rule of Project Euler I still thought that there must be a faster way. Not only does the number we are looking for have to be divisible by 20, it also has to be divisible by 19 as well. 19 multiplied by 20 equals 380. So we can be even faster by increasing answer by 380 on each iteration of the loop. We can amend the function like so:




def bruteForce(factors):
    answer = 0
    increase = factors[-1] * factors[-2]
    while True:
        if checkFactors(answer, factors):
            return answer
        answer += increase



This time around it only took just under 2 seconds to produce the correct answer. However it occurred to me that for each iteration of the while loop the checkFactors function has to iterate over 20 different values and that a lot of the checks are actually redundant, because some of the numbers in the range 1-20 are factors of other numbers already within the range. For example:

2 is a multiple of 20
4 is a multiple of 20
5 is a multiple of 20
10 is a multiple of 20

If the value being passed to checkFactors is evenly divisible by 20 it is also evenly divisible by 2, 4, 5 or 10 so we don't need to check them. What we need is another function.

def findUniqueFactors(factors):
    ufactors = list(n for n in factors)
    for n1 in factors:
        for n2 in factors:
            if n1 == n2:
                pass
            elif n1%n2 == 0:
                if n2 in ufactors:
                    ufactors.remove(n2)
    return ufactors

When we call this function with the variable twenty the ouput in the interpreter is the following.

>>>twenty = range(1,21)
>>>uTwenty = findUniqueFactors(twenty)
>>>print uTwenty
[11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
>>>len(uTwenty)
10

That means we have halved the number of values we need to check for each loop. So, lets put it all together!

def checkFactors(value, factors):
    """Returns True if value is evenly divisible
by all numbers within factors.
"""
    if value == 0: ## Because 0 divided by any number in Python returns 0.
        return False
    for in factors:
        if value%n != 0:
            return False
        elif value%n == 0:
            pass
    return True


def bruteForce(factors):
    answer = 0
    increase = factors[-1] * factors[-2]
    while True:
        if checkFactors(answer, factors):
            return answer
        answer += increase


def findUniqueFactors(factors):
    ufactors = list(n for in factors)
    for n1 in factors:
        for n2 in factors:
            if n1 == n2:
                pass
            elif n1%n2 == 0:
                if n2 in ufactors:
                    ufactors.remove(n2)
    return ufactors


twenty = range(1,21)
answer = bruteForce(findUniqueFactors(twenty))
print answer

When I timed this final version, Python found the correct answer in about half a second! While there still exist faster methods. I am more than happy to move on to the next challenge.




2 comments:

  1. Even though I don't understand it enough to discuss in parallel maybe you can do a non programmer friendly presentation of your research and discoveries.

    I also felt guilty about the reasons for stopping the shooter, wish I had more time dude.

    ReplyDelete
  2. Wow.. im still on the basic basics, i gues i have a long way to go until i can understand what you wrote there..
    Chat to you lata bro.

    Peace

    Chris

    ReplyDelete