# Re: Factor

Factor: the language, the theory, and the practice.

## Longest Palindrome

Sunday, October 24, 2010

Greplin issued a programming challenge recently, where the first question involved finding the longest palindrome substring. It was then posted as a challenge to the Programming Praxis blog, and I thought I would contribute a solution in Factor.

First, some vocabularies that we will be using:

``````USING: fry kernel locals make ranges sequences unicode.case
unicode.categories ;
``````

As part of the Factor language tutorial, the first program many people write in Factor is a word for detecting if something is a palindrome. The implementation of `palindrome?` (extended to support case-insensitive comparisons using the unicode vocabulary) looks like this:

``````: normalize ( str -- str' ) [ Letter? ] filter >lower ;

: palindrome? ( str -- ? ) normalize dup reverse = ;
``````

The “obvious” (but not that fast) way to solve the problem is to examine every possible substring, adding to a list if it is a palindrome. The list of palindrome substrings can then be used to answer the question. This is how we’ll implement it.

I thought it would be useful to split the problem into two steps. First, we need a way to enumerate all possible substrings (not including the “empty” substring), applying a quotation to each in turn.

``````:: each-subseq ( ... seq quot: ( ... x -- ... ) -- ... )
seq length [0,b] [
:> from
from seq length (a..b] [
:> to
from to seq subseq quot call( x -- )
] each
] each ;
``````

You can try this out in the listener, to see how it works:

``````IN: scratchpad "abc" [ . ] each-subseq
"a"
"ab"
"abc"
"b"
"bc"
"c"
``````

Once we have that, it’s pretty easy to build a word to look for palindrome substrings:

``````: palindromes ( str -- seq )
[
[ dup palindrome? [ , ] [ drop ] if ] each-subseq
] { } make ;
``````

We can use the `longest` word that I implemented for my anagrams post to find the longest palindrome substring:

``````: longest ( seq -- subseq )
dup 0 [ length max ] reduce '[ length _ = ] filter ;
``````

Using this on the 1169-character string from the original challenge, we find 52 unique palindromes of 2 or more characters. The longest palindrome substring I found was a 7-character sequence.