Project Euler P76

  • Python
  • Thread starter Arman777
  • Start date
  • #1
1,777
139

Summary:

How many different ways to write the 100.

Main Question or Discussion Point

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:

Answers and Replies

  • #2
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
2019 Award
24,565
7,457
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.
 
  • #3
1,777
139
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.
 
  • #4
308
168
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)))
 
  • #5
1,777
139
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
 
  • #6
PeterDonis
Mentor
Insights Author
2019 Award
29,653
8,927
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.
 

Related Threads on Project Euler P76

  • Last Post
Replies
4
Views
773
  • Last Post
Replies
14
Views
787
  • Last Post
4
Replies
97
Views
4K
  • Last Post
Replies
8
Views
4K
Replies
13
Views
1K
Replies
31
Views
3K
Replies
7
Views
521
  • Last Post
Replies
13
Views
18K
  • Last Post
Replies
5
Views
7K
Top