Project Euler P76: Counting Arrangements of Consecutive Numbers

[Arman777]

TL;DR Summary

How many different ways to write the 100.

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.

 

[Vanadium 50]

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.

 

[Arman777]

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 there's an better algorithm but I am asking about my code and how can I improve it. Not some other solutions line number or time.

 

[lomidrevo]

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:

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)))

 

[Arman777]

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:

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

 

[PeterDonis]

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.