发现一位专门用SQL解各种谜题的高人！

newkid

名字叫Frank Zhou, 似乎是中国人：
http://oraqa.com/author/frank-zhou/

最近OO发的几个趣味问题，他早就做过了。他写的SQL很对我的胃口，我准备陆续把一些有趣的问题转贴过来，比如这个：

http://oraqa.com/2008/02/01/how- ... ions-puzzle-in-sql/

Assuming you have enough coins of 1, 5, 10, 25 and 50 cents, how many ways are there to make change for a dollar?

用1分，5分,10分,25分,50分硬币凑成一元，总共有几种组合办法？

最直接了当的写法：
SELECT    '1*' ||c1 .cnt
       ||'+5*' ||c5 .cnt
       ||'+10*'||c10.cnt
       ||'+25*'||c25.cnt
       ||'+50*'||c50.cnt AS result
  FROM (SELECT ROWNUM-1 cnt FROM DUAL CONNECT BY ROWNUM-1<=100)  c1  ---- 利用CONNECT BY构造出0～100作为1分硬币的个数
      ,(SELECT ROWNUM-1 cnt FROM DUAL CONNECT BY ROWNUM-1<=20 )  c5
      ,(SELECT ROWNUM-1 cnt FROM DUAL CONNECT BY ROWNUM-1<=10 )  c10
      ,(SELECT ROWNUM-1 cnt FROM DUAL CONNECT BY ROWNUM-1<=4  )  c25
      ,(SELECT ROWNUM-1 cnt FROM DUAL CONNECT BY ROWNUM-1<=2  )  c50
WHERE 1 *c1 .cnt
     +5 *c5 .cnt
     +10*c10.cnt
     +25*c25.cnt
     +50*c50.cnt=100;


我用11GR2的写法：
WITH coins AS (
  SELECT 1 cents FROM DUAL
  UNION ALL SELECT 5 cents FROM DUAL
  UNION ALL SELECT 10 cents FROM DUAL
  UNION ALL SELECT 25 cents FROM DUAL
  UNION ALL SELECT 50 cents FROM DUAL
  )
,t(c1,c5,c10,c25,c50,cents,total_val) AS (
SELECT DECODE(c.cents,1,1,0)
      ,DECODE(c.cents,5,1,0)         
      ,DECODE(c.cents,10,1,0)         
      ,DECODE(c.cents,25,1,0)         
      ,DECODE(c.cents,50,1,0)         
      ,cents
      ,cents
  FROM coins c
UNION ALL
SELECT c1 + DECODE(c.cents,1,1,0)
      ,c5 + DECODE(c.cents,5,1,0)         
      ,c10+ DECODE(c.cents,10,1,0)         
      ,c25+ DECODE(c.cents,25,1,0)         
      ,c50+ DECODE(c.cents,50,1,0)         
      ,c.cents
      ,t.total_val + c.cents
  FROM t, coins c
WHERE t.total_val + c.cents<=100 AND t.cents<=c.cents
)
SELECT * FROM t WHERE total_val=100;

他的写法在11G通不过：
SELECT ltrim(max(str),',') combinations,
       rtrim(ltrim(replace(max(str_num),',','+'),'+'),'+') Sum,
       count(*) over () as counter
