Q For Problems - Episode 4

[jkane17]

Hi everyone,

Please check out episode 4 of the Q For Problems video series.

This covers problem 4 from the Project Euler problem set. Project Euler - Problem 4 

The problem wants us to find the largest palindrome made from the product of two 3-digit numbers.

Hopefully you enjoy the new intro, outro and section transitions! 😊

Feel free to share your own solutions and ideas in the comments.

Thanks

[SJT]

Having just posted about this problem at GitHub.com/qbists/studyq, really interesting to see your approach to it, and attention to performance. 

Minor quibble: I’m told composing a sequence of unaries by terminating it with the Identity function is an ‘accidental’ of the parser. Instead use Apply At  @, which is supported syntax.

Faster to compare by first Tok-ing to integers? Ah ha! I’ll incorporate that and credit you!  👏 

On the next episode of the ArrayCast the panel discusses the difference between using symbols and keywords. We have a nice example of that difference here!

The keyword max conveys clearly that it returns the highest item, which is what we want. Job done?

Its symbolic form |/ however is clearly an iteration, which suggests something to think about. The problem asks for the largest palindrome. Sorting is fast. We can sort the candidates and start testing from the top; stop at the first hit. We don’t need to test every candidate. Speed-up is 100×.

It is a subtle but profound point: the virtue of a “notation as a tool of thought” is not that that it lets us stop thinking about iteration but that it helps us think about iteration more clearly. (All that said, it is still good q style to prefer the q keywords to their symbolic definitions – but watch out!) 

The GitHub page discovers an elegant q form for finding in a list the last item that passes a test.

Your memory economy of tackling the problem in ranges works very well with this – but starting from the highest candidates. 

[jkane17]

Minor quibble: I’m told composing a sequence of unaries by terminating it with the Identity function is an ‘accidental’ of the parser. Instead use Apply At  @, which is supported syntax.

---

I picked up the use of the :: to create a composition from the FunQ book by Nick Psaris. In this book, Nick describes the :: as a better alternative to @ because

1.  :: is not visible in the function train:

   q)sqrt sum abs::
   sqrtsumabs
   q)sqrt sum abs@
   sqrtsum@[abs]

2.  @ creates a composition which can accept only a single argument, where as :: does not have this limitation:

   q)add:{x+y}
   q)f:1-add@
   q)f[1;2]
   'rank
   q)f:1-add::
   q)f[1;2]
   -2

I think it was a "happy" accident that this works, but I guess it may not be a good idea to use if it was going to be removed from the language in the future.

---

Its symbolic form |/ however is clearly an iteration, which suggests something to think about. The problem asks for the largest palindrome. Sorting is fast. We can sort the candidates and start testing from the top; stop at the first hit. We don’t need to test every candidate. Speed-up is 100×.

---

Interesting point. I guess this shows both a pro an con of using keywords. 

Pro: Development is faster and code is often simpler and easy to read. 

Con: The ease of using the keyword meant that I did not think about the underlying iteration. Should I have though about the iteration level, I might have discovered and applied the optimisation.

Looking forward to the next Array Cast episode!

[alivingston]

Good explaination of your approach here.

I've found a more novel approach where we can create palindromes and then check if it has products, rather than finding all products and checking if they are palindromes.

This has the benefit of not needing to create a matrix of products and keeps memory usage under control.

We can create the palindromes from inside out, going from 9 to 0. This means our list will be already be sorted in descending order.

Then using recursion, we can check if each palindrome has 2 products within our range and early exit once we have our solution.

This yields ~200ms for 5 digit numbers and 14s for 6 digit numbers.

f:{
    // Create all palindromes in reverse order
    digits:reverse string til 10;
    palindromes:{[x;y;z]raze x,/:'y,\:/:x}[digits]/[;til x-1];
    pals:"J"$palindromes 2#/:digits;

    // create all 4 digit numbers
    nums:reverse r[1]+til(-/)r:`long$10 xexp 0 -1+\:x;
    
    // Recursively check each palindrome, early exit if found
    {[pals;nums]
        p:first pals;
        b:and[first[nums]>n]not mod[;1]n:p%nums mod[p;nums]?0;
        $[b;p;.z.s[1_pals;nums]]
    }[pals;nums]
 }

\ts f 3 / 906609 -       0      820208
\ts f 4 / 99000099 -     6      13649968
\ts f 5 / 9966006699 -   204    360770864
\ts f 6 / 999000000999 - 14273  8422339312

[jkane17]

Very efficient solution!

[SJT]

Delightful! Lest this roll off into the past – as blogs naturally do – would you care to add a section on this at https://github.com/qbists/studyq/blob/main/euler/04.md ?

[alivingston]

Thanks Stephen! I've created a pull request there.

[gberkeley]

Hi, very nice. I'm pretty new to Q so it's cool to see how to handle recursion.  

I see 2 potential issues which may not really affect the final answer, but are perhaps worth bearing in mind.

The list pals will contain non palindromes as the outer digit is allowed to be zero. So for example:

q)digits:reverse string til 10;
q)palindromes:{[x;y;z]raze x,/:'y,\:/:x}[digits]/[;til 3-1];
q)pals:"J"$palindromes 2#/:digits
q)(-5)#pals
4400 3300 2200 1100 0

The other thing is only even length palindromes are considered. You can have odd length palindromes 911*109=99299, so you can't for instance reverse pals to find the min.

[alivingston]

Hi gberkeley, well spotted! You are totally correct in what you have said here, the last 10% of "pals" will have been joined with "0" and will therefore not be palindromes when cast back to a long.

You're also right that I don't check any of the odd-digit palindromes. This is because for X-digit products, their even-digit palindromes will always be larger than their odd-digit palindromes.

eg for 3-digit products

odd-digit palindrome range  = 10000  - 99999
even-digit palindrome range = 100000 - 999999

I figured I could get away with not checking odd-digit palindromes and not removing the last 10% of invalid "pals", if I could prove that there will always be at least 1 even-digit palindrome. And with a bit of trail and error, managed to find this:

909*902             / 819918
9009*9002           / 81099018
90009*90002         / 8100990018
900009*900002       / 810009900018
9000009*9000002     / 81000099000018
90000009*90000002   / 8100000990000018

I maybe should have added this into my original description, but I appreciate the question.

[alivingston]

Which, now that I think about it, could have been used to reduce the total number of "nums" that need checked.

nums:reverse(n-m)+til m:div[;10]n:prd x#10;

This doubles performance from original code.

Further improvements could be made by not creating all of the last palindrome joins and only joining 8 and 9.

palindromes:{[x;y;z]raze x,/:'y,\:/:x};
pals:"J"$palindromes[2#digits]/[;0] palindromes[digits]/[2#/:digits;til x-2];

This has a 5 times speed improvement from original code.