Puzzleup 2010 比赛快开始了，大家用SQL解答啊

〇〇

xeon   
   
WITH p AS (
SELECT pos,l
   FROM (SELECT ROWNUM pos FROM DUAL CONNECT BY ROWNUM<=10),(SELECT ROWNUM l FROM DUAL CONNECT BY ROWNUM<=3)
  )
,d3 as
(select rownum rn,num, numnum from
    (select num, power(num,2) numnum from (select level+99 num from dual connect by level<=999-100))
    where  (substr(num,1,1)<>substr(num,2,1) and substr(num,1,1)<>substr(num,3,1) and substr(num,3,1)<>substr(num,2,1))and
    length(numnum)=10-length(translate('0123456789','$'||numnum,'$')))
,t (str,len,path) AS (
/*SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') ,LEVEL,''
  FROM (SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
START WITH n>0
CONNECT BY NOCYCLE LEVEL<=3
*/
select a,length(a),'' from (select to_char(level,'fm999') a from dual connect by level<=999)
where a<=9
or(a>=10 and a<=99 and mod(a,11)>0)
or(a>=100 and (substr(a,1,1)<>substr(a,2,1) and substr(a,1,1)<>substr(a,3,1) and substr(a,3,1)<>substr(a,2,1)))
UNION ALL
SELECT SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+l)
       ,LENGTH(SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+l))
       ,path||SUBSTR(str,1,pos-1)||'('||SUBSTR(str,pos,l)||')'||SUBSTR(str,pos+l)||','
   FROM t,p
  WHERE pos+l-1<=t.len  and substr(SUBSTR(str,pos,l),-1)<>'0' and SUBSTR(str,p.pos,p.l)>'1' and (l<3 or SUBSTR(str,pos,l)in( select num from d3))
        AND LENGTH(TRANSLATE('1234567890','$'||SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+l),'$'))
            = 10 - LENGTH(SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+l))
)
CYCLE str SET cycle_flag TO 'Y' DEFAULT 'N'   
SELECT path||str FROM (
SELECT * FROM t ORDER BY len DESC,str DESC
)
WHERE ROWNUM=1;

PATH||STR
---------------------------------------------------------------------------
38(7),38(49),(3)82401,98(24)01,98(5)7601,98(2)57601,98457(6)01,984573601

已用时间:  00: 00: 35.00

lastwinner

原帖由 〇〇 于 10-9-3 09:06 发表

硬是看不懂,你把平方数的第一位换成$为什么

这不跟之前你们用来测试有无重复数字的代码差不多么？
要不你说应该替换为什么？

szusunny

38(7),38(49),(3)82401,98(24)01,98(5)7601,98(2)57601,98457(6)01,984573601
这个答案为什么不继续向前推呢?
38(7),38(49),(3)82401,98(24)01,98(5)7601,98(2)57601,98457(6)01,984(5)73601,9842573601

lastwinner

原帖由 szusunny 于 10-9-3 10:16 发表
38(7),38(49),(3)82401,98(24)01,98(5)7601,98(2)57601,98457(6)01,984573601
这个答案为什么不继续向前推呢?
38(7),38(49),(3)82401,98(24)01,98(5)7601,98(2)57601,98457(6)01,984(5)73601,9842573601

说明他们的算法还是有遗漏的地方

szusunny

不继续向前推的原因是判断字符不重复方法length(num)=10-length(translate('0123456789','$'||num,'$'))的漏洞.
应该加上nvl(...)解决NULL问题.
nvl(length(num),0)=10-nvl(length(translate('0123456789','$'||num,'$')),0)

〇〇

上面的代码在E5420
如果E7540
40秒
595
55秒

〇〇

原帖由 szusunny 于 2010-9-3 10:46 发表
不继续向前推的原因是判断字符不重复方法length(num)=10-length(translate('0123456789','$'||num,'$'))的漏洞.
应该加上nvl(...)解决NULL问题.
nvl(length(num),0)=10-nvl(length(translate('0123456789','$'||num,'$')),0)

NICEＪＯＢ

haiersknl

1 5 9 13 17 2 6 10 14 18 3 7 11 15 19 4 8 12 16

请你继续算第8题，上面有人算出984573601，有人指出应该继续运行得出9842573601。
那么现在的问题就出来了，程序上的漏洞会不会，让我们怀疑这个结果：9842573601 很可能不是最优的。

你们之前算的552是对的。552你们编程加调试一共用了多久？我有个简单方法笔算可搞定。

newkid

原帖由 haiersknl 于 2010-9-3 15:11 发表
1 5 9 13 17 2 6 10 14 18 3 7 11 15 19 4 8 12 16

请你继续算第8题，上面有人算出984573601，有人指出应该继续运行得出9842573601。
那么现在的问题就出来了，程序上的漏洞会不会，让我们怀疑这个结果：9842573601 很可能不是最优的。

