PUZZLEUP 2014

newkid

〇〇 发表于 2014-12-4 08:28
count(instr(s,pl))=4*3*2/(1*2)

最后除以二什么意思？INSTR返回0也会被COUNT知道吗？
我的SQL找到123412314231243121342132413214321，你如果有更小的贴出来。

lastwinner

newkid 发表于 2014-12-4 23:28
最后除以二什么意思？INSTR返回0也会被COUNT知道吗？
我的SQL找到123412314231243121342132413214321，你 ...

数了数，33个字节

lastwinner

newkid 发表于 2014-12-4 23:28
最后除以二什么意思？INSTR返回0也会被COUNT知道吗？
我的SQL找到123412314231243121342132413214321，你 ...

人工推了一下，和你的结果一样


1234
2341
  3412
   4123
     2314                        --循环了，跳一位
      3142
       1423
        4231
          3124                   --循环了，跳一位
           1243
            2431
             4312
                2134              --循环了，跳两位
                 1342
                  3421
                   4213
                     1324         --循环了，跳一位
                      3241
                       2413
                        4132
                          3214    --循环了，跳一位
                           2143
                            1432
                             4321 --结束

〇〇

lastwinner 发表于 2014-12-5 10:22
人工推了一下，和你的结果一样

怎么知道最小

newkid

SQL方法可以保证最小。

peter1166

#19
只能出3个， 4个的还没弄出来

WITH T AS (
          SELECT LEVEL N FROM DUAL CONNECT BY LEVEL <= 3
          )
,T1 AS (
        SELECT REPLACE(SYS_CONNECT_BY_PATH(N,','),',','') S
        FROM T
        WHERE LEVEL = 3
        CONNECT BY NOCYCLE LEVEL<= 3 AND N <> PRIOR N
        )
,T2 AS (
        SELECT SYS_CONNECT_BY_PATH(S,',') STR
               ,REGEXP_REPLACE(REGEXP_REPLACE(REGEXP_REPLACE(REPLACE(SYS_CONNECT_BY_PATH(S,','),',',''),'(.)(.)\1\2','\1\2'),'(.)(\1)','\1'),'(.)(.)\1\2','\1\2') S
        FROM T1
        WHERE LEVEL = 6
        CONNECT BY NOCYCLE PRIOR SUBSTR(S,-2) =  SUBSTR(S,1,2) OR PRIOR SUBSTR(S,-1) =  SUBSTR(S,1,1)
        START WITH S = '123'
        )
SELECT MIN(TO_NUMBER(S))
FROM T2
;
MIN(TO_NUMBER(S))
-----------------
        123121321

lastwinner

〇〇 发表于 2014-12-5 20:12
怎么知道最小

不知道，只知道这个一个足够小的，人工这样推不能保证最小

lastwinner

lastwinner 发表于 2014-12-6 16:45
不知道，只知道这个一个足够小的，人工这样推不能保证最小

当然，如果可以证明，不按这思路走，那么无论从哪一位开始得出的另外一条线路，都不会比现在思路得出的线路短或值小，那么“这思路”就是最佳的思路

newkid

#20 Balls

There are six red balls and four black balls in a box. The balls are randomly drawn one by one and the colors are tallied. The process is continued until all the balls have been drawn. What is the probability that the number of red balls is always bigger then the number of black balls throughout the whole process?

Enter your answer as a simplified fraction. Example:12/23


有六个红球和4个黑球放在一个盒子里。 随机一个个把球取出并统计颜色数，直到所有球都取完。如果在这个过程中，红球的数量始终都比黑球大，这样的概率是多少？
----------
SQL很容易写，但是半天跑不出来，后来我拆成两步并创建了中间表，也花了大约两分钟才出结果。

newkid

第19题我的写法：

VAR N NUMBER;
EXEC :N:=4;

WITH p AS (
SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') p,POWER(2,ROWNUM-1) id
  FROM (SELECT LEVEL n FROM DUAL CONNECT BY LEVEL<=:N)
WHERE LEVEL=:N
CONNECT BY NOCYCLE n<>PRIOR n
)
,t(s,all_id) AS ( -----第一次递归找出三位重叠的，每组只有四个，之后就循环了
SELECT CAST(p AS VARCHAR2(100)),id FROM p
UNION ALL
SELECT t.s||SUBSTR(p.p,-1),t.all_id+p.id
  FROM t,p
WHERE SUBSTR(t.s,1-:N)=SUBSTR(p.p,1,:N-1)
       AND INSTR(t.s,p.p)=0
)
,l AS (
SELECT *
  FROM t
WHERE NOT EXISTS
           (SELECT NULL
              FROM p
             WHERE SUBSTR(t.s,1-:N)=SUBSTR(p.p,1,:N-1)
                   AND INSTR(t.s,p.p)=0
            ) --- 相关子查询找出叶子
)
,q(s,all_id) AS ( ---- 第二次递归利用上次的结果拼接，一位或者两位重叠
SELECT s,all_id
  FROM l        
UNION ALL
SELECT CASE WHEN SUBSTR(q.s,-2)=SUBSTR(l.s,1,2) THEN q.s||SUBSTR(l.s,3)
                 ELSE  q.s||SUBSTR(l.s,2)
       END
      ,q.all_id+l.all_id
  FROM l,q
WHERE (SUBSTR(q.s,-2)=SUBSTR(l.s,1,2) OR SUBSTR(q.s,-1)=SUBSTR(l.s,1,1))
      AND BITAND(q.all_id,l.all_id)=0
)
SELECT MIN(s) KEEP(DENSE_RANK FIRST ORDER BY LENGTH(s)) s FROM q WHERE all_id=(SELECT SUM(id) FROM p);

结果：
123412314231243121342132413214321