Project Euler 76 - Counting Summations

Official link: https://projecteuler.net/problem=76

Thought Process

This problem is a more difficult Version of Problem 31, I had to come up with an actual partition function because I cannot do 100 loops in python (Or at-least I really didn't want to).

I thought that this would be a good problem to use some dynamic programming because we can break this problem down in sections for example lets say we want to find the number of ways to partition 10 and we must include a 7, then we have only a few ways:

10 = 7 + 3
10 = 7 + 2 + 1
10 = 7 + 1 + 1 + 1

What I notice here is that 3, 2+1, 1+1+1 are exactly the partitions of the number 3! so given that the number 7 must be included we have 3 ways to express the number 10, given the number 8 must be included we have 2 ways to express the number 10, and you can see where i'm going with this, each number references a predecessor which we can build up through dynamic programming.

As with most of my dynamic programming solutions I will try to give a more visual aid as it is difficult to understand

The function Partition takes 2 inputs:

goal
- The is the number we are looking to achieve for this question goal would be 100
alist
- This is a list that contains all of the numbers we are allowed to use, for the given problem it would be all numbers 2 to 100

I have included a sample output which shows the function calculating the number of ways to partition 5 so we can understand what is going. Here goal is 5 and alist = [2,3,4,5]

We initialise an array called ways = [1, 0, 0, 0, 0, 0] where ways[x] represents the number of ways to write x using only the number 1
- Note: ways[0] = 1 because 0 = 0 + 0
After the first iteration where options = 1, we get ways = [1, 1, 1, 1, 1, 1] because every number can be written as a sum of 1's
options = 2, what we are going to do now is find the number of ways to partition the numbers 1 to 5 using only 1 and 2
- len(ways)-options = 4
- i = 0 => ways[i + option] = ways[2] += ways[0], this tells us we can write 2 in only 1 way using 2 and 0 which is 2 + 0
  1. ways = [1, 1, 2, 1, 1, 1]
- i = 1 => ways[i + option] = ways[3] += ways[1], this tells us we can write 3 in only 1 new way using 2 and 1 which is 2 + 1
  1. ways = [1, 1, 2, 2, 1, 1]
- i = 2 => ways[i + option] = ways[4] += ways[2], this tells us we can write 4 in only 2 new ways using 2 and 1 which is 2 + 1 and 2 + 2
  1. ways = [1, 1, 2, 2, 3, 1]
- i = 3 => ways[i + option] = ways[5] += ways[3], this tells us we can write 5 in only 2 new ways using 2 and 1 which is 2 + 2+ 1 and 2 + 1 + 1 + 1
  1. ways = [1, 1, 2, 2, 3, 3]

Now we see that given that we can only use the numbers 0, 1, and 2 we can write 5 in 3 different ways 1 + 1 + 1 + 1 + 1, 2 + 1 + 1 + 1, 2 + 2 + 1

Using this process we iteratively build up the possible number of ways.

The partition function will be included in my Essential Functions

Interactive Code

Input an integer (userinput)

Code will output the number of ways yourinput can be written as a sum of at least 2 positive integers

Page updated

Google Sites

Report abuse