How to find the longest add-a-gram using SQL
July 17th, 2007 By Frank Zhou
The following is an interesting puzzle posted by itasofware on the web.
An “add-a-gram” is a sequence of words formed by starting with a 3-letter word, adding a letter and rearranging to form a 4-letter word, and so on. For example, here are add-a-grams of the words “CREDENTIALS” and “ANACHRONISM”:
ail + s =
sail + n =
nails + e =
aliens + t =
salient + r =
entrails + c =
clarinets + e =
interlaces + d =
CREDENTIALS (length 11)
—————————————–
mar + c =
cram + h =
march + s =
charms + o =
chromas + n =
monarchs + i =
harmonics + a =
maraschino + n =
ANACHRONISM (length 11)
given the dictionary WORD.LST (1.66MB), what is the longest add-a-gram?
————————————10G Solution————————————————–
Copy the word.lst from the web to a word.txt file on the database server ( /tmp directory)
Create a new IOT table by selecting the data from the external table by using a special query.
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;
——-Create an IOT table to speed up the query’s performance——–
CREATE TABLE IOT8
(len, sub_str, order_str, str,
PRIMARY KEY (len, sub_str, order_str, str )
) ORGANIZATION INDEX AS
SELECT Len, CAST(SUBSTR(order_str,1,LENGTH(order_str) -1)
AS VARCHAR2(30)) sub_str, CAST(order_str AS VARCHAR2(30)), str
FROM (
SELECT LENGTH(STR) Len, STR,
MAX(REPLACE(SYS_CONNECT_BY_PATH (ch , ','), ',' )) order_str
FROM
(
WITH INPUT AS (
SELECT STR , SUBSTR(STR, LEVEL , 1) ch,
row_number( )OVER (PARTITION BY STR ORDER BY SUBSTR(STR, LEVEL, 1)) rn
FROM ( SELECT STR FROM WORDS WHERE LENGTH(STR) >=3 )
CONNECT BY PRIOR STR = STR
AND LEVEL <= LENGTH(STR)
AND PRIOR dbms_random.string ('P', 10) IS NOT NULL)
SELECT STR, ch, rn FROM INPUT
)
START WITH rn = 1
CONNECT BY PRIOR STR = STR AND PRIOR rn = rn -1
GROUP BY STR
);
————————————————-10G SQL solution——————————
SELECT
CASE WHEN leaf_flag != 1
THEN path || ' + ' ||add_char||' = '
ELSE path || ' ( Length '|| LENGTH(path) || ' ) ' END AS NEW_STR
FROM
(SELECT SUBSTR(path,
INSTR(path, ',', 1, LEVEL ) + 1,
INSTR(path, ',', 1, LEVEL+1) -
INSTR(path, ',', 1, LEVEL) -1 ) path,
SUBSTR(last_char,
INSTR(last_char, ',', 1, LEVEL ) + 1,
INSTR(last_char, ',', 1, LEVEL+1) -
INSTR(last_char, ',', 1, LEVEL) -1 ) AS add_char,
CONNECT_BY_ISLEAF leaf_flag
FROM (
SELECT path||',' as path, length(substr(path, instr(path, ',', -1)+1 )) len,
ltrim(ORDER_path,',') ORDER_path,
substr(last_char,instr(last_char,',', 2))||',' as last_char
FROM (SELECT path,LENGTH(path) len, ORDER_path, last_char,
MAX(LENGTH(path)) OVER ( ) max_len
FROM (SELECT SYS_CONNECT_BY_PATH (STR, ',') path ,
SYS_CONNECT_BY_PATH (ORDER_STR, ',') ORDER_path,
SYS_CONNECT_BY_PATH (substr(ORDER_STR,
length(ORDER_STR)), ',') last_char
FROM IOT8
START WITH LEN >=3
CONNECT BY PRIOR LEN + 1 = LEN
AND PRIOR ORDER_STR = sub_str
)
)
WHERE len = max_len
)
CONNECT BY PRIOR path = path
AND INSTR (path, ',', 1, LEVEL+1) > 0
AND PRIOR dbms_random.string ('p', 10) IS NOT NULL
);
NEW_STR
------------------------------------------------------
ged + i =
gied + l =
gelid + m =
glimed + n =
melding + o =
modeling + r =
moldering + s =
smoldering + u =
smouldering ( Length 11 )
ged + i =
gied + l =
NEW_STR
--------------------------------------------------------
gelid + m =
glimed + n =
melding + o =
modeling + r =
remolding + s =
smoldering + u =
smouldering ( Length 11 )
ged + i =
gied + l =
gelid + m =
glimed + n =
NEW_STR
---------------------------------------------------------
mingled + o =
modeling + r =
moldering + s =
smoldering + u =
smouldering ( Length 11 )
ged + i =
gied + l =
gelid + m =
glimed + n =
mingled + o =
modeling + r =
NEW_STR
--------------------------------------------------------------
remolding + s =
smoldering + u =
smouldering ( Length 11 )
ged + i =
gied + l =
gelid + m =
midleg + n =
melding + o =
modeling + r =
moldering + s =
smoldering + u =
NEW_STR
--------------------------------------------------------------
smouldering ( Length 11 )
ged + i =
gied + l =
gelid + m =
midleg + n =
melding + o =
modeling + r =
remolding + s =
smoldering + u =
smouldering ( Length 11 )
ged + i =
NEW_STR
----------------------------------------------------------------
gied + l =
gelid + m =
midleg + n =
mingled + o =
modeling + r =
moldering + s =
smoldering + u =
smouldering ( Length 11 )
ged + i =
gied + l =
gelid + m =
NEW_STR
-----------------------------------------------------------------
midleg + n =
mingled + o =
modeling + r =
remolding + s =
smoldering + u =
smouldering ( Length 11 )
ged + i =
gied + l =
glide + m =
glimed + n =
melding + o =
NEW_STR
----------------------------------------------------------------
modeling + r =
moldering + s =
smoldering + u =
smouldering ( Length 11 )
ged + i =
gied + l =
glide + m =
glimed + n =
melding + o =
modeling + r =
remolding + s =
NEW_STR
-------------------------------------------------------------------
smoldering + u =
smouldering ( Length 11 )
ged + i =
gied + l =
glide + m =
glimed + n =
mingled + o =
modeling + r =
moldering + s =
smoldering + u =
smouldering ( Length 11 )
NEW_STR
------------------------------------------------------------------
ged + i =
gied + l =
glide + m =
glimed + n =
mingled + o =
modeling + r =
remolding + s =
smoldering + u =
smouldering ( Length 11 )
ged + i =
gied + l =
NEW_STR
---------------------------------------------------------------
glide + m =
midleg + n =
melding + o =
modeling + r =
moldering + s =
smoldering + u =
smouldering ( Length 11 )
ged + i =
gied + l =
glide + m =
midleg + n =
NEW_STR
---------------------------------------------------------------
melding + o =
modeling + r =
remolding + s =
smoldering + u =
smouldering ( Length 11 )
ged + i =
gied + l =
glide + m =
midleg + n =
mingled + o =
modeling + r =
NEW_STR
-------------------------------------------------------------------
moldering + s =
smoldering + u =
smouldering ( Length 11 )
ged + i =
gied + l =
glide + m =
midleg + n =
mingled + o =
modeling + r =
remolding + s =
smoldering + u =
NEW_STR
--------------------------------------------------------------------
smouldering ( Length 11 )
144 rows selected.