Python Project Euler P76

  • Thread starter Arman777
  • Start date
1,444
102
Summary
How many different ways to write the 100.
Python:
import time
start = time.perf_counter()

def con(H):
    J = []
    Q = []
    W = []
    for i in H:
        for j in range(len(i)-1):
            Cop = i[::]
            y = i[j]+i[j+1]
            del Cop[j:j+2]
            Cop.insert(j,y)
            J.append(Cop)
    for i in J:
        y =(sorted("".join(str(j) for j in i)))
        Q.append("".join(y))
    T = list(set(Q))
    for i in T:
        y = [int(j) for j in i]
        W.append(y)
    return W

for num in range(1,100):
    K = [[1 for i in range(num)]]
    count = 0
    for i in range(len(K[0])-2):
        K = con(K)
        count = count + len(K)
    print(num,count+1)
    end = time.perf_counter()
    print(end-start,"second")
Here what this code does, For example, let us say num = 4. Then it creates an array of

[[1,1,1,1]]. Then it sums the consecutive numbers so our result becomes (from line 9-14)

[[2,1,1],[1,2,1],[1,1,2]] Since they are all same my code (from line 15-18) makes them just one function and returns ["112"] and then from 18-21 turns ["112"] to [[1,1,2]] and then I do this whole process again for the [[1,1,2]] and then I count the number of these arrays (from 25-29). The problem is its fast up to num = 20-30 but then it really slows down. Is there a way to increase the speed of my code or should I try a different algorithm?

Thanks.

For num = 5 the number should be 6
(1,1,1,1,1)
(2,1,1,1)
(2,2,1)
(3,2)
(3,1,1)
(4,1)

My code is correct bu just works slow.
 
Last edited:

Vanadium 50

Staff Emeritus
Science Advisor
Education Advisor
22,601
4,878
First, at no time do you mention the words "sum of integers". You are making us figure out what the problem is instead of writing it clearly. Please have more respect for our time.

Second, what algorithm? I see a mess of uncommented code, bit no description of what you are thinking about. I suppose we could eventually figure it out, but please have more respect for our time.

Third, yes, there is a better algorithm. My code (14 lines of C++) gets the answer in 2 milliseconds.
 
1,444
102
I have already explained my code. I gave an example for 5. I think I was pretty clear.
My code (14 lines of C++) gets the answer in 2 milliseconds
Indeed theres an better algorithm but I am asking about my code and how can I improve it. Not some other solutions line number or time.
 
237
116
I must agree with @Vanadium 50 , the goal could be defined in a more clear way. However with some little of guessing I think I understand what result you expect (actually deducing from your example num=5).
If you don't need to list all the possible combinations of the relative integers, you can solve the problem by using combinatorics, and using numpy arrays in order to avoid slow python loops.

Try this code:
Python:
import numpy as np
from scipy.special import binom

# input
num = 5
n = np.arange(2, num+1)
x = binom(num-1, num-n) / binom(n,1)
# output
print(np.sum(np.ceil(x)))
 
1,444
102
I must agree with @Vanadium 50 , the goal could be defined in a more clear way. However with some little of guessing I think I understand what result you expect (actually deducing from your example num=5).
If you don't need to list all the possible combinations of the relative integers, you can solve the problem by using combinatorics, and using numpy arrays in order to avoid slow python loops.

Try this code:
Python:
import numpy as np
from scipy.special import binom

# input
num = 5
n = np.arange(2, num+1)
x = binom(num-1, num-n) / binom(n,1)
# output
print(np.sum(np.ceil(x)))
This is calculating wrong. For 6 there are 10 different ways. Your code gives 12
 
24,387
6,023
I think I was pretty clear.
You weren't. The problem is to figure out how many different ways there are of writing the number 100 as a sum of two or more positive integers. "How many different ways to write 100" does not clearly communicate that.

Also, this is an Euler problem, and solutions aren't supposed to be publicly visible. So I am closing this thread.
 

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top