Archive

Monthly Archives: August 2011

Hi folks! I know I have been a little bit out of writing something here but today I decided to write something about coding and more particularly Project Euler and the problem 14( http://projecteuler.net/index.php?section=problems&id=14 ).

I’ve found this problem very interesting and since I didn’t had much to do I decided to solve it and make this post.

The biggest challenge of this problem its the magnitude of numbers we are trying to calculate(100000). Those who are familiar with the problem and tried a “brute force” approach to this problem knows that it might take “a while”(A LOT) to finish.

The algorithm of this approach will look something like this:

maximum = 0
max_value = 0
for value in xrange(1, 1000000):
    status = value
    terms = 0
    while status > 1:
        if status % 2 == 0:
            #even
            status = status / 2
        else:
            # odd
            status = status * 3 + 1
        terms += 1
    
    terms += 1
    
    if terms > maximum:
        max_value = value
        maximum = terms
        
print "value: %s   terms: %s" % (max_value, maximum)

Well, don’t even try this because this is will take a lot of time to come out a result.

What we need here to solve this its a simple cache to return the number of terms from values we already know.

So, the iterative way to solve this problem comes like this:

maximum = 0
max_value = 0
SEQUENCE_CACHE = dict()
for value in xrange(1, 1000000):
    status = value
    terms = 0
    while status > 1:
        try:
            terms += SEQUENCE_CACHE[status] - 1 
            break
        except KeyError:
            pass

        if status % 2 == 0:
            #even
            status = status / 2
        else:
            # odd
            status = status * 3 + 1
        terms += 1

    terms += 1
    SEQUENCE_CACHE[value] = terms

    if terms > maximum:
        max_value = value
        maximum = terms 
        
print "value: %s   terms: %s" % (max_value, maximum)

This one will take a few seconds and solve the problem. As you can see SEQUENCE_CACHE will keep track of previous results. Using this kind of cache system will allow to decrease dramatically the number of iterations required to achieve the number of terms of a certain value.   Try it yourself.

 

As I found this problem interesting I decided to do also the recursive solution to it.

So, as before if we try a brute force recursive approach to this problem we will face the same situation, the algorithm will take a lot to finish.

This first and not correct approach will be something like:

def euler14(value, status=None, n=1):
    """
        'value' represents the base value
        'status' represents the actual value according with odd and even forulas
        'n' recursion deepness
    """
    if status is None:
        status = value
 
    if status <= 1:
        return n
    if status % 2 == 0:
        #even
        status = status / 2
    else:
        #odd
        status = status * 3 + 1

    return euler14(value, status, n+1)
terms = 0
value = 0
for x in xrange(0, 1000000):
    result = euler14(x)
    if result > terms:
        value = x
        terms = result

print "value: %s   terms: %s" % (value, terms)

This will take a lot of time to finish because it doesn’t take into account previous known results.

So, once again a cache enters in the play to solve the issue. If you are familiar with cache and python you know that a common use of python decorators are actually for cache and it comes in the form of @decorator_name. Our case is no different so the solution comes like:

SEQUENCE_CACHE = dict()                                                  
def cache_euler14(fn):                                                   
                                                                         
    def kicker(value, status=None, n=None):                              
        try:                                                             
            SEQUENCE_CACHE[value] = n - 1 + SEQUENCE_CACHE[status]       
            return SEQUENCE_CACHE[value]                                 
        except (KeyError, TypeError):                                    
            pass                                                         
                                                                         
        if n is None:                                                    
            result = fn(value, status)                                   
        else:                                                            
            result = fn(value, status, n)                                
        if status <= 1:                                                  
            SEQUENCE_CACHE[value] = result                               
        return result                                                    
                                                                         
    return kicker                                                        
                                                                         
@cache_euler14                                                            
def euler14(value, status=None, n=1):
    """
        'value' represents the base value                                 
        'status' represents the actual value according with odd and even formulas
        'n' recursion deepness                                            
    """
    if status is None:                                                    
        status = value                                                    
    
    if status <= 1:                                                       
        return n
    if status % 2 == 0:                                                   
        #even
        status = status / 2                                               
    else:
        #odd
        status = status * 3 + 1                                           
    
    return euler14(value, status, n+1)                                    
                                                                          

terms = 0                                                                 
value = 0
for x in xrange(0, 1000000):                                              
    result = euler14(x)                                                   
    if result > terms:                                                    
        value = x
        terms = result                                                    

print "value: %s   terms: %s" % (value, terms)

Both solutions presented here will find the answer, no optimization was taken into account. Now, from here its just keep tracking of execution of this scripts and try to optimize it.

[apalma@insys projecteuler] time python euler14_it.py 
value: 837799   terms: 525

real	0m15.777s
user	0m15.601s
sys	0m0.128s

15 seconds…. Well Its not that hard to do beter than this but I’m tired and I’ll leave it for now. One clue: for the cache, try to use a list() instead of a dictionary.

 

Regards folks

Advertisements
%d bloggers like this: