954,545 Members — Technology Publication meets Social Media
Username:
Password:
Lost login information?

Reasonable fast solution of Project Euler problem 61 (under 3 ms)

0
By Tony Veijalainen on Feb 4th, 2011 5:02 am

Here is my celebration post for entering level 3 in Project Euler.

Again I left in my debug prints. I am in process of adapting myself to new .format style of formatting. I have commented out the prints though to get visible the running time of the functions own action. It is not doing half bad actually:

J:\test\Project Euler>\python27\python -m timeit "import euler61" "euler61.euler61()"
100 loops, best of 3: 2.5 msec per loop

That is faster than the printing of the result to console with newline.

Of course, my generator expression is anything but PEP8 compliant in it's simplicity, but it is self documenting for me.

Problem description can be found in: http://projecteuler.net/index.php?section=problems&id=61

from __future__ import print_function
import time
import itertools

def join(*n):
    '''concatenate intergers for a new integer'''
    a = n[0]
    for b in n[1:]:
        a = a * next(10**n for n in range(1000) if (b < 10**n)) + b
    return a

assert(join(123,456)==123456)

def triangle(start,until):
    n = value = 0
    while value < until:
        value = int(n*(n+1)/2)
        n+=1
        if value > start: yield value

def square(start,until):
    n = value = int(start**0.5)-1
    while value < until:
        value = int(n*n)
        n+=1
        if value > start: yield value

def pentagonal(start,until):
    n = value = 0
    while value < until:
        value = int(n*(3*n-1)/2)
        n+=1
        if value > start: yield value

def hexagonal(start,until):
    n = value = 0
    while value < until:
        value = int(n*(2*n-1))
        n+=1
        if value > start: yield value

def heptagonal(start,until):
    n = value = 0
    while value < until:
        value = int(n*(5*n-3)/2)
        n+=1
        if value > start: yield value

def octagonal(start,until):
    n = value = 0
    while value < until:
        value = int(n*(3*n-2))
        n+=1
        if value > start: yield value

def function_name(gen):
    return str(gen).split()[1]

def euler61():
    generators = (triangle, square, pentagonal, hexagonal, heptagonal, octagonal)[::-1]
    generator_names = tuple(function_name(gen) for gen in generators)
    t0 = time.clock()
    generated_values = [[value for value in generator(1000, 10000)] for generator in generators]
#     print('Function values counted in {t} us'.format(t=1000000*(time.clock()-t0)))

    t0 = time.clock()
    data =tuple((generator_names[ind],
                sorted((a, b) for a, b in (divmod(value, 100)
                                        for value in values)
                        if a > 9 and b > 9))
                for ind, values in enumerate(generated_values))

    t1 = time.clock()
#     print('function divmod values generated in {t} us'.format(t=1000000*(t1-t0)))
    values = next(((a, x2, c, x4, e, x6), (g1, g2, g3, g4, g5, g6))
        for g1, g2, g3, g4, g5, g6 in itertools.combinations(generator_names, 6)

        for g1, values1 in data
        for (a, x1) in values1

        for g2, values2 in data if g2 != g1
        for (x2, b) in values2 if x1==x2

        for g3, values3 in data if g3 not in (g1, g2)
        for (c, x3) in values3 if b==c

        for g4, values4 in data if g4 not in (g1, g2, g3)
        for (x4, e) in values4 if x3==x4

        for g5, values5 in data if g5 not in (g1, g2, g3, g4)
        for (f, x5) in values5 if e==f

        for g6, values6 in data if g6 not in (g1, g2, g3, g4, g5)
        for (x6, g ) in values6 if x5==x6 and a==g)

#     print('Path {v} found in {t2} us'.format(v=values, t2=1000000*(time.clock()-t1)))
    numbers = list(join(*values[0][i:i+2]) for i in range(len(generators)-1)) + [join(values[0][-1], values[0][0])]
#     print('As numbers {thenumbers}, sum = {s}. Final timing: {t} us'.format(thenumbers=numbers, s=sum(numbers), t=1000000 * (time.clock()-t1)))
    return sum(numbers)

if __name__ == '__main__':
    print(euler61())

OK, not so clean and clear code. Here is the slower version, 20 ms. Also the naming of chain variables is by logic to get result a,b,c,d,e,f. lambda stuff makes this version so slow but cutting out repetition of code:

from __future__ import print_function
import time

def join(*n):
    '''concatenate intergers for a new integer'''
    a = n[0]
    for b in n[1:]:
        a = a * next(10**n for n in range(1000) if (b < 10**n)) + b
    return a

assert(join(123,456)==123456)

def figurate(f, start,until):
    n = value = 0
    while value < until:
        value = f(n)
        n+=1
        if value > start: yield value

