Euleryx Problem 31 – Coin Sums
My workflow and macro:
Spoiler
Workflow:
Macro:
Answer: 73682
Last Week's Favourite Solution:
Last week's project emphasised the importance of identifying an upper bound, whilst all solutions ran quickly, @DaisukeTsuchiya’s solution required the least amount of records, crowning it, last weeks favourite solution. This solution not only generates the least records but also includes a table at the top, to highlight, why the upper bound was chosen. I would also like to give credit to those who increased the lower bound. Although these only eliminated a few records, this was a clever trick to reduce the input further. Please find @DaisukeTsuchiya's solution on page one of last week's post or click here.
Definitions:
- Permutations: A list of values where the order matters. I.e:
Are all different permutations.
- Combination: A list of values where the order does NOT matter, I.e:
Are all considered the same combination of letters.
Mathematical Theory:
This problem could be approached in many different ways, the angle taken in the solution below, is somewhat bruit force, however, there are some constraints which prevent any duplicate values from being calculated.
The first thing to note, is that this problem is asking for the number of ways to make £2. Although it may sound a little ambiguous, this is refereeing to combinations, NOT permutations. Acknowledging this is key as it enables the solution to remove any duplicate records. The only question is, how can we easily tell if it’s a duplicate or not?
Taking the example from the definition section above, the permutations
All look different at first glance. As we are dealing with combinations, we know the order doesn’t matter, so let's rearrange all of these permutations alphabetically.
- A,B,C = A,B,C
- A,C,B = A,B,C
- B,C,A = A,B,C
This list of values is then easy to deduplicate; there is a way to avoid creating the duplicates in the first place. Assuming we start with a single letter, every time we add another one to the list, lets just make sure it is either equal to, or after the previous letter. I.e
Start with :
A
B
C
Then add only letters which appear after them, to each one.
A – (A,A) (A,B) (A,C)
B – (B,B) (B,C)
C – (C,C)
Following the same rule for each of these, we get:
(A,A) – (A,A,A) (A,A,B) (A,A,C)
(A,B) – (A,B,B) (A,B,C)
(A,C) – (A,C,C)
(B,B) – (B,B,B) (B,B,C)
(B,C) – (B,C,C)
(C,C) – (C,C,C)
As you can see, by following this simple rule, all combinations are therefore created in alphabetical order, and are already unique. This removes the need for a deduplicate step, and stops the data from exploding with loads of duplicate combinations.
Method:
1) Input the coin values, and create some placeholder columns for later.
2) Feed both the original list of coins, and the data with the additional columns, into an iterative macro:
- Inside the macro, first, output any records which already have a value of £2, and completely remove any which exceed the £2 threshold
- Append all the coin values onto records which are currently under £2
- Now like mentioned in the previous section, by ensuring any subsequent values are atleast as big as the latest coin selected, we can avoid any duplicate data. Use a filter to remove the unwanted records.
- Update the Value, Last coin and Coins column, to reflect all the coins selected per record.
- Loop back round, adding another coin on each time, until all lists of coins exceed the threshold. (Note: make sure to set the maximum iterations high enough in the interface designer).
3) All that’s left after the macro is to count the number of combinations (records), to get the answer.
4) Submit your answer to the Project Euler Website!
Summary:
Removing duplicates early on proved key in this challenge. Instead of waiting until the end, each iteration would only loop through unique records, thanks to an easy trick to keep the combination values sorted. Optimisation tricks like these ultimately reduce the computation required and massively improve the run times.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
