4
\$\begingroup\$

Project Euler Problem 76 asks:

How many different ways can one hundred be written as a sum of at least two positive integers?

My code is correct but just works slowly.

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

num = 5
K = [[1 for i in range(num)]]
count = 0
for i in range(len(K[0])-2):
    K = con(K)
    print(K)
    count = count + len(K)
print(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?

\$\endgroup\$
  • \$\begingroup\$ That fact that you need to spend a paragraph explaining how your code works is a pretty good sign that your code is in desperate need of better variable names and some commenting. \$\endgroup\$ – Bailey Parker Apr 28 at 2:27
3
\$\begingroup\$

The optimal solution to this is significantly simpler than what you have. We'll get to that in a second. First, let's examine your code:

  • Cop should not begin with a capital letter. Variables should be snake_case. Furthermore, cop is a bad name. At the least it should be copy (don't shorten names, it only makes things less clear--unless the shortening is a broadly understood acronym like HTML). But copy of what? From that name, I can't tell. I have to go hunting for the initialization of it (and all of the mutations to it) to figure out what it actually does. What are J, Q, and W? Again, they should be lowercase. But also, letters make awful variable names (except for maybe i and j for numeric loop variables). n
  • Your code either has or is precariously close to an off by one issue with all of the +1ing that you're doing. Why is it print(count + 1) and not print(count)?
  • count = count + len(K) should be count += len(K)
  • [[1 for i in range(num)]] can just be [[1] * num]
  • PEP8 your code. It is messy and has little whitespace, which makes it hard to follow.
  • con is a poorly named function. What does that even mean? Clearly it doesn't count anything because you have to use it in a loop to get the answer to the problem.
  • Why are you maintaining Q as a list to only use it in T = list(set(Q))? Q should just be a set from the start, that's more efficient.
  • There's no need to do the list in T = list(set(Q)). You can iterate over T = set(Q) (without the need to create a list).
  • You need to comment this code. The fact that you need to spend a paragraph explaining how your code works is a pretty good sign of this. It would take a long time for me to walk through this an understand how each piece works. Comment things that aren't clear. Comment why not how. Add docstrings to functions. I wouldn't even know how to just use your code to get the answer to the problem. I assume setting num, but it's unclear to me if that gives the answer for 5 or 4, given that you do range(num) which is exclusive not inclusive (it's [0, 1, 2, 3, 4])

That's a not exhaustive list of issues with your code as it exists. But, we need to start from scratch, because what you have is way too complicated for the task at hand. If we take a step back and rethink the problem, we can come up with a much more elegant solution.

Let's start by looking at the problem:

It is possible to write five as a sum in exactly six different ways:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

Here's a question: can we write out all of the ways to write four as a sum? Sure, it looks like:

3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

Hmm, that looks suspiciously similar to the list above. Let's rewrite the sums for five. I'll put the parts that are unique to five in parenthesis:

(4 + 1)
(3 + 2)
3 + 1 (+ 1)
2 + 2 (+ 1)
2 + 1 + 1 (+ 1)
1 + 1 + 1 + 1 (+ 1)

We should notice a pattern here. Namely, the sums for five are the sums for four with + 1 added and an additional 2 new ways. The 2 new ways are just combinations of the first sum of four + 1. 3 + 1 + 1 if you merge the 1 + 1 is 3 + 2 and 3 + 1 + 1 if your merge the 3 + 1 is 4 + 1.

Similarly, we can write the sums for four as the sums of three with some extras added on:

(3 + 1)
(2 + 2)
2 + 1 (+ 1)
1 + 1 + 1 (+ 1)

This pattern continues all the way down to one where there is only one sum: 1 itself.

Hopefully, this pattern is hinting to you that there is a recurrence relation we could take advantage of. Namely, if we know the number of sums for 5 is the number of sums for 4 plus some extras. This goes all the way down to 1. This should hint to you that a recursive solution may be appropriate. However, there's a catch. While we can implement it recursively, it turns out that the dependency chain isn't linear. Each answer depends on every answer before it. Because of this, even though you could compute the answer recursively, it would be inefficient, because it would require recomputing the answer for every number below. But we're really close.

As an aside, there are other (perhaps more natural) phrasings of this problem, which may make this +1 structure more obvious. Consider you have n pennies. How many unique groups of all n pennies can you make (each group is like one of the terms in the addition). For example, if n = 5 then a group of 4 pennies and a group of 1 pennies (one of the sums for 5) is like 4 + 1.

The efficient solution recalls that we can take a dynamic programming approach where we memoize answers to smaller problems. We can do so by accumulating a list of the previous answers num_ways_to_sum and build this up from 1 up to the desired number:

def count_number_of_ways_to_sum(target_sum):
    """
    Compute the number of unique ways (order does not matter) of summing to target_sum
    using numbers from 1 to target_sum, exclusive.
    """
    if target_sum <= 1:
        raise ValueError('there are no numbers greater than 0 less than the target sum')

    # ith index contains the answer to the (i + 1)th subproblem
    num_ways_to_sum = [0] * (target_sum + 1)

    # There is only 1 way to sum to 1
    num_ways_to_sum[0] = 1

    # Consider sums involving numbers in [1, target_sum)
    for i in range(1, target_sum):
        # Every subproblem j >= i depends on i
        for j in range(i, target_sum + 1):
            # The number of ways to sum j includes all the ways to sum i 
            # with all the ways to sum (j - i) appended (like the parenthesis)
            num_ways_to_sum[j] += num_ways_to_sum[j - i]

    return num_ways_to_sum[target_sum]

Note a few things:

  • We document and properly name the function
  • We are careful with domain. We raise ValueError when we are given an impossible target_sum. (1 has no solution, because there are no counting numbers less than 1 but greater than 0)
  • We name variables appropriately. It is clear what num_ways_to_sum is. We may even consider renaming i and j, although the comments perhaps make them clear enough (and given that they are only used over 3 lines, this information is close together and intelligible as a single unit.
  • We comment!
  • We use python standard library features appropriately (like lists, range, etc.)

Now, you should definitely test this with the unittest package.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot for your great explanation and effort. From now on, I'll be much more careful about the variable names and syntax.I ll test it and try to understand the dynamical programming. Thanks a lot again. \$\endgroup\$ – Reign Apr 28 at 8:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.