General Discussions
Discuss any topics that are not product-specific here.
Euleryx Problem 8 - Largest Product in a Series
My workflow and answer:
Answer: 23514624000
Last Weeks Favourite Solution:
Another tough decision but, with a macro free solution that ran in under 1 second, @AkimasaKajitani's solution leveraging a generate rows has won this weeks award. The generate rows doesn't just check for factors but is even able to tag the prime numbers with a "-1", all in a singular tool. If you want to check you this solution, please view it on page one of last weeks post or by clicking here.
Mathematical Theory – The Truth
Yes, throughout this series, my intention was to try and solve these problems using some form of mathematical theory to help optimise the solution. However, problem 8 has got me stumped. Whilst there are some time-saving techniques we could use, such as ignoring any groups that contain a 0 (as their product will just = 0), I could not think of any significant theories to apply here.
On the bright side, this does give me the opportunity to join Team Brute Force! If you are still interested, here's how I tackled the problem.
Method:
As with any problem, no matter what approach you take, you need an input to begin. In this case, I pasted the 1000-digit number into the text input tool, then began to solve the problem:
1) Use Regex to remove new lines and then tokenise the number to get one digit per line.
2) Create a Record ID and then generate 13 rows per digit. (If we are creating groups of 13 consecutive numbers, each digit will appear in up to 13 groups).
3) Create Group IDs. Now we have 13 copies of each digit, we can allocate their groups based on their Record ID and RowCount.
4) Find the product per group, and filter to groups with 13 digits only (full groups).
5) Sort descending and sample your top answer.
6) Submit your answer to the Project Euler Website!
Summary:
Despite taking a different approach from usual, we have arrived at a solution that not only runs but takes just 0.3 seconds.
With it being so quick, I'd like to think this was still an effective method, please share your thoughts below!
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
I knew my 13 digit number couldn't have a 0 in it so I initially treated 0 as a delimiter. I then filtered for any numbers that were 13 or more characters. Then I ran it through an iterative macro where iteration 0 would take the first 13 digits, iteration 1 would take digits 1-14, etc.
But then for v2, I was thinking about how the odds were good that my number also wouldn't have a 1 in it, probably not a 2, or even maybe a 3. So I treated 0123 as delimiters. I was left with a single 13 digit number, which was the solution.
I feel like that was cheating...? I dunno, it seemed too simple/neat :) If I had multiple results and/or results with >13 characters, I would've sent it through the macro and evaluated the largest product, but I didn't need to
I solved it using a straightforward approach.
My solution. With this data volume, I could not see difference in time if I the 13 digits contains "0" or not..
I compared the performance between with and without Filter tool.
Comparison of performance profiling between with / without filtering "0".
After adding Filter tool (0.64 milli second), RegEx tool (to split to single digit), Select tool (to convert str to number)
and Summarize tool (to calculate products) ran 23 milli seconds faster.
So we may see more notable performance enhancement with a much larger data set.
String Coding Tool Golf
Happy Solving!
