Project Euler Problem #76

Problem #76 concerns partitions of positive integers. The question reads:

Project Euler Problem 76: Counting summations
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?

You may notice that this solution is very similar to Project Euler Problem #31 which involved determining the number of ways certain amounts of currency could be represented with coins. The only difference is that in this question, the possible values of the coins include every positive integer. You may also recall that the more efficient solution I presented in Problem #31 came from Project Euler’s documentation. Thus, I will reuse their solution to solve this problem and give credit appropriately. Here is Project Euler’s Solution:

Solution #1: Dynamic Approach (Project Euler’s Approach)

As in Project Euler Problem #31, we can observe that adding larger types of currency can be thought of as adding to the same problem with only the smaller amounts of currency. Thus, we dynamically count the number of ways each total can be summed for each new currency. In this case, the currencies range in value from 1 to n-1. Once all of the currencies have been iterated through, we are done. Here is an implementation of this approach in Python 2.7. As listed above, this is very similar to Project Euler’s solution for Problem #31.

 '''
 Author: Walker Kroubalkian (Heavily inspired by Project Euler's Solution to Project Euler Problem #31)
 Dynamic Approach to Project Euler Problem #76
 '''
 
 import time
 
 def projectEulerProblemSeventySix(n):
     numbers = []
     for x in range(1,n):
         numbers.append(x)
     ways = [0]*(n+1)
     ways[0] = 1
     for i in range(len(numbers)):
         for j in range(numbers[i], n+1):
             ways[j] = ways[j] + ways[j-numbers[i]]
     return ways[n]
 
 start = time.time()
 print projectEulerProblemSeventySix(100)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 190569291
 --- 0.000514030456543 seconds ---
 
 for input of n = 100.
 ''' 

And with that, we’re done. That only took half a millisecond to run. This is yet another example of the powers of dynamic programming.

Thanks for reading! See you tomorrow.