4. Largest palindromic product
We find the highest palindromic number in a list, and discover a general form for the last (or first) item that passes a test, without testing every item.
Problem
https://projecteuler.net/problem=4
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009=91×99. Find the largest palindrome made from the product of two 3-digit numbers.
Solution
Our candidates are the products of the unique pairs of 3-digit numbers:
c:prdeachdistinctasceach{xcrossx}1\_til1000 / candidate productsip:{x~reversex} / is palindrome?maxcwhereipeachstringc
Optimisation
Or we can loop through the products in descending order:
i:countC:asccwhile[notipstringCi-:1;] C i
The cost of the sort and the explicit loop is repaid by not casting the entire list to strings and testing all of them.
q)\tsmaxcwhereipeachstringc9424835552q)\tsi:countC:ascc;while[notipstringCi-:1;]; C i1012584304
A functional version of the above:
.[@] ({notipstringx y}.)@[;1;-1+]/(ascc;count[c]-1)
Note the use of @[;1;-1+]/ to decrement the index, and .[@] to resolve the result.
Generalisation
From this we can see a general form for finding the last item that passes a test:
lastitem:{[test;list].[@] ({x y z}[test].)@[;1;-1+]/(list;-1+countlist)}lastitem[notipstring@]ascc
From https://github.com/qbists/studyq/blob/main/euler/04.md
Studying q rocks.