你们之前算的552是对的。552你们编程加调试一共用了多久？我有个简单方法笔算可搞定。

你的答案是19?题目要找出最小的人数，我的答案是17:
1,5,9,13,17,4,8,12,16,3,7,11,15,2,6,10,14
1,14,10,6,2,15,11,7,3,16,12,8,4,17,13,9,5

这两个答案是顺序相反的排列。如果你觉得17有错，那么其中哪一个人的排列不符合题目要求？

第8题原来的TRANSLATE有漏洞，改过来就好了。如果你觉得还有错只需再举个反例，或者指出程序中的错误。

552指的是47楼那题？我花不到10分钟就写了那个递归SQL, 如果你有好的人肉方法请贴出来共享。

newkid

第8题，先把所有不重复的平方数找出来：

CREATE TABLE nums AS
WITH
n AS (
  SELECT TO_NUMBER(REPLACE(SYS_CONNECT_BY_PATH(rn,','),',','')) num  
    FROM (SELECT ROWNUM-1 rn FROM DUAL CONNECT BY ROWNUM<=10)
  START WITH rn>0
  CONNECT BY NOCYCLE rn<>PRIOR rn AND LEVEL<=5
  )
,nums AS (
SELECT TO_CHAR(num) num, TO_CHAR(numnum) numnum,LENGTH(numnum) l2
  FROM (SELECT num, num*num numnum FROM n)
WHERE LENGTH(numnum)=11-LENGTH(TRANSLATE('$0123456789','$'||numnum,'$'))
)
SELECT * FROM nums;



----------------------------------------
没有3位限制的写法：
WITH p AS (
SELECT pos,l
   FROM (SELECT ROWNUM pos FROM DUAL CONNECT BY ROWNUM<=10),(SELECT ROWNUM l FROM DUAL CONNECT BY ROWNUM<=5)
  WHERE pos+l<=11
  )
,t (str,len,path) AS (
SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') ,LEVEL,''
  FROM (SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
START WITH n>0
CONNECT BY NOCYCLE LEVEL<=3
UNION ALL
SELECT REPLACE(str,num,numnum)
       ,t.len+nums.l2-p.l
       ,path||SUBSTR(str,1,p.pos-1)||'('||num||')'||SUBSTR(str,p.pos+p.l)||','
   FROM nums,t,p
  WHERE p.pos+p.l-1<=t.len
        and substr(SUBSTR(str,pos,l),-1)<>'0' and SUBSTR(str,p.pos,p.l)>'1'
        AND LENGTH(TRANSLATE('$1234567890','$'||REPLACE(str,num,numnum),'$'))
            = 11 - (t.len+nums.l2-p.l)
        AND SUBSTR(str,p.pos,p.l) = nums.num
)
CYCLE str SET cycle_flag TO 'Y' DEFAULT 'N'   
SELECT path||str FROM (
SELECT * FROM t ORDER BY len DESC,str DESC
)
WHERE ROWNUM<=1;

PATH||STR
-------------------------------------------------------------------------
19(8),(1964),3857(2)96,3857(49)6,(3)85724016,98572401(6),9857240136

Elapsed: 00:00:20.40

有3位限制的写法：
WITH p AS (
SELECT pos,l
   FROM (SELECT ROWNUM pos FROM DUAL CONNECT BY ROWNUM<=10),(SELECT ROWNUM l FROM DUAL CONNECT BY ROWNUM<=3)
  WHERE pos+l<=11
  )
,t (str,len,path) AS (
SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') ,LEVEL,''
  FROM (SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
START WITH n>0
CONNECT BY NOCYCLE LEVEL<=3
UNION ALL
SELECT REPLACE(str,num,numnum)
       ,t.len+nums.l2-p.l
       ,path||SUBSTR(str,1,p.pos-1)||'('||num||')'||SUBSTR(str,p.pos+p.l)||','
   FROM nums,t,p
  WHERE p.pos+p.l-1<=t.len
        and substr(SUBSTR(str,pos,l),-1)<>'0' and SUBSTR(str,p.pos,p.l)>'1'
        AND LENGTH(TRANSLATE('$1234567890','$'||REPLACE(str,num,numnum),'$'))
            = 11 - (t.len+nums.l2-p.l)
        AND SUBSTR(str,p.pos,p.l) = nums.num
)
CYCLE str SET cycle_flag TO 'Y' DEFAULT 'N'   
SELECT path||str FROM (
SELECT * FROM t ORDER BY len DESC,str DESC
)
WHERE ROWNUM<=1;


PATH||STR
---------------------------------------------------------------------------------------
38(7),38(49),(3)82401,98(24)01,98(5)7601,98(2)57601,98457(6)01,984(5)73601,9842573601

Elapsed: 00:00:17.19

奇怪的是如果我把表nums写成WITH, 计划就改变了，等了好几分钟也出不来。有一步HASH JOIN变成了NESTED LOOP, 不知道有什么HINTS可以让它走HASH JOIN.