OraQA

Oracle Question and Answer

  • Do you have a solution to a problem? Do you have an unanswered question? Login and share it with the Oracle community. More...

Oracle News


Entries RSS feed

Comments RSS feed

How to solve the Dodgson’s Doublets Puzzle in SQL

June 2nd, 2010 By Frank Zhou

The following is an interesting puzzle posted on the programming praxis website:

Dodgson’s Doublets
Charles Dodgson was an English author, mathematician and logician of the nineteenth century;
In 1879, Dodgson published the Doublets word game in the Vanity Fair magazine:

The rules of the Puzzle are simple enough. Two words are proposed, of the same length; and the Puzzle consists in linking these together by interposing other words, each of which shall differ from the next word in one letter only. That is to say, one letter may be changed in one of the given words, then one letter in the word so obtained, and so on, till we arrive at the other given word. The letters must not be interchanged among themselves, but each must keep to its own place. As an example, the word ‘head’ may be changed into ‘tail’ by interposing the words ‘heal, teal, tell, tall’. I call the given words ‘a Doublet’, the interposed words ‘Links’, and the entire series ‘a Chain’, of which I here append an example:

H E A D
h e a l
t e a l
t e l l
t a l l
T A I L

Write a program that takes two words and finds a chain between them.


create table dictionary ( word varchar2(38) PRIMARY KEY );

insert into dictionary values ('HEAD');
insert into dictionary values ('heal');
insert into dictionary values ('teal');
insert into dictionary values ('tell');
insert into dictionary values ('tall');
insert into dictionary values ('TAIL');
insert into dictionary values ('toll');
commit;


COLUMN str FORMAT  A38
variable begin_str varchar2(38)
variable end_str varchar2(38)
exec :begin_str:='head'
exec :end_str:='tail'





------------------------------------------------SQL Solution-----------------------------------------------



WITH data as (
SELECT word
FROM  dictionary  
WHERE length(word) = length(:begin_str)
), 
Links as 
(SELECT path
 FROM 
 (SELECT ltrim(sys_connect_by_path( word, ','), ',') path
  FROM data 
  WHERE upper(word) = upper(:end_str)
  START WITH upper(word) = upper(:begin_str)
  CONNECT BY NOCYCLE  utl_match.edit_distance(upper(PRIOR word), upper(word) ) =1
  ORDER BY LEVEL
 )
 WHERE ROWNUM = 1
)
SELECT  rownum as rn, trim(column_value) str
FROM links a, xmltable(('"'||replace(a.path, ',', '","')||'"'));



        RN STR
---------- --------------------------------------
         1 HEAD
         2 heal
         3 teal
         4 tell
         5 tall
         6 TAIL

6 rows selected.

SQL>

--------------------------------SQL Solution using Recursive Subquery Factoring-------------------------------------


WITH data AS (
SELECT word  FROM dictionary 
WHERE length(word) = length(:begin_str)
), 
Links (path, h_level, word) AS
(SELECT word, 1 , word
 FROM data 
 WHERE upper(word) = upper(:begin_str)
 UNION ALL 
 SELECT d.path||','||e.word as path, d.h_level+1 AS h_level, e.word
 FROM Links d, data e
 WHERE utl_match.edit_distance(upper(d.word), upper(e.word) ) = 1
)
SEARCH DEPTH FIRST BY word SET seq
CYCLE word SET is_cycle to '1' DEFAULT '0'
SELECT ROWNUM as rn, trim(COLUMN_VALUE) str 
FROM 
(SELECT path 
 FROM
 (SELECT path FROM Links
  WHERE upper(word) = upper(:end_str)
  AND is_cycle = 0
  ORDER BY  h_level
 )
 WHERE ROWNUM = 1 ) a, xmltable(('"'||replace(a.path, ',', '","')||'"'));


        RN STR
---------- --------------------------------------
         1 HEAD
         2 heal
         3 teal
         4 tell
         5 tall
         6 TAIL

6 rows selected.

SQL>

