# Puzzles/Palindromic Pangram

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