Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Python Project Euler Question 60

  1. Aug 29, 2018 #1
    https://projecteuler.net/problem=60

    I wrote a piece of code to solve the problem but it still takes too much time to solve it Any ideas how can I improve my code, like adjustments that I can make ?

    Code (Text):
    import itertools
    import time

    start = time.perf_counter()
    def prime(N):
        if N == 0 or N == 1 or N == 5:
            return False
        for i in range(2, int(N ** 0.5) + 1):
            if N % i == 0:
                return False
        return True


    def dig_sum(j, n):  # j is the number, n is the element in the list as tuple
        d = 0
        if j == 0:  
            for k in n:
                d += sum(int(digit) for digit in str(k))
            if d%3 == 0:
                return False
            return True
        else:
            s = sum(int(digit) for digit in str(j))
            for k in n:
                w = s + sum(int(digit) for digit in str(k))
                if w % 3 == 0:
                    return False
            return True


    def con_test(j, n):  # j is the number, n is the element in the list as tuple
        if j == 0:
            w = int(str(n[0]) + str(n[1]))
            w1 = int(str(n[1]) + str(n[0]))
            if prime(w) == False or prime(w1) == False:
                return False
            return True
        else:
            for i in n:
                w = int(str(j) + str(i))
                w1 = int(str(i) + str(j))
                if prime(w) == False or prime(w1) == False:
                    return False
            return True


    def st(n):            #to get rid of the repeated elements
        H = [tuple(sorted(i)) for i in n]
        G = set(H)
        return G


    Primes = [i for i in range(3,8000) if prime(i) == True]   #Prime range

    Com_two = list(itertools.combinations(Primes,2))

    G2 = [i for i in Com_two if dig_sum(0,i) == True and con_test(0,i) == True]

    G2r = st(G2)

    G3 = [(i,*j) for i in Primes for j in G2r if dig_sum(i,j) == True and con_test(i,j) == True ]

    G3r = st(G3)

    G4 = [(i,*j) for i in Primes for j in G3r if dig_sum(i,j) == True and con_test(i,j) == True ]

    G4r = st(G4)

    G5 = [(i,*j) for i in Primes for j in G4r if dig_sum(i,j) == True and con_test(i,j) == True ]

    F = [(sum(j),j) for j in G5]

    end = time.perf_counter()
    Time = end-start
    print(Time)
    print(F)
     
    When I set Primes range to 8000 it took 18 min to give an answer I checked the solution for the 4 set of primes and it gives me the right result.(If you want to check print (G4r))

    Any ideas how can I make my program faster ?
     
  2. jcsd
  3. Aug 29, 2018 #2

    jedishrfu

    Staff: Mentor

    You should try timing each function individually to see how much time they take and then from there optimize the specific functions.

    Its often said that program execution spends 80% executing 20% of the code. Try to find that 20% code and optimize it.
     
  4. Aug 29, 2018 #3
    I find the answer at by setting prime limit 10.000 . Yey for that it took 41 min. I ll try to I guess it mostly does it on the G2 level and then decreases cause the options are decreasing but G2 level is the starting point. I also think that its probably due to the algorithm . I mean I am not sure you understand what I am trying to do but I think there must be a mathematical trick.
     
  5. Aug 29, 2018 #4

    jedishrfu

    Staff: Mentor

    Yeah, I’m not sure what the code is doing but when faced with something like this that has performance issues, I try to identify what function is being the time hog and go from there.
     
  6. Aug 29, 2018 #5

    jim mcnamara

    User Avatar

    Staff: Mentor

    Consider profiling, ex: cProfile. This shows you how much time is spent by each function/method. Trying to guess is not the best choice unless you are very experienced.

    How to profile, options - https://devopedia.org/profiling-python-code
     
  7. Aug 30, 2018 #6

    verty

    User Avatar
    Homework Helper

    Use a sieve to sieve primes up to say 10 million. I think your time hog is that prime check procedure.
     
  8. Aug 30, 2018 #7
    Its my bad that I didnt explain it but I guess I dont need to from now on ( unless you want to).


    I finally manage to run it . I am saying finally cause it was hard for me to find how to run it. I add the image.

    Functions have names and you see the time that took to complete them.

    Line 63 took 168 sec and thats the G3 = [] line other then that I run this code for prime range 5000.

    İt seems that I need a better prime tester and a better con_test function.

    227.948833517
    []
    Code (Text):
             96268183 function calls in 227.950 seconds

       Ordered by: standard name

       ncalls  tottime  percall  cumtime  percall filename:lineno(function)
            1    0.018    0.018  227.950  227.950 pps.py:1(<module>)
      5775553    9.231    0.000   34.385    0.000 pps.py:16(dig_sum)
      2093904    0.437    0.000    0.437    0.000 pps.py:20(<genexpr>)
     26176944    6.086    0.000    6.086    0.000 pps.py:25(<genexpr>)
     40268129    9.080    0.000    9.080    0.000 pps.py:27(<genexpr>)
      2891920    5.823    0.000  191.264    0.000 pps.py:33(con_test)
            3    0.001    0.000    0.007    0.002 pps.py:49(st)
            3    0.004    0.001    0.006    0.002 pps.py:50(<listcomp>)
            1    0.001    0.001    0.006    0.006 pps.py:55(<listcomp>)
            1    0.068    0.068    9.512    9.512 pps.py:59(<listcomp>)
            1    1.642    1.642  168.858  168.858 pps.py:63(<listcomp>)
            1    0.549    0.549   48.872   48.872 pps.py:67(<listcomp>)
      3886258  185.447    0.000  185.447    0.000 pps.py:7(prime)
            1    0.009    0.009    0.675    0.675 pps.py:71(<listcomp>)
            1    0.000    0.000    0.000    0.000 pps.py:73(<listcomp>)
            1    0.000    0.000  227.950  227.950 {built-in method builtins.exec}
            2    0.001    0.000    0.001    0.000 {built-in method builtins.print}
        12885    0.002    0.000    0.002    0.000 {built-in method builtins.sorted}
     15162571    9.552    0.000   25.154    0.000 {built-in method builtins.sum}
            2    0.000    0.000    0.000    0.000 {built-in method time.perf_counter}
            1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
     
     

    Attached Files:

    Last edited by a moderator: Aug 30, 2018
  9. Aug 30, 2018 #8
    I changed my prime code to Miller–Rabin primality test ( I didnt write the code myself I copied ) and I find the result in 8 min 30 sec. I also need to change the con_test() function for improved result ..
     
    Last edited: Aug 30, 2018
  10. Aug 30, 2018 #9

    Vanadium 50

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2017 Award

    This runs counter to the advice earlier in the thread that the OP should learn to profile. He won't learn that if we tell him what the answer is. This is especially true if we guess.
     
  11. Aug 30, 2018 #10

    jedishrfu

    Staff: Mentor

    That's great!

    One rule of thumb that you should consider is adding a comment about where you got the copied code. In a professional environment, this may not be allowed and you might need to rewrite it (or get someone in your company untouched by seeing the code) in order to make it original code to protect your company from copyright laws.
     
  12. Aug 30, 2018 #11

    verty

    User Avatar
    Homework Helper

    True. He should learn to profile his code and I see he did just that. So I'll leave it up to him now.
     
  13. Aug 30, 2018 #12

    rcgldr

    User Avatar
    Homework Helper

    One issue is that Python is interpretative, so that will consume a lot of time compared to a compiled language like C or C++. I'm wondering how much faster the same algorithm would be in C or C++.
     
  14. Aug 30, 2018 #13
    thats really good question Sadly I dont know C...And I dont think anyone here will try to convert it. I couldnt find a faster way to do the con_test(), so thats also another thing that can make the program run faster.
     
  15. Aug 30, 2018 #14

    jedishrfu

    Staff: Mentor

    You could try converting it to Julia. Its hot right now in Data Science and is arguably much faster than Python.

    Python compiles its code into byte codes and follow on executions use that saving some conversion time. I'd run your algorithm a couple of times using the 'time' command if you were on Linux or MacOS.
     
  16. Aug 30, 2018 #15
    This is the last version with
    I dont know it too.But can it make a really huge difference ? Like minutes
     
  17. Aug 30, 2018 #16

    jedishrfu

    Staff: Mentor

  18. Aug 30, 2018 #17
  19. Aug 30, 2018 #18

    jedishrfu

    Staff: Mentor

    You have to take it with a grain of salt. Performance tests are notoriously difficult to get right. Developers will do anything to get bragging rights for speed especially in situations where money is involved. In this case, there’s a Julia consulting company being formed by the original creators so of course they’ll want Julia to win.

    As an example, the developers might optimize the underlying code to do especially well for specific test cases in order to beat a competitor. The database engine wars were like that. It meant that one database product would outperform a competitor one year and the competitor would fire back on the next release. To the ordinary user both products would perform well enough to not really matter but products are first selected based on these numbers and so there’s a sales opportunity and followon upgrades that turns into big money especially for enterprise databases.
     
  20. Aug 31, 2018 #19

    fluidistic

    User Avatar
    Gold Member

    You guys are missing an important thing. Project Euler is notoriously known for problems that aren't approachable via brute force (though you certainly can solve a few of them that way). What I mean is that, it is both a mathematical and programming challenge. Usually most problems can be solved under 2 minutes using Python. If this isn't the case, then the approach is to be reconsidered. So before going blindly into profiling and things of the sort, the very first thing to think about, is whether the mathematical approach is reasonably well suited, keeping in mind that brute force approaches are to be discarded.

    Another thing. Since the OP actually did get the correct result, he has access to the solution to this problem posted by others. And since Python is very popular, he can directly compare his code and therefore his method, to others.
     
  21. Aug 31, 2018 #20
    I think that my code would work under 1 min in C/C++ . I didnt use brute force , but I also couldnt find a better alogrithm under then this. My code works like this.

    First I made a set of 2 primes that satisfies two conditions.The first condition was the digit sum cannot be 3. The other condition was the concentrating test. After finding these all 2 prime sets, I tried to add the third prime to the set and again I checked these 2 conditions are satisfied. After that, I tried to add the fourth prime and so on.

    The best python solution that I noticed is by ximera2 :and he uses prime dictionary and then using it (and also other sort of thing he manages to reduces time 26.5sec)

    İn C and Java I saw 2 sec solution codes. I saw another python solution using graph theory and finding it in seconds.

    I dont think my algorithm is bad but I am not a good coder so this is best I can do.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted