2012感恩节最短源代码比赛newkid代码解析

oracle_novice

牛！

幕南风

gyhgood

太牛了！求签名

sj198421

只能膜拜下了！！

newkid

〇〇 发表于 2012-12-4 09:14
有个疑问：neighbours的用途是在递归过程中确保新加入的第N个方格和已有的N-1个方格中的至少一个相邻
这种 ...

怎么不相邻？B的右边不就是b? 按我的递归算法，这个形状构成的顺序是：b(右上)->b(右)->B(中)
每次加入的都和前一个相邻。

〇〇

newkid 发表于 2012-12-4 23:11
怎么不相邻？B的右边不就是b? 按我的递归算法，这个形状构成的顺序是：b(右上)->b(右)->B(中)
每次加入的 ...

那这个
aba
aBb
aaa
怎么又是从上中/中/右中？路线不一样？

278676125

膜拜大神。。。

newkid

〇〇 发表于 2012-12-5 06:41
那这个
aba
aBb

你理解的“路线”到底是怎样的？每个形状不一样，“路线”当然不一样！
不变的是递归的规则，每次加入的新方格都和前面相邻。不管哪个方向都可以加入。

newkid

新加入的递归条件可以进一步提升效率

VAR N NUMBER;
EXEC :N:=8;

旧方法：
WITH blocks AS ( ----- 构造25个点坐标
SELECT TRUNC((LEVEL-1)/:N) X  ---- 行号从0到4
      ,MOD(LEVEL-1,:N) Y      ---- 列号从0到4
      ,LEVEL num             ----- 格子编号
      ,POWER(2,:N*:N-LEVEL) ID  ----- 每个格子的二进制编码，编号1作为最高位，25作为最低位，这是排序要求的
  FROM DUAL
CONNECT BY LEVEL<=:N*:N
)
,neighbours AS ( ---- 找出所有方格及其相邻的方格ID
SELECT c1.id id1
      ,SUM(c2.id) id2
      ,c1.num
  FROM blocks c1,blocks c2
WHERE ABS(c1.X-c2.X)+ABS(c1.Y-c2.Y)=1 ---- 两个方格相邻的条件
       AND c1.x+c1.y<:N  
       AND c2.x+c2.y<:N
GROUP BY c1.id,c1.num   
)
,T(cnt,id_sum,shape_val) AS ( ---- 用递归的方法生成所有位置的所有形状
SELECT 1,ID,num FROM blocks WHERE x=0 ---- 从行坐标轴上的点开始递归
UNION ALL
SELECT cnt+1,id_sum+n.id1,t.shape_val+n.num
  FROM T,neighbours n  ---- 逐渐加入其他方格
WHERE BITAND(T.id_sum,n.ID1)=0 AND BITAND(T.id_sum,n.ID2)>0 ---- 加入的条件是：该方格本身未被包含，而其邻居则已被包含
       AND cnt<:N  ---- 到达N个方格就停止
)
,all_shapes AS (
    SELECT DISTINCT id_sum,shape_val ---- 去除结果中的重复数据
      FROM T
     WHERE cnt=:N
           AND BITAND(id_sum,(SELECT SUM(id) FROM blocks WHERE y=0))>0
)
SELECT COUNT(*) FROM all_shapes;

  COUNT(*)
----------
      2725

Elapsed: 00:00:31.74

新方法：如果递归过程中发现没有希望接触到Y轴，则放弃该路径
WITH blocks AS (
SELECT TRUNC((LEVEL-1)/:N) X
      ,MOD(LEVEL-1,:N) Y   
      ,LEVEL num            
      ,POWER(2,:N*:N-LEVEL) ID
  FROM DUAL
CONNECT BY LEVEL<=:N*:N
)
,neighbours AS (
SELECT c1.id id1
      ,SUM(c2.id) id2
      ,c1.num
      ,c1.y     ---------- 为新递归条件服务
  FROM blocks c1,blocks c2
WHERE ABS(c1.X-c2.X)+ABS(c1.Y-c2.Y)=1
       AND c1.x+c1.y<:N  
       AND c2.x+c2.y<:N
GROUP BY c1.id,c1.num,c1.y
)
,T(cnt,id_sum,shape_val,min_y) AS (
SELECT 1,ID,num,y FROM blocks WHERE x=0
UNION ALL
SELECT cnt+1,id_sum+n.id1,t.shape_val+n.num,LEAST(t.min_y,n.y)  ----- min_y: 形状中最接近Y轴的点
  FROM T,neighbours n  
WHERE BITAND(T.id_sum,n.ID1)=0 AND BITAND(T.id_sum,n.ID2)>0
       AND t.min_y+t.cnt<=:N -------- 新条件：剩下方块的个数全部往Y轴方向凑，必须能够接触到Y轴
       AND cnt<:N  
)
,all_shapes AS (
    SELECT DISTINCT id_sum,shape_val ---- 去除结果中的重复数据
      FROM T
     WHERE cnt=:N
           AND BITAND(id_sum,(SELECT SUM(id) FROM blocks WHERE y=0))>0
)
SELECT COUNT(*) FROM  all_shapes;

  COUNT(*)
----------
      2725

Elapsed: 00:00:16.10

中间结果T从80多万下降为40多万。重复的还是太多，此时用PLSQL应该占优。

〇〇

newkid 发表于 2012-12-5 23:01
你理解的“路线”到底是怎样的？每个形状不一样，“路线”当然不一样！
不变的是递归的规则，每次加入的 ...

我理解为只有后加入的点数比已有的大，看来我错了