puzzleup 2018

solomon_007

newkid 发表于 2018-11-23 01:09
我的写法：

VAR N NUMBER;

CTE中不能使用GROUPBY ,DISTINCT，不能UNION ALL 后的SELECT外再包一层，所以ROW_NUMBER的
方法也被我放弃了，今天看到你的去重写法，很好！
引用一下你的去除重复的方法：

SQL> set timing on;
SQL>
SQL>
SQL> with point(n,x,y) as (select level n,ceil(level/3),decode(mod(level,3),0,3,mod(level,3)) from dual connect by level<=9),
  2         line(n,p1,p2) as (select rownum,p1.n,p2.n from point p1,point p2 where abs(p1.x - p2.x) + abs(p1.y-p2.y) =1 and p1.n < p2.n),
  3         shape(lvl,nlist,val,plist,rn) as (select 1,cast(n as varchar2(100)),power(2,n),p1||','||p2,1 from line
  4                                        union all
  5                                        select s.lvl + 1,
  6                                               s.nlist||','||a.n,
  7                                               s.val + power(2,a.n),
  8                                               s.plist||','||a.p1||','||a.p2,
  9                                               row_number() over(partition by s.lvl+1,s.val + power(2,a.n) order by s.val + power(2,a.n)) rn
10                                         from shape s,line a
11                                        where bitand(s.val,power(2,a.n))=0
12                                          and (instr(s.plist,a.p1) > 0 or instr(s.plist,a.p2) > 0)
13                                          and lvl < 12
14                                          and rn = 1
15                                        )
16   select sum(cnt)
17     from (select lvl, count(distinct val) cnt from shape group by lvl)
18  /
  SUM(CNT)
----------
      1759
Executed in 0.094 seconds

newkid

把加菲猫的写法和我的结合，代码短了：

VAR N NUMBER;
EXEC :N:=3;

WITH
  d as (select power(2,level) n,ceil(level/:N) x,mod(level,:N) y from dual connect by level<=:N*:N)
,e AS (
select p1.n+p2.n b2,power(2,rownum-1) b
   from d p1,d p2
  where abs(p1.x - p2.x) + abs(p1.y-p2.y) =1 and p1.n < p2.n
)
,t (b,b2,rn) as (
select b,b2,1 from e
union all
select t.b+e.b
       ,t.b2+e.b2-bitand(t.b2,e.b2) --- bitor
       ,row_number() over(partition by t.b+e.b order by 1) rn
   from t,e
  where t.rn=1  ------- 去重复
        and bitand(t.b,e.b)=0
        and bitand(t.b2,e.b2)>0
)
select count(distinct b) from t;

COUNT(DISTINCTB)
----------------
            1759

Elapsed: 00:00:00.03

newkid

lugionline 发表于 2018-11-23 08:49
发现我的社区积分竟然是-1，做这个论坛的真是个人才啊

还是你NB, 把-1转成二进制，每位都是1。

solomon_007

--去掉调试用的字段，再简化一下
SQL> with point(n,x,y) as (select level n,ceil(level/3),decode(mod(level,3),0,3,mod(level,3)) from dual connect by level<=9),
  2         line(n,p1,p2) as (select rownum,p1.n,p2.n from point p1,point p2 where abs(p1.x - p2.x) + abs(p1.y-p2.y) =1 and p1.n < p2.n),
  3         shape(lvl,val,plist,rn) as (select 1,power(2,n),p1||','||p2,1 from line
  4                                        union all
  5                                        select s.lvl + 1,
  6                                               s.val + power(2,a.n),
  7                                               s.plist||','||a.p1||','||a.p2,
  8                                               row_number() over(partition by s.lvl+1,s.val + power(2,a.n) order by s.val + power(2,a.n)) rn
  9                                         from shape s,line a
10                                        where bitand(s.val,power(2,a.n))=0
11                                          and (instr(s.plist,a.p1) > 0 or instr(s.plist,a.p2) > 0)
12                                          and rn = 1
13                                        )
14   select sum(cnt)
15     from (select lvl, count(distinct val) cnt from shape group by lvl)
16  /
  SUM(CNT)
----------
      1759
Executed in 0.078 seconds

newkid

〇〇 发表于 2018-11-23 06:02
@newkid 用对称能算n=4吗

那就得找出反转旋转后重复的那些，然后去掉，不是不可能就是太烦了。

在N=4的情况下，16段的结果已经300万，再一次笛卡尔积就受不了。

〇〇

lugionline 发表于 2018-11-23 08:43
快有什么用，要对
看这图能不能杀死pub

我打印了，可以作为练字纸，就是A4纸字太小

lugionline

嗯嗯，这就是传说中的易筋经，打印出来学是最方便了，祝你早日练成神功

peter1166

加了2长线段问题解决了， 但是慢了很多。


WITH t AS (
SELECT 'a' n ,  1 x,2 y  FROM dual UNION ALL
SELECT 'b' n ,  2 , 3 FROM dual UNION ALL
SELECT 'c' n ,  1 , 4 FROM dual UNION ALL
SELECT 'd' n ,  2 , 5 FROM dual UNION ALL
SELECT 'e' n ,  3 , 6 FROM dual UNION ALL
SELECT 'f' n ,  4 , 5 FROM dual UNION ALL
SELECT 'g' n ,  5 , 6 FROM dual UNION ALL
SELECT 'h' n ,  4 , 7 FROM dual UNION ALL
SELECT 'i' n ,  5 , 8 FROM dual UNION ALL
SELECT 'j' n ,  6 , 9 FROM dual UNION ALL
SELECT 'k' n ,  7 , 8 FROM dual UNION ALL
SELECT 'l' n ,  8 , 9 FROM dual UNION ALL
SELECT 'di' n ,  2 , 8 FROM dual UNION ALL
SELECT 'gf' n ,  4 , 6 FROM dual
)
SELECT   
        COUNT(DISTINCT TRANSLATE(TRANSLATE('abcdefghijkl',replace(sys_connect_by_path(n,',') ,',',''),'1111111111111111'),'abcdefghijkl','000000000000') ) cnt
FROM t
CONNECT BY  NOCYCLE
    x IN (PRIOR x,PRIOR y)
OR  y IN (PRIOR x,PRIOR y)
;

       CNT
----------
      1759
      
Executed in 18.643 seconds

newkid

lugionline 发表于 2018-11-23 10:38
嗯嗯，这就是传说中的易筋经，打印出来学是最方便了，祝你早日练成神功

你是不是练成神功了?

newkid

peter1166 发表于 2018-11-23 11:47
加了2长线段问题解决了， 但是慢了很多。

这很不科学，给定一个图形，你怎么判断哪些延长边是要手工加入的?