puzzleup 2018

peter1166

newkid 发表于 2018-11-24 00:12
这很不科学，给定一个图形，你怎么判断哪些延长边是要手工加入的?

哈哈。。这个确实有人为手工判断的因素。
当然， 如果不想这样， 把所有长度为2的线段都加进去也行，然后再加上 level <= 12 限定最多12步。就是更慢了。
然后也可以考虑加上限定开始点， 想了一下好像只可以去掉一个点，9个点不用全部都是开始点，1-8就可以。
但是也快不了多少。 Connect by 确实慢。

newkid

peter1166 发表于 2018-11-24 00:49
哈哈。。这个确实有人为手工判断的因素。
当然， 如果不想这样， 把所有长度为2的线段都加进去也行，然 ...

如果在算N=4, 3X3格子的，那么即使把所有长度为2的加进去也会有漏洞。
限定开始点的思路就是OO说的对称做法，问题是得排除重叠。
在同样算法情况下，CONNECT BY是比递归要快的。加菲猫一开始没有在递归过程中去除重复，同样很慢。CONNECT BY没法对上一层数据加工去掉重复。

〇〇

newkid 发表于 2018-11-24 02:52
如果在算N=4, 3X3格子的，那么即使把所有长度为2的加进去也会有漏洞。
限定开始点的思路就是OO说的对称 ...

pl/sql好办吗

peter1166

newkid 发表于 2018-11-24 02:52
如果在算N=4, 3X3格子的，那么即使把所有长度为2的加进去也会有漏洞。
限定开始点的思路就是OO说的对称 ...

如果是 3*3 的， 就还要加上长度为3的，长度1,2,3 的都要列举出然后再遍历所有可能的情况了。
要尝试一下 3*3 么。

newkid

peter1166 发表于 2018-11-24 12:17
如果是 3*3 的， 就还要加上长度为3的，长度1,2,3 的都要列举出然后再遍历所有可能的情况了。
要尝试一 ...

就算这样，CONNECT BY也算不出来，中间的重复太多了。

PL/SQL做法：其实就是把我那个递归写法拆散，每层建立一个临时表而已，但是这样就快了很多。递归SQL还是不够聪明。

VAR N NUMBER;
EXEC :N:=4;

create table e (b number,b2 number);

insert into e
WITH
  d as (select power(2,level) n,ceil(level/:N) x,mod(level,:N) y from dual connect by level<=:N*:N)
select power(2,rownum-1) b,p1.n+p2.n b2
   from d p1,d p2
  where abs(p1.x - p2.x) + abs(p1.y-p2.y) =1 and p1.n < p2.n
;

create table e1_12 as
with
t (b,b2,rn,lvl) as (
select b,b2,1,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
       ,lvl+1
   from t,e
  where t.rn=1  ------- 去重复
        and bitand(t.b,e.b)=0
        and bitand(t.b2,e.b2)>0
        and lvl<12
)
select distinct b,b2,lvl from t;


Elapsed: 00:01:09.17

create table e12 as select b,b2 from e1_12 where lvl=12;

begin
   for i in 13..24 loop
       execute immediate 'drop table e'||i;
       execute immediate '
create table e'||i||' as
select distinct t.b+e.b b
       ,t.b2+e.b2-bitand(t.b2,e.b2) b2
   from e'||(i-1)||' t,e
  where  bitand(t.b,e.b)=0
        and bitand(t.b2,e.b2)>0
        ';

   end loop;
end;
/

PL/SQL procedure successfully completed.

Elapsed: 00:00:23.87

〇〇

newkid 发表于 2018-11-25 07:28
就算这样，CONNECT BY也算不出来，中间的重复太多了。

PL/SQL做法：其实就是把我那个递归写法拆散，每 ...

好办法.

〇〇

〇〇 发表于 2018-11-25 08:35
好办法.

最后还得把e1_12,13 ...24全都union all再count distinct

newkid

根本没必要再 union 更没必要 distinct, 分别 count 就行。

〇〇

newkid 发表于 2018-11-26 03:16
根本没必要再 union 更没必要 distinct, 分别 count 就行。

确实，你create都distinct了
SQL> set serverout on

SQL> declare
  2  tot int;
  3  tmp int;
  4  begin
  5  select count(*) into tot from e1_12 ;
  6  for i in 13..24 loop
  7  execute immediate 'select count(*) from e'||i into tmp;
  8  tot:=tot+tmp;
  9  end loop;
10  dbms_output.put_line(tot);
11  end;
12  /
3565408

PL/SQL procedure successfully completed.

Elapsed: 00:00:00.20
我的服务器
SQL> show sga

Total System Global Area 8.1336E+10 bytes
Fixed Size                  7653480 bytes
Variable Size            1.6106E+10 bytes
Database Buffers         6.3888E+10 bytes
Redo Buffers              260780032 bytes
In-Memory Area           1073741824 bytes
怎么还比你的慢那么多？
SQL> create table e1_12 as
  2  with
  3  t (b,b2,rn,lvl) as (
  4  select b,b2,1,1 from e
  5  union all
  6  select t.b+e.b
  7         ,t.b2+e.b2-bitand(t.b2,e.b2) --- bitor
  8         ,row_number() over(partition by t.b+e.b order by 1) rn
  9         ,lvl+1
10     from t,e
11    where t.rn=1  ------- 去重复
12          and bitand(t.b,e.b)=0
13          and bitand(t.b2,e.b2)>0
14          and lvl<12
15  )
16  select distinct b,b2,lvl from t;

Table created.

Elapsed: 00:02:57.78

〇〇

〇〇 发表于 2018-11-26 08:21
确实，你create都distinct了
SQL> set serverout on

第一个也用物理表
SQL> begin
  2  execute immediate 'drop table e1 purge';
  3  execute immediate 'create table e1 as select b,b2 from e';
  4     for i in 2..12 loop
  5  begin
  6  execute immediate 'drop table e'||i;
  7  exception when others then null;
  8  end;
  9         execute immediate '
10  create table e'||i||' as
11  select distinct t.b+e.b b
12         ,t.b2+e.b2-bitand(t.b2,e.b2) b2
13     from e'||(i-1)||' t,e
14    where  bitand(t.b,e.b)=0
15          and bitand(t.b2,e.b2)>0
16          ';
17  
18     end loop;
19  
20  end;
21  /

PL/SQL procedure successfully completed.

Elapsed: 00:00:04.39