def euler61():
    figurates = (("triangle", lambda n: (n*(n+1)//2)),
                  ("square", lambda n: n*n),
                  ("pentagonal", lambda n:(n*(3*n-1)//2)),
                  ("hexagonal", lambda n: n*(2*n-1)),
                  ("heptagonal", lambda n: n*(5*n-3)//2),
                  ("octagonal", lambda n: n*(3*n-2)))

    figurate_names = [name for name, _ in figurates[::-1]]
    generated_values = dict((name, list(figurate(formula,1000, 10000)))
                            for name, formula in figurates)
    data= tuple((name, sorted((a, b)
                        for a, b in (divmod(value, 100)
                        for value in values) if b > 9))
                for name, values in generated_values.items())

    values = next(((a, b, c, d, e, f), (g1, g2, g3, g4, g5, g6))
        for g1, values1 in data
        for (a, x1) in values1

        for g2, values2 in data if g2 != g1
        for (b, x2) in values2 if b == x1

        for g3, values3 in data if g3 not in (g1, g2)
        for (c, x3) in values3 if c == x2

        for g4, values4 in data if g4 not in (g1, g2, g3)
        for (d, x4) in values4 if d == x3

        for g5, values5 in data if g5 not in (g1, g2, g3, g4)
        for (e, x5) in values5 if e == x4

        for g6, values6 in data if g6 not in (g1, g2, g3, g4, g5)
        for (f, x6 ) in values6 if f == x5 and a == x6)

    numbers = list(join(*values[0][i:i+2]) for i in range(len(figurates)-1)) + [join(values[0][-1], values[0][0])]
    return sum(numbers)

if __name__ == '__main__':
    print(euler61())


Also the clean up done for the faster version and misleading itertools.combinations removed.

from __future__ import print_function
import time

def join(*n):
    '''concatenate intergers for a new integer'''
    a = n[0]
    for b in n[1:]:
        a = a * next(10**n for n in range(1000) if (b < 10**n)) + b
    return a

assert(join(123,456)==123456)

def triangle(start,until):
    n = value = 0
    while value < until:
        value = int(n*(n+1)/2)
        n+=1
        if value > start: yield value

def square(start,until):
    n = value = int(start**0.5)-1
    while value < until:
        value = int(n*n)
        n+=1
        if value > start: yield value

def pentagonal(start,until):
    n = value = 0
    while value < until:
        value = int(n*(3*n-1)/2)
        n+=1
        if value > start: yield value

def hexagonal(start,until):
    n = value = 0
    while value < until:
        value = int(n*(2*n-1))
        n+=1
        if value > start: yield value

def heptagonal(start,until):
    n = value = 0
    while value < until:
        value = int(n*(5*n-3)/2)
        n+=1
        if value > start: yield value

def octagonal(start,until):
    n = value = 0
    while value < until:
        value = int(n*(3*n-2))
        n+=1
        if value > start: yield value

def function_name(gen):
    return str(gen).split()[1]

def euler61():
    generators = (triangle, square, pentagonal, hexagonal, heptagonal, octagonal)[::-1]
    generator_names = tuple(function_name(gen) for gen in generators)
    t0 = time.clock()
    generated_values = (list(generator(1000, 10000)) for generator in generators)
#     print('Function values counted in {t} us'.format(t=1000000*(time.clock()-t0)))

    t0 = time.clock()
    data = tuple((generator_names[ind],
                sorted((a, b) for a, b in (divmod(value, 100)
                                        for value in values)
                        if b > 9))
                for ind, values in enumerate(generated_values))

    t1 = time.clock()
#     print('function divmod values generated in {t} us'.format(t=1000000*(t1-t0)))
    values = next(((a, b, c, d, e, f), (g1, g2, g3, g4, g5, g6))
        for g1, values1 in data
        for (a, x1) in values1

        for g2, values2 in data if g2 != g1
        for (b, x2) in values2 if b == x1

        for g3, values3 in data if g3 not in (g1, g2)
        for (c, x3) in values3 if c == x2

        for g4, values4 in data if g4 not in (g1, g2, g3)
        for (d, x4) in values4 if d == x3

        for g5, values5 in data if g5 not in (g1, g2, g3, g4)
        for (e, x5) in values5 if e == x4

        for g6, values6 in data if g6 not in (g1, g2, g3, g4, g5)
        for (f, x6 ) in values6 if f == x5 and a == x6)

#     print('Path {v} found in {t2} us'.format(v=values, t2=1000000*(time.clock()-t1)))
    numbers = list(join(*values[0][i:i+2]) for i in range(len(generators)-1)) + [join(values[0][-1], values[0][0])]
#     print('As numbers {thenumbers}, sum = {s}. Final timing: {t} us'.format(thenumbers=numbers, s=sum(numbers), t=1000000 * (time.clock()-t1)))
    return sum(numbers)

if __name__ == '__main__':
    print(euler61())
pyTony
pyMod
Moderator
5,359 posts since Apr 2010
Reputation Points: 782
Solved Threads: 852
 

This article has been dead for over three months

Post: Markdown Syntax: Formatting Help
You
View similar articles that have also been tagged: