Euleryx Problem 4 - Largest Palindrome Product
My workflow and answer:
Spoiler
Answer: 906609
Last Weeks Favourite Solution:
Last week's episode had some really interesting discussions, thank you everyone for being so detailed in your answers. This week, we have selected @patrick_digan's solution as our winner! We loved the idea that you could calculate which factors were prime by simply checking if they were divisibly by the other factors. If you want to check out @patrick_digan's post, find it on page two of last weeks challenge, or click here.
You may also have noticed that we have been recognised with an official "Project Euler" label, now attached to all of our posts. Thanks for the amazing feedback and support all, shout out @Carolyn for being the Euleryx mascot!
Definitions:
- Product: The result of multiplying two numbers together.
- Palindrome: A number (or word/ sequence) which reads the same backwards as it does forwards. E.g. 101.
Weighing up the options:
Two main routes sprang to mind here:
- Use an iterative macro. This would allow us to stop calculations as soon as the answer is found.
- Use generate rows to find all possible palindromes, then take the greatest.
On the face of it, an iterative approach sounds like the quicker option as it involves fewer calculations; however, if the Advent of Code has taught me anything, it's to properly consider all options. If not, you may pay the price with a lengthy run time!
If we went the generate rows route, we would need to calculate the product of every 3-digit number pair. As a rough estimate, this would be 1000 * 1000 calculations (1,000,000). Whilst this seems like a large number, this is not a great deal of records for Alteryx, so I decided to go with this method. (Plus, I had a couple of ideas in mind to significantly reduce this number.)
Method:
- To begin with, I used a generate rows to create my input values. Instead of generating all numbers from 0-1000, I instead only generated the 3-digit numbers by starting from 100 and ending at 999.
- Next, I appended this list to itself to create all combinations of 2, 3-digit numbers.
- Here’s where we can save some time, as we are finding the product, the order of the numbers does not matter, i.e. 100 * 200 = 200 * 100, therefore considering both records would be redundant.
This will occur with almost every pair of 3-digit numbers. To remove these redundancies, we can use a filter to state that the number in the left-hand column must be greater than (or equal to) the number in the right-hand column. This leaves us with only 405,450 records going forward.
- Calculate the product of all the 3-digit number pairs. And reverse the answer, too.
- Filter to records, where the product = the reversed string. Then sort and sample to get the greatest value.
- Submit your answer to the Project Euler website!
Summary:
Whilst the solution this time was somewhat brute force; we were still able to use a couple of tricks to reduce the computation required.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