7 Responses to “How to solve the Dodgson’s Doublets Puzzle in SQL”

  1. newkid Says:
    SELECT chain
      FROM (
    SELECT SYS_CONNECT_BY_PATH(word,'->') chain,LEVEL lvl,word
      FROM dictionary 
     START WITH UPPER(word) = UPPER(:begin_str)
     CONNECT BY NOCYCLE wordPRIOR word AND LENGTH(TRANSLATE(UPPER(word),'$'||UPPER(PRIOR word),'$'))=1
    )
    WHERE UPPER(word) = UPPER(:end_str);
    
    CHAIN
    -------------------------------------------------------------
    ->HEAD->heal->tall->TAIL
    ->HEAD->heal->tall->teal->TAIL
    ->HEAD->heal->tall->tell->teal->TAIL
    ->HEAD->heal->tall->toll->tell->teal->TAIL
    ->HEAD->heal->teal->TAIL
    ->HEAD->heal->teal->toll->tall->TAIL
    ->HEAD->heal->teal->toll->tell->tall->TAIL
    ->HEAD->heal->tell->tall->TAIL
    ->HEAD->heal->tell->tall->teal->TAIL
    ->HEAD->heal->tell->teal->TAIL
    ->HEAD->heal->tell->teal->toll->tall->TAIL
    ->HEAD->heal->tell->toll->tall->TAIL
    ->HEAD->heal->tell->toll->tall->teal->TAIL
    
  2. newkid Says:

    Forgot to check the length in connect by:

    SELECT chain
      FROM (
    SELECT SYS_CONNECT_BY_PATH(word,'->') chain,LEVEL lvl,word
      FROM dictionary 
     START WITH UPPER(word) = UPPER(:begin_str)
     CONNECT BY NOCYCLE wordPRIOR word AND LENGTH(TRANSLATE(UPPER(word),'$'||UPPER(PRIOR word),'$'))=1
             AND LENGTH(word) = LENGTH(PRIOR word)
    )
    WHERE UPPER(word) = UPPER(:end_str);
    
  3. Frank Zhou Says:

    Hi NewKid,

    Please read all the rules carefully.

    The letters must not be interchanged among themselves,
    **** but each must keep to its own place ***

    The translate can not guarantee the “position” of the letters.

    Thanks for give this problem a try !

    Frank

  4. newkid Says:

    oops…I missed that one!

  5. newkid Says:
    WITH w AS (
    SELECT word
          ,UPPER(SUBSTR(word,rn,1)) c 
          ,rn
      FROM dictionary, (SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=(SELECT MAX(LENGTH(word)) FROM dictionary))
     WHERE rn<=LENGTH(word)
    )
    ,l AS (SELECT w1.word w1,w2.word w2
      FROM w w1,w w2
     WHERE LENGTH(w1.word)=LENGTH(w2.word) AND w1.rn=w2.rn
           AND w1.word != w2.word
    GROUP BY w1.word,w2.word
    HAVING COUNT(CASE WHEN w1.c=w2.c THEN 1 END)=MAX(LENGTH(w1.word))-1
    )
    SELECT *
      FROM (
    SELECT SYS_CONNECT_BY_PATH(w1,',')||','||:end_str
     FROM l
    WHERE UPPER(w2) = UPPER(:end_str)
     START WITH UPPER(w1) = UPPER(:begin_str)
    CONNECT BY NOCYCLE w1 = PRIOR w2 AND UPPER(PRIOR w2) != UPPER(:end_str)
    ORDER BY LEVEL
    )
    WHERE ROWNUM=1;
    
    
    SYS_CONNECT_BY_PATH(W1,',')||','||:END_STR
    -------------------------------------------------
    ,HEAD,heal,teal,tell,tall,tail
     
  6. newkid Says:
    WITH w AS (
    SELECT word
          ,UPPER(SUBSTR(word,rn,1)) c
          ,rn
      FROM dictionary, (SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=(SELECT MAX(LENGTH(word)) FROM dictionary))
     WHERE rn<=LENGTH(word)
    )
    ,l AS (SELECT w1.word w1,w2.word w2
      FROM w w1,w w2
     WHERE LENGTH(w1.word)=LENGTH(w2.word) AND w1.rn=w2.rn
           AND w1.word != w2.word
    GROUP BY w1.word,w2.word
    HAVING COUNT(CASE WHEN w1.c=w2.c THEN 1 END)=MAX(LENGTH(w1.word))-1
    )
    SELECT *
      FROM (
    SELECT SYS_CONNECT_BY_PATH(w1,',')||','||:end_str
     FROM l
    WHERE UPPER(w2) = UPPER(:end_str)
     START WITH UPPER(w1) = UPPER(:begin_str)
    CONNECT BY NOCYCLE w1 = PRIOR w2 AND UPPER(PRIOR w2) != UPPER(:end_str)
    ORDER BY LEVEL
    )
    WHERE ROWNUM=1;
    
  7. newkid Says:

    WITH w AS (
    SELECT word
    ,UPPER(SUBSTR(word,rn,1)) c
    ,rn
    FROM dictionary, (SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=(SELECT MAX(LENGTH(word)) FROM dictionary))
    WHERE rn<=LENGTH(word)
    )
    ,l AS (SELECT w1.word w1,w2.word w2
    FROM w w1,w w2
    WHERE LENGTH(w1.word)=LENGTH(w2.word) AND w1.rn=w2.rn
    AND w1.word<>w2.word
    GROUP BY w1.word,w2.word
    HAVING COUNT(CASE WHEN w1.c=w2.c THEN 1 END)=MAX(LENGTH(w1.word))-1
    )
    SELECT *
    FROM (
    SELECT SYS_CONNECT_BY_PATH(w1,’,')||’,'||:end_str
    FROM l
    WHERE UPPER(w2) = UPPER(:end_str)
    START WITH UPPER(w1) = UPPER(:begin_str)
    CONNECT BY NOCYCLE w1 = PRIOR w2 AND UPPER(PRIOR w2) != UPPER(:end_str)
    ORDER BY LEVEL
    )
    WHERE ROWNUM=1;

    SYS_CONNECT_BY_PATH(W1,’,')||’,'||:END_STR
    ————————————————-
    ,HEAD,heal,teal,tell,tall,tail

Leave a Reply

You must be logged in to post a comment.

RSS feed for comments on this question