OraQA

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>

Filed under General, SQL. Follow any responses to this entry through this RSS 2.0 feed.

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

newkid Says:
June 24th, 2010 at 9:19 am

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

newkid Says:
June 24th, 2010 at 9:26 am

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);

Frank Zhou Says:
June 24th, 2010 at 11:22 am
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
newkid Says:
June 24th, 2010 at 12:41 pm
oops…I missed that one!

newkid Says:
June 24th, 2010 at 2:07 pm

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

newkid Says:
June 24th, 2010 at 2:09 pm

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;

newkid Says:
June 25th, 2010 at 5:47 am
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

You must be logged in to post a comment.

RSS feed for comments on this question

« How to solve the Landmarks Puzzle in SQL

How to solve the Anagrams Puzzle in SQL »

Oracle Question and Answer

Categories

Links

Oracle News

How to solve the Dodgson’s Doublets Puzzle in SQL

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

Leave a Reply