How to find the shortest possible palindromic pangram in a SQL statement
July 11th, 2007 By Frank Zhou
The following is an interesting puzzle posted by ItaSofware on the web.
A palindrome is a sequence of words that uses the same letters reading backwards as forwards. 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: WORD.LST (1.66MB). find the shortest possible palindromic pangram in terms of the total number of words or letters used.
The following SQL patterns can be used to find the shortest possible palindromic pangram in a single SQL statement.
10G Solution:
Copy the word.lst from the web to a word.txt file on the database server ( /tmp directory). You can select directly from the external table or insert the data to a real table and then selecting from the table instead.
create or replace directory tmp as '/tmp'
CREATE TABLE words (str VARCHAR2(38))
ORGANIZATION EXTERNAL
(
TYPE ORACLE_LOADER
DEFAULT DIRECTORY tmp
ACCESS PARAMETERS
(
records delimited by newline
fields terminated by whitespace
missing field values are null
( str
)
)
LOCATION ('word.txt')
)
REJECT LIMIT UNLIMITED;
Shortest possible palindromic pangram in terms of the total number of letters
SELECT LENGTH(REPLACE(fin_str,' ')) Letter_cnt,
LENGTH(fin_str)-LENGTH(REPLACE(fin_str,' ', ''))+1
as word_cnt,
CASE WHEN REPLACE(fin_str,' ') = REVERSE(REPLACE(fin_str,' '))
THEN 'Forward_Matches_backward!'
ELSE 'NO' END AS flag_match,
fin_str
FROM
(SELECT str, re, fin_str
FROM(
WITH BASE AS (
SELECT str, REVERSE(str) as rev, SUBSTR(str,1,1) as ch FROM Words
),
data_pair AS
(SELECT str, rev, ch
FROM ( SELECT str, rev, ch,
CASE WHEN COUNT(*) OVER (PARTITION BY
GREATEST(str, rev),LEAST(str,rev)) -
COUNT(*) OVER (PARTITION BY str,rev)= 1
THEN 'T'
ELSE 'F'
END AS flag
FROM BASE
)
WHERE flag = 'T'
),
DATA AS (
SELECT str, re, cnt, ch
FROM (SELECT str, re, cnt, ch,
MIN(str) OVER (PARTITION BY ch) min_str
FROM(SELECT str, rev re, cnt, ch,
MIN(cnt) OVER (PARTITION BY ch) min_len
FROM (SELECT str, rev, ch,
COUNT(DISTINCT SUBSTR(str,LEVEL,1)) cnt
FROM (SELECT str, rev, ch FROM data_pair)
CONNECT BY PRIOR str = str
AND LEVEL <= LENGTH(str)
AND PRIOR DBMS_RANDOM.STRING ('p',10) IS NOT NULL
GROUP BY ch,str, rev
)
)
WHERE cnt = min_len
)
WHERE str = min_str
),
miss_ch AS (
SELECT CHR(ASCII('a')+LEVEL-1) AS ch
FROM dual CONNECT BY LEVEL <ASCII('z') - ASCII('a') + 2
MINUS
SELECT ch FROM data_pair
),
miss_data AS (
SELECT str, (SELECT ch FROM miss_ch WHERE ROWNUM = 1) ||re AS re , cnt
FROM (SELECT str, re, COUNT(DISTINCT SUBSTR(str,LEVEL,1)) cnt
FROM (SELECT w2.str, w2.rev AS re
FROM BASE w1, BASE w2
WHERE w1.ch IN (SELECT ch FROM miss_ch)
AND w2.str = SUBSTR(w1.rev,1,LENGTH(w1.rev)-1)
)
CONNECT BY PRIOR str = str
AND LEVEL <= LENGTH(str)
AND PRIOR DBMS_RANDOM.STRING ('p',10) IS NOT NULL
GROUP BY str, re
ORDER BY cnt DESC
)
WHERE ROWNUM =1
)
SELECT str, re, cnt, to_number(null) as flag FROM data
UNION ALL
SELECT str, re, cnt, 1 FROM miss_data
)
MODEL
DIMENSION BY (ROW_NUMBER( ) OVER (ORDER BY cnt DESC, str DESC) id )
MEASURES
(CAST(NULL AS VARCHAR2(3999)) tmp_str, str, re,
CAST(NULL AS VARCHAR2(3999)) fin_str, flag )
RULES
(tmp_str[ANY] ORDER BY id =
CASE WHEN str[cv()-1] IS NULL
THEN str[cv()]||'#'||re[cv()]
ELSE CASE WHEN flag[cv()] =1
THEN substr(tmp_str[cv()-1],1,
instr(tmp_str[cv()-1],'#')-1)||' '||str[cv()]
||' '||re[cv()]||' ' ||
substr(tmp_str[cv()-1],
instr(tmp_str[cv()-1],'#')+1)
ELSE CASE WHEN instr(tmp_str[cv()-1],
SUBSTR(str[cv()],1,1))<1
THEN str[cv()]||' '||tmp_str[cv()-1]||
' '||re[cv()]
ELSE tmp_str[cv()-1]
END
END
END,
fin_str[ANY] ORDER BY id = CASE WHEN str[cv()+1] IS NULL
THEN tmp_str[cv()]
END
)
)
WHERE fin_str IS NOT NULL;
LETTER_CNT WORD_CNT FLAG_MATCH FIN_STR
----------- ------------ ----------- --------------
77 28 Forward_Matches_backward!
de ha la na wo cam fer gab jar kay vat xis zaps piu
quip spaz six tav yak raj bag ref mac ow an al ah ed
Shortest possible palindromic pangram in terms of the total number of words
SELECT LENGTH(REPLACE(fin_str,' ')) Letter_cnt,
LENGTH(fin_str)-LENGTH(REPLACE(fin_str,' ', ''))+1
as word_cnt,
CASE WHEN REPLACE(fin_str,' ') = REVERSE(REPLACE(fin_str,' '))
THEN 'Forward_Matches_backward!'
ELSE 'NO' END AS flag_match,
fin_str
FROM
(SELECT str, re, fin_str
FROM(
WITH BASE AS (
SELECT str, REVERSE(str) as rev, SUBSTR(str,1,1) as ch FROM Words
),
data_pair AS
(SELECT b2.str, b2.rev, b2.ch
FROM BASE b1, BASE b2
WHERE b1.rev =b2.str
AND b1.str != b2.str
),
DATA AS (
SELECT str, re, cnt, ch
FROM (SELECT str, re, cnt, ch,
MIN(str) OVER (PARTITION BY ch) min_str
FROM(SELECT str, rev re, cnt, ch,
MAX(cnt) OVER (PARTITION BY ch) max_len
FROM (SELECT str, rev, ch,
COUNT(DISTINCT SUBSTR(str,LEVEL,1)) cnt
FROM (SELECT str, rev, ch FROM data_pair)
CONNECT BY PRIOR str = str
AND LEVEL <= LENGTH(str)
AND PRIOR DBMS_RANDOM.STRING ('p',10) IS NOT NULL
GROUP BY ch,str, rev
)
)
WHERE cnt = max_len
)
WHERE str = min_str
),
miss_ch AS (
SELECT CHR(ASCII('a')+LEVEL-1) AS ch
FROM dual CONNECT BY LEVEL <ASCII('z') - ASCII('a') + 2
MINUS
SELECT ch FROM data_pair
),
miss_data AS (
SELECT str, (SELECT ch FROM miss_ch WHERE ROWNUM = 1) ||re AS re, cnt
FROM (SELECT str, re, COUNT(DISTINCT SUBSTR(str,LEVEL,1)) cnt
FROM (SELECT w2.str, w2.rev re
FROM BASE w1, BASE w2
WHERE w1.ch IN (SELECT ch FROM miss_ch)
AND w2.str = SUBSTR(w1.rev,1,LENGTH(w1.rev)-1)
)
CONNECT BY PRIOR str = str
AND LEVEL <= LENGTH(str)
AND PRIOR DBMS_RANDOM.STRING ('p',10) IS NOT NULL
GROUP BY str, re
ORDER BY cnt
)
WHERE ROWNUM =1
)
SELECT str, re, cnt, to_number(null) as flag FROM data
UNION ALL
SELECT str, re, cnt, 1 FROM miss_data
)
MODEL
DIMENSION BY (ROW_NUMBER( ) OVER (ORDER BY cnt DESC, str DESC) id )
MEASURES
(CAST(NULL AS VARCHAR2(3999)) tmp_str, str, re,
CAST(NULL AS VARCHAR2(3999)) fin_str, flag)
RULES
(tmp_str[ANY] ORDER BY id =
CASE WHEN str[cv()-1] IS NULL
THEN str[cv()]||'#'||re[cv()]
ELSE CASE WHEN flag[cv()] =1
THEN substr(tmp_str[cv()-1],1,
instr(tmp_str[cv()-1],'#')-1)
||' '||str[cv()]||' '||re[cv()]||' '
||substr(tmp_str[cv()-1],
instr(tmp_str[cv()-1],'#')+1)
ELSE CASE WHEN instr(tmp_str[cv()-1],
SUBSTR(str[cv()],1,1))<1
THEN str[cv()]||' '||tmp_str[cv()-1]
||' '||re[cv()]
ELSE tmp_str[cv()-1]
END
END
END,
fin_str[ANY] ORDER BY id = CASE WHEN str[cv()+1] IS NULL
THEN tmp_str[cv()]
END
)
)
WHERE fin_str IS NOT NULL;
LETTER_CNT WORD_CNT FLAG_MATCH FIN_STR
----------- -------- ------------------------- --------
111 24 Forward_Matches_backward!
jar vat xis yaps zaps habus pacer degami gateman wolfer stinker ta
qat reknits reflow nametag imaged recap subah spaz spay six tav raj