Euleryx Project 4 - Largest Palindrome Product

[Pilsner]

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:

1. 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.
   
   
   
   
   
2. Next, I appended this list to itself to create all combinations of 2, 3-digit numbers.
   

     

   
   
   
   
3. 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.
   
   
   
   
4. Calculate the product of all the 3-digit number pairs. And reverse the answer, too.
   
   
   
5. Filter to records, where the product = the reversed string. Then sort and sample to get the greatest value.
     
   
   
   
6. 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.

[DaisukeTsuchiya]

Solved it straightforwardly.

Spoiler

Repeat "Generate row" twice to create all possible combinations of 3-digit numbers.
Use formulas to calculate the Product and Reverse String, and find the largest matching pair among them.

[caltang]

Did it! 

Spoiler

The largest palindrome made from the product of two 3-digit numbers is 906,609.

[caltang]

Haha omg @DaisukeTsuchiya same solution!! You beat me to it.

[KGT]

Many ways to solve this, and the main difference being Number vs String for the palindrome check...

Spoiler

I created a field Floor(length(....)/2 and used that in Left/Reverse(Right) comparison

[BS_THE_ANALYST]

I got to use the REVERSESTRING function. Love it when I get a chance to use this 😏😂. I still need to do last week's solution @Pilsner. I'll get that sorted this weekend. Can't wait to nerd out 😂.

Spoiler

[martinson]

Great challenge!

Spoiler

2 minutes 50 seconds 

[Carolyn]

Solved!

Initially I did a Generate Rows with all the numbers from 900 to 999. 

But then for v2, I thought about how since we're talking about products, I know that my numbers will end in either 1, 3, or 9, assuming that my palindrome product starts with 9. So then I redid my Generate Rows and instead of 1000 values, I only had 30.

And I agree with others - ReverseString is such a fun function that I don't often get to break out!

Spoiler

[gawa]

I implemented a pruning with fuzzy assumption 'answer would be 6 digits'. With this, I just had to examine the number of multiple of 11. More in spoiler.

Spoiler

If answer is 6 digits, it is always divisible by 11. Either of two 3-digit number shall be divisible by 11.
Accordingly, the combination of number to be examined can be pruned as follows, that is 72,900 patterns:
(110, 121,132...979,990) x (100,101,102...998,999)

[Yoshiro_Fujimori]

My solution.

I also tried with 4-digits numbers.

Spoiler

Workflow

1. Generated rows with column [a] from 999 to 900.
  (assuming there would be at least one Palindromic number)
2. Calculate Palindromic numbers [b] for each [a].
3. Generate rows for each row with new column [c] from Sqrt([b]) up to 999.
  (Because one of the factor has to be smaller than Sqrt([b]).)
4. Check if [c] is a factor of [b].

Eventually, there was only one Palindromic number between 999999 and 900009.
Result: 993 * 913 = 906609

I applied the same logic to solve for 4 digits

Result: 9999 * 9901 = 99000099
But I am not 100% sure if this is correct. Could anyone verify this?