Palindromic Pangrams
ITA SOFTWARE'S PALINDROMIC PANGRAM PUZZLE
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.
In the past, they suggested the following programming challenge.
(Note: their current version of this challenge is slightly different, making my approach here somewhat inapplicable.)
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, finding the shortest possible palindromic pangram in terms of the total number of letters used.
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
//* Java SE 6 Version 2009
package www;
import java.io.*;
import java.util.*;
public class PPWrangler {
public static void main(String[] args) {
new PPWrangler("abcdef");
}
// instance variables
private static String iAlphabet;
private static int iOK = 4; // find at least 4 pp's
private Dictionary iDict;
private String iSeed;
private ArrayList<String> iFound = new ArrayList<String>();
// constructor
public PPWrangler(String alphabet) {
System.out.println("Palindromic Pangram Wrangler");
iAlphabet = alphabet;
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<String, String> iMaxWordLengths =
new HashMap<String, String>();
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 = 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
|
HOME
INFO
CONTACT
MORE
FOOLISHNESS
LINKS
SITE MAP
|
