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:prd each distinct asc each {x cross x} 1 _ til 1000 / candidate products
ip:{x~reverse x} / is palindrome?
max c where ip each string c
Optimisation
Or we can loop through the products in descending order:
i:count C:asc c
while[not ip string C i-: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)\ts max c where ip each string c
94 24835552
q)\ts i:count C:asc c; while[not ip string C i-:1;]; C i
10 12584304
A functional version of the above:
.[@] ({not ip string x y}.) @[;1;-1+]/ (asc c;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+count list)}
lastitem[not ip string@] asc c
From https://github.com/qbists/studyq/blob/main/euler/04.md
Studying q rocks. 😂
