分享一下SQL数据库编程大赛第二期我的解法

rollingpig

最遗憾的就是在处理对角线时，没有用 *10 的方式来处理，导致整个code的可读性下降和性能的稍微下降，如果但是采用*10的方式，自己就很满意了.

对于我来说，最满意的写法应该是：

1. 
   
2. with
   
3. linesrc(line,linenum) as (   -- 生成 01010串
   
4.       select replace(linestr,',') line ,to_number(replace(linestr,','))
   
5.     from (
   
6.       select sys_connect_by_path(bit,',') linestr,level LevelN
   
7.       from (
   
8.         select 0 bit from dual
   
9.         union all
   
10.         select 1 from dual
    
11.       )
    
12.       connect by level <= :n
    
13.     )where LevelN=:n
    
14.   and length(linestr)-length(replace(linestr,1))=:m     -- 每行正好m个球.
    
15. ),
    
16. solution(LevelN ,solutionStrings, cmp1,cmp2,cmp3 ) as (
    
17.   select
    
18.      1 --LevelN
    
19.     ,line -- solutionStrings
    
20.     ,linenum
    
21.     ,linenum
    
22.     ,linenum * power(10,:n-1)
    
23.   from linesrc  
    
24.   where line>=reverse(line)  --预先过滤左右对称
    
25.   union all
    
26.   select
    
27.     LevelN +1  
    
28.     ,solutionStrings || line
    
29.     ,cmp1+linenum     
    
30.     ,cmp2+linenum*power(10,levelN)     
    
31.     ,cmp3+linenum*power(10,:n-levelN-1)     
    
32.   from solution,linesrc     
    
33.   where
    
34.   levelN<:n and
    
35.   instr((cmp1+linenum ) || ( cmp2+linenum*power(10,levelN))  || (cmp3+linenum*power(10,:n-levelN-1)) ,:m+1 ) =0
    
36. ),
    
37. solution2(solutionStrings) as(  -- original solution
    
38.   select /*+ materialize */  solutionStrings from   solution
    
39.   where LevelN=:n
    
40. )
    
41. ,
    
42. symmtmp(blockN,xo,yo,xx,yy) as (  --base table for  对称判断.
    
43.   select /*+ materialize */  rownum-1 ,mod(rownum-1,:n),floor((rownum-1)/:n)  , :n-1-mod(rownum-1,:n),:n-1-floor((rownum-1)/:n)
    
44.   from dual
    
45.   connect by rownum <= :n*:n
    
46. ),
    
47. symmsrc(blockN,bit,symmtype) as (   -- 对称判断表， blockN 是方格位置，bit是 blockN所对应对称点的二进制数字，symmtype是对称方式，共有八种（包括原地??
    
48.   select blockN, power(2,blockN   ),0 from symmtmp  -- type 0, self, no symm
    
49.   union all select blockN, power(2,xx+yo*:n ),1 from symmtmp -- type 1,上下
    
50.   union all select blockN, power(2,xo+yy*:n ),2 from symmtmp -- type 2,左右
    
51.   union all select blockN, power(2,yo+xo*:n ),3 from symmtmp -- type 3,对角
    
52.   union all select blockN, power(2,yy+xx*:n ),4 from symmtmp -- type 4,反对角
    
53.   union all select blockN, power(2,yo+xx*:n ),5 from symmtmp -- type 5,顺时针 90
    
54.   union all select blockN, power(2,xx+yy*:n ),6 from symmtmp -- type 6,顺时针 180
    
55.   union all select blockN, power(2,yy+xo*:n ),7 from symmtmp -- type 7,顺时针 270
    
56. ),
    
57. solution_symm as (
    
58.   select /*+ materialize use_hash(symmsrc solution2) ordered */ solutionStrings,sum(bit) bitSum--,symmtype
    
59.   -- 去除对称重复结果第一步, 得出每个solution对应的对称结果的二进制数据 .
    
60.   from symmsrc,solution2
    
61.   where substr(solutionStrings,blockN+1,1)='1'
    
62.   group by solutionStrings,symmtype
    
63. )
    
64. select * from
    
65. (select :m m, :n n,count(distinct bitSum) "AllCnt" from solution_symm), --这里把前面过滤掉的左右对称部分找回来 .
    
66. (select  count(distinct min(bitSum)) "NoReptCnt" from solution_symm group by solutionStrings)
    
67. 
    

复制代码

[ 本帖最后由 rollingpig 于 2011-3-30 12:29 编辑 ]

tigerfish

lastwinner

有扎实的DBA基础的滚珠，写SQL代码时极尽一切调优手段，性能想不高都难

newkid

构造symmsrc的思路真是令人叹为观止，读这种程序是很享受的。
但我还是更喜欢TRANSLATE的方法，效率更高（symmsrc里面有N*N*8行），受ORACLE的NUMBER精度限制，BIT的表现力只能做到N=11.

rollingpig

嗯。
对于我来说，translate的方式当时是想不到的。
说实话，直到看到答案之前，我还不知道translate还有带3个参数的做法。