FROM
(SELECT sys_connect_by_path(str,', ') str, rownum rn,
        translate(sys_connect_by_path(str_num,','),
                  chr(0)||'ABCDE',chr(0))||',' AS str_num
FROM
(SELECT str_num, str, to_number(substr(str_num,0,length(str_num)-1)) n,
        substr(str_num,length(str_num)) coin_type
  FROM
(SELECT LEVEL||'A' str_num ,   LEVEL||' Penny' AS str
   FROM dual CONNECT BY LEVEL <=100
UNION ALL
SELECT LEVEL*5||'B' str_num,  LEVEL||' Nickel'
   FROM dual CONNECT BY LEVEL*5 <=100
UNION ALL
SELECT LEVEL*10||'C' str_num, LEVEL||' Dime'
   FROM dual CONNECT BY LEVEL*10 <=100
UNION ALL
SELECT LEVEL*25||'D' str_num, LEVEL||' Quarter'
   FROM dual CONNECT BY LEVEL*25 <=100
UNION ALL
SELECT LEVEL*50||'E' str_num, LEVEL||' Half D$'
   FROM dual CONNECT BY LEVEL*50<=100
)
)
WHERE
CASE LEVEL
WHEN  1 THEN CASE WHEN n = 100 THEN 1 END
WHEN  2 THEN CASE WHEN n + PRIOR  n =100 THEN 1 END
WHEN  3 THEN CASE WHEN CONNECT_BY_ROOT n + PRIOR n + n =100 THEN 1 END
ELSE  1 END =1
CONNECT BY PRIOR coin_type < coin_type
AND
CASE LEVEL
WHEN 2 THEN CASE WHEN n + PRIOR  n <=100 THEN 1 END
WHEN 3 THEN CASE WHEN CONNECT_BY_ROOT n + PRIOR n + n <=100 THEN 1 END
WHEN 4 THEN CASE WHEN CONNECT_BY_ROOT n + PRIOR n + n <96   THEN 1 END
WHEN 5 THEN CASE WHEN CONNECT_BY_ROOT n + PRIOR n + n <=85  THEN 1 END
ELSE 1 END =1
)
CONNECT BY PRIOR rn = rn
AND INSTR(str_num,',', 1,LEVEL+1) > 0
AND PRIOR dbms_random.string('p',10) IS NOT NULL
GROUP BY rn
HAVING SUM(TO_NUMBER(SUBSTR(str_num,
           INSTR(str_num,',', 1, LEVEL) + 1,
           INSTR(str_num,',', 1, LEVEL+1) -
           INSTR(str_num,',', 1, LEVEL) -1))) = 100 ;

WHEN 3 THEN CASE WHEN CONNECT_BY_ROOT n + PRIOR n + n <=100 THEN 1 END
                      *
ERROR at line 38:
ORA-30007: CONNECT BY ROOT operator is not supported in the START WITH or in the CONNECT BY condition

印象中只有某个版本允许在CONNECT BY条件中使用CONNECT_BY_ROOT。

[ 本帖最后由 newkid 于 2010-6-29 03:44 编辑 ]

newkid

在美国，我已经给他发了邮件不知道他会不会理我。如果能邀请到这里来就好了。

dingjun123

原帖由 newkid 于 2010-6-24 23:24 发表
在美国，我已经给他发了邮件不知道他会不会理我。如果能邀请到这里来就好了。

这样的高人要能来，那真是太好了啊

dingjun123

我在10G R2下测试可以，292种，11G不行？？

dingjun123

这些人把SQL当作无所不能的东西啊，佩服,连除法过程都被整出来了，想起了我才以前在论坛看到整柱状图的，创意无处不在啊
How to solve the Feynman’s Puzzle in SQL
June 9th, 2010 By Frank Zhou

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

Feynman’s Puzzle

This Puzzles was proposed by Richard Feyman ( An American physicist)

‘A’ can be any digit; each ‘.’ can be any digit from 0 through 9 except ‘A’. There is only one solution.


         ..A.
    ---------
.A. ) ....A..
      ..AA
      ----
       ...A
        ..A
       -----
        ....
        .A..
        -----
         ....
         ....
         ----
            0

COLUMN str FORMAT  A38
COLUMN d_e_A_f FORMAT A8
COLUMN b_A_c  FORMAT  A8

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

WITH DATA1 AS
(SELECT LEVEL n FROM DUAL CONNECT BY LEVEL < 10 ),
DATA2 AS
(SELECT LEVEL-1 n FROM DUAL CONNECT BY LEVEL  < 11 )
SELECT d_e_A_f||chr(10)||'     ------------'||chr(10)||b_A_c||'  )'||Div as str, b_A_c, d_e_A_f
FROM
(SELECT b.n|| A.n|| c.n as b_A_c ,  d.n||e.n||A.n||f.n  as d_e_A_f , to_number(b.n|| A.n|| c.n )* to_number(d.n||e.n||A.n||f.n) as Div
FROM data2 A,  data1 b, data2 c,  data1 d,  data2 e, data2 f
WHERE b.n != A.n
AND   c.n != A.n
AND   d.n != A.n
AND   e.n != A.n
AND   f.n != A.n
AND length ((b.n * 100 + A.n *10 + c.n) *  (d.n *1000 + e.n *100 + A.n *10 + f.n)) =7
AND to_number(substr((b.n * 100 + A.n *10 + c.n) *  (d.n *1000 + e.n *100 + A.n *10 + f.n), 5, 1 ) ) = A.n
AND to_number(substr((b.n * 100 + A.n *10 + c.n) * d.n, 3, 2 ))  = to_number(A.n||A.n)
AND to_number(substr((b.n * 100 + A.n *10 + c.n)*e.n, 3, 1 )) = A.n
AND to_number(substr((b.n * 100 + A.n *10 + c.n) * A.n , 2, 1 ) ) = A.n
AND e.n < d.n
);

