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

newkid

加了两个hints，终于可以不用中间表了：

每次划掉三位以内的：

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<=3
  )
,nums AS (
SELECT /*+ materialize */ 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,'$'))
)
,p AS (
SELECT /*+ materialize */ 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:11.85


每次划掉五位以内的：

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 /*+ materialize */ 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,'$'))
)
,p AS (
SELECT /*+ materialize */ 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:13.94

〇〇

newkid too strong

〇〇

没想到
AND SUBSTR(str,p.pos,p.l) = nums.num
代替
SUBSTR(str,p.pos,p.l) in(select nums.num from nums)效果这么好

提示实体化比rownum固化也好

〇〇

我这里,如果
SELECT to_char(num,'fm999') ,length(num),''from n
UNION ALL
还会快1点点

haiersknl

你的17是对的，我看走眼了，552人肉快的话需要25分钟-到半小时计算出结果，还是你的编程快，就不贴人肉方法了。之所以我觉得可以人肉，是因为有很多巧妙的限制条件，这些限制条件大大减小了遍历的可能性。newkid： 世界上只有两种语言：甲骨文和肢体语言。

lastwinner

原帖由 〇〇 于 10-9-4 06:45 发表
我这里,如果
SELECT to_char(num,'fm999') ,length(num),''from n
UNION ALL
还会快1点点

这种“优化”其实用处并不大，要尝试走出这样的误区，单就你这个例子而言，其实这就一次/几次尝试而已，并不能从根本上证明这样就一定能快。当然，我这个论断可能是不对的，仅供参考而已。

计算效率要提高，在硬件不变的情况下，首先就是要充分利用硬件资源，但这一点我们在sql中无法做到
其次就是提高算法效率，具体有几种：1是使用更佳的算法，2是同样算法下减少计算次数
如果计算涉及到设备之间的数据交互，还要想办法减少交互次数，降低交互时传输的字节数

以上种种，才是提高计算效率的办法

haiersknl

你怎么用（1964）？括号最多可以括3位！

haiersknl

原帖由 haiersknl 于 2010-9-4 17:05 发表
你怎么用（1964）？括号最多可以括3位！

newkid 继续，把你的程序完善，注意题中条件。

haiersknl

原帖由 haiersknl 于 2010-9-4 17:10 发表


newkid 继续，把你的程序完善，注意题中条件。

不好意思，是我漏看了，我没看到你100楼的程序说明，呵呵

newkid

原帖由 haiersknl 于 2010-9-4 17:00 发表
你的17是对的，我看走眼了，552人肉快的话需要25分钟-到半小时计算出结果，还是你的编程快，就不贴人肉方法了。之所以我觉得可以人肉，是因为有很多巧妙的限制条件，这些限制条件大大减小了遍历的可能性。newkid： 世界上只有两种语言：甲骨文和肢体语言。

确实，有了十个手指头和十个脚趾头，20以内运算就不用计算器了！
我写递归的时候也尽量把能想到的结束递归条件在WHERE中体现出来，这样就能砍掉很多无用的分支，提高效率。