cancel
Showing results for 
Search instead for 
Did you mean: 

Project Euler #4

SJT
Valued Contributor

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. 😂

1 REPLY 1

LeahS
Moderator Moderator
Moderator

Brilliant post @SJT

Great reference for our KX Community!