Puzzles/Palindromic Pangram

From http://www.itasoftware.com/careers/eng/job1.php

A palindrome is a sequence of words like "lid off a daffodil" or "shallot ayatollahs" that uses the same letters reading backwards as forwards. The words need not form a meaningful or grammatical sentence.

A palindromic pangram is a multi-word palindrome that includes all 26 letters of the alphabet. Write a program to find a palindromic pangram. Use this dictionary: File:Itawords.txt (1.8MB), originally downloaded from http://www.itasoftware.com/careers/WORD.LST.

Bonus (optional, very hard!): find the shortest possible palindromic pangram in terms of the total number of words or letters used.

A Solution from 2004-02-23

I downloaded the words file and crunched it into a boxed list of words.

   read=: 1!:1
   # t=: read <'\ijs\itawords.txt'
1749989
   a.i._10{.t
10 122 121 122 122 121 118 97 115 10
   # words=: <;._2 t
173528

If the palindromic words contain all the letters from a-z, we are done. How close are we to that?

   # p=: words #~  words = |.&.>words
103
   /:~ ~. ; p
abcdefghiklmnoprstuvwxy
   ] alp=: a. {~ 97+i.26
abcdefghijklmnopqrstuvwxyz
   alp -. /:~ ~. ; p
jqz

The problem has just become much smaller and manageable -- we just need to find a palindrome involving j, q, and z, and then surround it with palindromic words, and we are done.

After a few moments of thought, I came up with 'ooze he zoo' for the letter z.

Now compute all words containing j and q:

   # j=: words #~ 'j'&e.&>words
2467
   # q=: words #~ 'q'&e.&>words
2541

I stared at the short words involving j:

   _10]\ j #~ 5>:#&>j

and found that raj is a word. So: 'raj jar' for the letter j. Similarly, staring at the short words for q,

   _10]\ q #~ 5>:#&>q

I found that suq is a word. So: 'suq us' for the letter q. This sequence must sit in the middle of the overall solution. That means 'ooze he zoo' must be replaced.

'ooze e zoo' is a pretty good place to start: we just need a palindrome which can have an e tacked onto the end and still use valid words. 'am' and 'mae' are both words, so 'ooze am mae zoo' would work for the letter z. Putting the q j z solutions together:

   x=: 'raj ooze am suq us mae zoo jar'

Now we just need to tack on palindromic words to the front and to the back to make up the rest of the letters. I came up with:

   p5=: 'bib civic dewed gag huh kayak oxo pullup refer tenet '
   y=: p5 , x , |. p5
   y
bib civic dewed gag huh kayak oxo pullup refer tenet raj ooze am suq
     us mae zoo jar tenet refer pullup oxo kayak huh gag dewed civic bib
   # y
136

Now apply some checks on the solution:

test=: 3 : 0  NB. test for palindromic pangram
 assert. (-:|.) y-.' '   NB. palindromic
 assert. alp e. y        NB. pangramic
 assert. (;:y) e. words  NB. in dictionary
 1
)

   test y
1

Strictly speaking, I didn't really solve the problem, because I didn't write a program to do it. :) Moreover, the bonus problem, finding the shortest possible palindromic pangram in terms of the total number of words or letters used, remains unsolved. I would be more motivated to solve it if the quality of word list is higher. (e.g. The word list does not include a or i or o.)

---

Contributed by Roger Hui.