STR                                    B_A_C      D_E_A_F
---------------------------           --------    --------
         7289                           484        7289
     ------------
484  )3527876

SQL>

[ 本帖最后由 dingjun123 于 2010-6-25 00:13 编辑 ]

newkid

http://oraqa.com/2010/06/08/how- ... n-sql/#comment-1000

How to solve the Multiple Dwellings Puzzle in SQL

June 8th, 2010 By Frank Zhou

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

Multiple Dwellings
Baker, Cooper, Fletcher, Miller and Smith live on different floors of an apartment house that contains only five floors.
Baker does not live on the top floor. Cooper does not live on the bottom floor.
Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper.
Smith does not live on a floor adjacent to Fletcher’s.
Fletcher does not live on a floor adjacent to Cooper’s. Where does everyone live?

Baker, Cooper, Fletcher, Miller and Smith住在一座房子的不同楼层。
Baker 不住顶层。Cooper不住底层。
Fletcher 既不住顶层也不住底层。Miller住得比Cooper高。
Smith住的楼层和Fletcher不相邻。
Fletcher住的楼层和Cooper不相邻。

我的答案：

WITH comb as (  
       SELECT INSTR(p,'1') AS Baker
             ,INSTR(p,'2') AS Cooper      
             ,INSTR(p,'3') AS Fletcher      
             ,INSTR(p,'4') AS Miller  
             ,INSTR(p,'5') AS Smith     
         FROM ( SELECT REPLACE(SYS_CONNECT_BY_PATH(rn,'\'),'\') AS p
                  FROM (SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=5)
                 WHERE LEVEL=5
                 CONNECT BY NOCYCLE LEVEL<=5 AND rn<>PRIOR rn
                 )
          )
SELECT * FROM comb
WHERE Baker<>5
      AND Cooper<>1
      AND Fletcher NOT IN (1,5)
      AND Miller > Cooper
      AND Smith-Fletcher NOT IN (1,-1)
      AND Cooper-Fletcher NOT IN (1,-1);


     BAKER     COOPER   FLETCHER     MILLER      SMITH
---------- ---------- ---------- ---------- ----------
         3          2          4          5          1

这比以前这个题目容易多了：
http://www.itpub.net/thread-1253844-1-1.html

newkid

原帖由 dingjun123 于 2010-6-25 00:01 发表
我在10G R2下测试可以，292种，11G不行？？

确实不行，印象中10GR2的文档也说了不允许在CONNECT BY中使用CONNECT_BY_ROOT.

dingjun123

原帖由 newkid 于 2010-6-25 00:53 发表

确实不行，印象中10GR2的文档也说了不允许在CONNECT BY中使用CONNECT_BY_ROOT.

10G R2文档上说
CONNECT_BY_ROOT
CONNECT_BY_ROOT is a unary operator that is valid only in hierarchical queries.
When you qualify a column with this operator, Oracle returns the column value using
data from the root row. This operator extends the functionality of the CONNECT BY
[PRIOR] condition of hierarchical queries.
Restriction on CONNECT_BY_ROOT You cannot specify this operator in the START
WITH condition or the CONNECT BY condition
这人是不是利用了10G R2的BUG啊，我在10G R2上测试竟然通过，晕

newkid

又做了一个：
http://oraqa.com/2010/06/08/how- ... grams-puzzle-in-sql

newkid

再来一个：
http://oraqa.com/2010/06/02/how-to-solve-the-dodgson’s-doublets-puzzle-in-sql

给定一个词典和两个单词。每次改变单词中的一个字母，改过的单词必须也是字典中存在的。任务是求出从开始单词到结束单词的变化路径。

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'

我写的：
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);

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


从他那里偷学了utl_match.edit_distance, xmltable:
------------------------------------------------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>

[ 本帖最后由 newkid 于 2010-6-25 02:34 编辑 ]