| |
Palindromic
Pangrams
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.
The
above description of palindromic pangrams is taken from ITA Software's
puzzles page.
They go on to suggest the following programming challenge:
Write a program to find a palindromic pangram.
Bonus (optional, very hard) find the shortest possible palindromic
pangram in terms of the total number of words or letters used.
The
listing below (based on the "permuter" class shown elsewhere)
is a serious effort to solve the above programming challenge, in
particular the "bonus" task of using the least number
of letters.
Notes:
The solution works by incrementally permuting, mirroring and splicing
a character string, looking for palindromic pangrams. An alphabet
of 26 characters results in a vast number of permutations: 26! (factorial).
There are probably more permutations than grains of sand in the
Sahara, so, although the solution works in theory, the Sun will
have burned out and destroyed the Earth long before the program
ever finishes, even if I were to rewrite it in C++ :)
Therefore,
to test the program, we use a much shorter alphabet of, say, "abcdef",
resulting in only 6! initial permutations (120). The results are
shown below. The most satisfactory palindromic pangram found using
just these 6 letters is "decaf aba faced" (an "aba"
is, apparently, a sleeveless garment woven from goat and camel hair).
This is the shortest possible (13 letters) using the test alphabet.
According to the Wrangler, there are no valid 11 or 12 character
palindromic pangrams using the test alphabet (11 being the shortest
technically possible).
Another
test run, this time using a 9 character alphabet of "abcdefghi",
produced the rather
nonsensical palindromic pangram of "ab dig feh chef gid ba"
(all "words" are in ITA Software's supplied dictionary
file).
The
results contain duplicate solutions. These could obviously be eliminated
by a trivial addition to the program.
I
have also created a heavily optimized version of the Wrangler that
eliminates non-viable permutations by indentifying and bypassing
character-triples not represented in the dictionary. This was, of
course, in retrospect, a foolish and (mostly) ineffective improvement,
since it does not fix the underlying problems associated with the
"permuter" approach. It is obvious that an entirely different
design is required to solve the problem with a full 26 character
alphabet in a non-apocalyptic timeframe. I'm working on an Ant
Colony Optimization-based approach.
Output results follow the listing.
//* Palindromic Pangram Wrangler
//* Andrew Carson 2006
import java.io.*;
import java.util.*;
public class PPWrangler {
public static void
main(String[] args) {
PPWrangler p = new
PPWrangler();
}
/* instance variables
*/
private static
String iAlphabet = "abcdef";
private static
int iOK = 4; // stop after finding
at least 4 pp's
private
Dictionary iDict;
private
String iSeed;
private
ArrayList iFound = new ArrayList();
/* constructor */
public
PPWrangler() {
System.out.println("Palindromic
Pangram Wrangler");
iDict = new
Dictionary();
Lexi extraChars
= new Lexi("a",
0);
while
(iFound.size() < iOK) {
iSeed
= iAlphabet + extraChars.next();
int[]
value = new int[iSeed.length()];
for
(int i = 0; i < iSeed.length();
i++) value[i] = i + 1;
permute(value,
0, iSeed.length());
}
System.out.println(">>>
found " + iFound.size()
+ " palindromic pangrams");
}
void
permute(int[] v, int
a, int b) {
start(v);
for
(int i = b - 2; i >= a; i--)
{
for
(int j = i + 1; j < b; j++)
{
swap(v,
i, j); permute(v, i + 1, b);
}
rotate(v,
i, b);
}
}
void
swap(int[] v, int
a, int b) {
int
t = v[a];
v[a] = v[b]; v[b]
= t;
}
void
rotate(int[] v, int
a, int b) {
int
t = v[a];
for
(int i = a; i < b - 1; i++)
v[i] = v[i + 1]; v[b - 1] = t;
}
void
start(int[] v) {
wrangle(mirror(toString(v),
0), 0);
}
String toString(int[]
v) {
String s = "";
for
(int i = 0; i < v.length; i++)
s += iSeed.charAt(v[i] - 1);
return
s;
}
String mirror(String s, int
e) {
for
(int i = s.length() - 2 + e;
i > -1; i--)
s
+= s.charAt(i);
return
s;
}
void
wrangle(String pan, int i) {
for
(int j = i + 1; j <= i + iDict.max(pan.charAt(i))
&&
j <= pan.length(); j++)
if
(iDict.isWord(pan.substring(i, j)))
if
(j == pan.length()) {
iFound.add(pan);
System.out.println(" --- \"" + pan
+ "\"");
}
else
wrangle(pan.substring(0, j) + " " +
pan.substring(j), j + 1);
}
private class
Dictionary {
private
String iWordList = "";
private
HashMap iMaxWordLengths = new
HashMap();
Dictionary() {
System.out.print(">>> Loading dictionary...
");
try { loadWordList(); } catch
(Exception e) { }
lookupLongWords();
System.out.println("loaded");
}
void
loadWordList()
throws FileNotFoundException,
IOException {
FileInputStream fin = new FileInputStream("c:\\word.lst");
int c, i = 0;
StringBuffer
b = null;
while
(true) {
if
(b == null) {
b = new StringBuffer(20000);
b.setLength(20000);
}
c
= fin.read();
if
(c == -1) { b.setLength(i); break;
}
b.setCharAt(i++,
(char)c);
if (i
== 20000) { iWordList += b; i = 0; b = null;
}
}
if
(b != null) iWordList += b;
fin.close();
iWordList
= "|" + iWordList.trim().replaceAll("\r\n",
"|") + "|";
}
void
lookupLongWords() {
for
(int i = 0; i < iAlphabet.length();
i++) {
String
alpha = Character.toString(iAlphabet.charAt(i));
for
(int j = 0;;) {
int
k = iWordList.indexOf('|' + alpha,
j);
if
(k < 0) break; else
j = k + 2;
while
(iWordList.charAt(j) != '|') { j++;
}
String
s = (String)iMaxWordLengths.get(alpha);
if
(s == null || Integer.parseInt(s)
< j - k - 1)
iMaxWordLengths.put(alpha,
Integer.toString(j - k - 1));
}
}
}
//
see if exists in the dictionary
boolean
isWord(String word) {
return
iWordList.indexOf("|" + word + "|")
> -1;
}
//
return the max word length starting with 'c'
int
max(char c) {
String
max = (String)iMaxWordLengths.get(Character.toString(c));
if
(max == null) return
0; else return Integer.parseInt(max);
}
}
private class
Lexi {
private
int iCount;
private
String iFirst, iCurr;
public
Lexi(String first, int c) {
iFirst = first; iCount = c; }
public
String current() { return iCurr;
}
public
String next() {
if
(iCount++ == 0) { return "";
}
if
(iCurr == null) { iCurr = iFirst;
return iCurr; }
int
digit = 0, ch;
do
{
ch
= iAlphabet.indexOf(iCurr.charAt(digit)) + 1;
if
(ch == iAlphabet.length()) ch = 0;
iCurr
= iCurr.substring(0, digit)
+ iAlphabet.charAt(ch) + iCurr.substring(digit + 1);
if
(ch == 0) digit++;
if
(digit == iCurr.length()) {
iCurr
+= iAlphabet.charAt(0); break;
}
}
while (ch == 0);
return
iCurr;
}
}
}
Palindromic Pangram Wrangler
>>> Loading dictionary... loaded
--- "ab decaf aced ba"
--- "ab face decaf ba"
--- "ba cafe de fa cab"
--- "ba decaf ace dab"
--- "ba decaf aced ab"
--- "ba de fa cafe dab"
--- "bade fa cafe dab"
--- "ba face decaf ab"
--- "ba cafe de fa cab"
--- "ba decaf ace dab"
--- "ba decaf aced ab"
--- "ba de fa cafe dab"
--- "bade fa cafe dab"
--- "ba face decaf ab"
--- "dace ba fa be cad"
--- "deaf ba cab fa ed"
--- "decaf aba faced"
--- "decaf aba faced"
--- "deaf ba cab fa ed"
--- "dace ba fa be cad"
--- "faced aba decaf"
--- "fa ed ba cab deaf"
--- "fed aba cab ad ef"
--- "fed abaca bad ef"
--- "fed aba cab ad ef"
--- "fed abaca bad ef"
--- "faced aba decaf"
--- "fa ed ba cab deaf"
--- "ab decaf aced ba"
--- "ab face decaf ba"
>>> found 30 palindromic pangrams
|
|
