cancel
Showing results for
Did you mean:

## Project Euler #4  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```

Studying q rocks. 😂    