另外，看了一下人肉和你创建translate穿的做法，似乎有一个更为简单的写法。

1. 
   
2. 
   
3. var n number
   
4. exec :n:=10;
   
5. with symmtmp(blockN,xo,yo,xx,yy) as (  --base table for  对称判断.
   
6.   select /*+ materialize */  
   
7. rownum-1 ,mod(rownum-1,:n),floor((rownum-1)/:n)  ,
   
8. :n-1-mod(rownum-1,:n),:n-1-floor((rownum-1)/:n)
   
9.   from dual
   
10.   connect by rownum <= :n*:n
    
11. ), symmsrc(block_org,block_new,symmtype) as (   -- 对称判断表， blockN 是方格位置，bit是 blockN所对应对称点的二进制数字，symmtype是对称方式，共有八种（包括原地??
    
12.   select blockN, blockN ,0 from symmtmp  -- type 0, self, no symm
    
13.   union all select blockN, xx+yo*:n ,1 from symmtmp -- type 1,上下
    
14.   union all select blockN, xo+yy*:n ,2 from symmtmp -- type 2,左右
    
15.   union all select blockN,yo+xo*:n ,3 from symmtmp -- type 3,对角
    
16.   union all select blockN, yy+xx*:n ,4 from symmtmp -- type 4,反对角
    
17.   union all select blockN, yo+xx*:n ,5 from symmtmp -- type 5,顺时针 90
    
18.   union all select blockN, xx+yy*:n ,6 from symmtmp -- type 6,顺时针 180
    
19.   union all select blockN, yy+xo*:n ,7 from symmtmp -- type 7,顺时针 270
    
20. ) ,
    
21. symm_string as (
    
22. select MAX(DECODE(symmtype,0,replace(r,'!'))) tpl0
    
23.       ,MAX(DECODE(symmtype,1,replace(r,'!'))) tpl1
    
24.       ,MAX(DECODE(symmtype,2,replace(r,'!'))) tpl2
    
25.       ,MAX(DECODE(symmtype,3,replace(r,'!'))) tpl3
    
26.       ,MAX(DECODE(symmtype,4,replace(r,'!'))) tpl4
    
27.       ,MAX(DECODE(symmtype,5,replace(r,'!'))) tpl5
    
28.       ,MAX(DECODE(symmtype,6,replace(r,'!'))) tpl6
    
29.       ,MAX(DECODE(symmtype,7,replace(r,'!'))) tpl7  
    
30. from(
    
31.     select sys_connect_by_path(chr(block_new+ascii('!')+1),'!')  r ,level as l,symmtype
    
32.     from symmsrc start with block_org=0 connect by  prior block_org+1  = block_org and prior symmtype = symmtype
    
33. )
    
34. where l = :n*:n )
    
35. select * from symm_string
    
36. 
    
37. 
    

复制代码

原帖由 newkid 于 2011-3-29 21:48 发表
构造symmsrc的思路真是令人叹为观止，读这种程序是很享受的。
但我还是更喜欢TRANSLATE的方法，效率更高（symmsrc里面有N*N*8行），受ORACLE的NUMBER精度限制，BIT的表现力只能做到N=11.

newkid

我看了一下其实大同小异，你写得紧凑些，我的行列转换多了一层，因为中间那一层我后面有用（还原所有解法）。
这几个模版怎么折腾，复杂性都有限，开销可以忽略。

zhangweicai74

只有看的份

mychary

from linesrc  
  where line>reverse(line)  --预先过滤左右对称
  union all
大师笔误，应该是  where line>=reverse(line)

rollingpig

里面多了一步去除字符list中0,1,分隔符. 实际上里面不需要特意去0,1,不会影响translate的结果。当然,我的分隔符实际上也是去的，不过是直接通过从分隔符+1开始拼字符串来去掉的。

如果担心因此影响N的取值，也有办法轻松绕过。

1. 
   
2. with
   
3. linesrc(line,linenum) as (   -- 生成 01010串
   
4.       select replace(linestr,',') line ,to_number(replace(linestr,','))
   
5.     from (
   
6.       select sys_connect_by_path(bit,',') linestr,level LevelN
   
7.       from (
   
8.         select 0 bit from dual
   
9.         union all
   
10.         select 1 from dual
    
11.       )
    
12.       connect by level <= :n
    
13.     )where LevelN=:n
    
14.   and length(linestr)-length(replace(linestr,1))=:m     -- 每行正好m个球.
    
15. ),
    
