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

Updated TrustyTony 0 Tallied Votes 684 Views Share

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())
TrustyTony 888 pyMod Team Colleague Featured Poster

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())
TrustyTony 888 pyMod Team Colleague Featured Poster

Finally came time to move on to faster computer and now this code runs at 755 microseconds original, 502 microseconds the faster cleaned up version :-)

HiHe 174 Junior Poster

I like
http://projecteuler.net/problem=59
it's actually practical.

TrustyTony 888 pyMod Team Colleague Featured Poster

And some alternatives and reason why the key can not be safely reused can be found in our longish discussion in this thread: xor encryption (link to best function). I do not remember exactly how I did the 59, hard disk crash took most my solutions about year ago. I seem to remember it was quite simple stuff. But three lowercase letters, what can you expect...
(BTW running the speed test not including the fastest one of different versions gives me now 69 ms on my i7 computer vs 898 ms of original testers PC)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.