16. solution(LevelN ,solutionStrings, cmp1,cmp2,cmp3 ) as (
    
17.   select
    
18.      1 --LevelN
    
19.     ,line -- solutionStrings
    
20.     ,linenum
    
21.     ,linenum
    
22.     ,linenum * power(10,:n-1)
    
23.   from linesrc  
    
24.   where line>=reverse(line)  --预先过滤左右对称
    
25.   union all
    
26.   select
    
27.     LevelN +1  
    
28.     ,solutionStrings || line
    
29.     ,cmp1+linenum     
    
30.     ,cmp2+linenum*power(10,levelN)     
    
31.     ,cmp3+linenum*power(10,:n-levelN-1)     
    
32.   from solution,linesrc     
    
33.   where
    
34.   levelN<:n and
    
35.   instr((cmp1+linenum ) || ( cmp2+linenum*power(10,levelN))  || (cmp3+linenum*power(10,:n-levelN-1)) ,:m+1 ) =0
    
36. ),
    
37. solution2(solutionStrings) as(  -- original solution
    
38.   select /*+ materialize */  solutionStrings from   solution
    
39.   where LevelN=:n
    
40. ),
    
41. symmtmp(blockN,xo,yo,xx,yy) as (  --base table for  对称判断.
    
42.   select /*+ materialize */  
    
43. rownum-1 ,mod(rownum-1,:n),floor((rownum-1)/:n)  ,
    
44. :n-1-mod(rownum-1,:n),:n-1-floor((rownum-1)/:n)
    
45.   from dual
    
46.   connect by rownum <= :n*:n
    
47. ), symmsrc(block_org,block_new,symmtype) as (   -- 对称判断表， blockN 是方格位置，bit是 blockN所对应对称点的二进制数字，symmtype是对称方式，共有八种（包括原地??
    
48.   select blockN, blockN ,0 from symmtmp  -- type 0, self, no symm
    
49.   union all select blockN, xx+yo*:n ,1 from symmtmp -- type 1,左右
    
50.   union all select blockN, xo+yy*:n ,2 from symmtmp -- type 2,上下
    
51.   union all select blockN,yo+xo*:n ,3 from symmtmp -- type 3,对角
    
52.   union all select blockN, yy+xx*:n ,4 from symmtmp -- type 4,反对角
    
53.   union all select blockN, yo+xx*:n ,5 from symmtmp -- type 5,顺时针 90
    
54.   union all select blockN, xx+yy*:n ,6 from symmtmp -- type 6,顺时针 180
    
55.   union all select blockN, yy+xo*:n ,7 from symmtmp -- type 7,顺时针 270
    
56. ) ,
    
57. symm_string as (
    
58. select MAX(DECODE(symmtype,0,replace(r,'!'))) tpl0
    
59.       ,MAX(DECODE(symmtype,1,replace(r,'!'))) tpl1
    
60.       ,MAX(DECODE(symmtype,2,replace(r,'!'))) tpl2
    
61.       ,MAX(DECODE(symmtype,3,replace(r,'!'))) tpl3
    
62.       ,MAX(DECODE(symmtype,4,replace(r,'!'))) tpl4
    
63.       ,MAX(DECODE(symmtype,5,replace(r,'!'))) tpl5
    
64.       ,MAX(DECODE(symmtype,6,replace(r,'!'))) tpl6
    
65.       ,MAX(DECODE(symmtype,7,replace(r,'!'))) tpl7  
    
66. from(
    
67.     select sys_connect_by_path(chr(block_new+ascii('!')+1),'!')  r ,level as l,symmtype
    
68.     from symmsrc start with block_org=0 connect by  prior block_org+1  = block_org and prior symmtype = symmtype
    
69. )
    
70. where l = :n*:n )
    
71. select * from
    
72. (select :m M,:n n,
    
73. count(distinct least(
    
74.     SOLUTIONSTRINGS
    
75.     ,TRANSLATE(tpl1,tpl0,SOLUTIONSTRINGS)
    
76.     ,TRANSLATE(tpl2,tpl0,SOLUTIONSTRINGS)
    
77.     ,TRANSLATE(tpl3,tpl0,SOLUTIONSTRINGS)
    
78.     ,TRANSLATE(tpl4,tpl0,SOLUTIONSTRINGS)
    
79.     ,TRANSLATE(tpl5,tpl0,SOLUTIONSTRINGS)
    
80.     ,TRANSLATE(tpl6,tpl0,SOLUTIONSTRINGS)
    
81.     ,TRANSLATE(tpl7,tpl0,SOLUTIONSTRINGS)
    
82. )) as noReptCnt from symm_string,solution2),
    
83. (select count(distinct SOLUTIONSTRINGS) as all_cnt from (
    
84. select SOLUTIONSTRINGS from symm_string,solution2
    
85. union  select translate(tpl0,tpl1,SOLUTIONSTRINGS) from symm_string,solution2
    
86. ))
    
87. 
    

复制代码

原帖由 newkid 于 2011-3-30 11:27 发表
我看了一下其实大同小异，你写得紧凑些，我的行列转换多了一层，因为中间那一层我后面有用（还原所有解法）。
这几个模版怎么折腾，复杂性都有限，开销可以忽略。

rollingpig

改过来了

原帖由 mychary 于 2011-3-30 12:11 发表
from linesrc  
  where line>reverse(line)  --预先过滤左右对称
  union all
大师笔误，应该是  where line>=reverse(line)