puzzleup 2018

〇〇

先来测试4个线段，条件不对，少了1个形状
with point (n,a,b) as(
select level,ceil(level/2),mod(level-1,2)+1 from dual connect by level<=4),
line (n,n1,n2) as(select rownum,p1.n,p2.n from point p1,point p2 where abs(p2.a-p1.a) + abs(p2.b-p1.b)=1 and p1.n<p2.n),
shap (lv,nn,s,s2,nx) as(select 1,n,power(2,n),power(2,n1)+power(2,n2),n from line --s1 exists lines,s2 exists points
union all
select lv+1,n,s+power(2,n),
s2+power(2,n1)+power(2,n2)-bitand(s2, power(2,n1)+power(2,n2)),  --BITOR(x,y) = (x + y) - BITAND(x, y)
greatest(nx,n)
from shap,line where n>nx and
bitand(s,power(2,n))=0 and (bitand(power(2,n1),s2)=power(2,n1) or bitand(power(2,n2),s2)=power(2,n2) ) and
lv<(select count(*) from line))
select * from shap;
        LV         NN          S         S2         NX
---------- ---------- ---------- ---------- ----------
         1          1          2          6          1
         1          2          4         10          2
         1          3          8         20          3
         1          4         16         24          4
         2          2          6         14          2
         2          3         10         22          3
         2          4         20         26          4
         2          4         24         28          4
         3          3         14         30          3
         3          4         22         30          4
         3          4         26         30          4
         4          4         30         30          4

〇〇

〇〇 发表于 2018-11-22 14:08
先来测试4个线段，条件不对，少了1个形状
with point (n,a,b) as(
select level,ceil(level/2),mod(level ...

n>nx 有问题
每次加入的线要比前面的大
1011就不能拼成，

〇〇

〇〇 发表于 2018-11-22 14:13
n>nx 有问题
每次加入的线要比前面的大
1011就不能拼成，

去掉n>nx条件有很多重复，4个线段能算，12个就不行了
SQL> with point (n,a,b) as(
  2  select level,ceil(level/2),mod(level-1,2)+1 from dual connect by level<=4),
  3  line (n,n1,n2) as(select rownum,p1.n,p2.n from point p1,point p2 where abs(p2.a-p1.a) + abs(p2.b-p1.b)=1 and p1.n<p2.n),
  4  shap (lv,nn,s,s2,nx) as(select 1,n,power(2,n),power(2,n1)+power(2,n2),n from line --s1 exists lines,s2 exists points
  5  union all
  6  select lv+1,n,s+power(2,n),
  7  s2+power(2,n1)+power(2,n2)-bitand(s2, power(2,n1)+power(2,n2)),  --BITOR(x,y) = (x + y) - BITAND(x, y)
  8  greatest(nx,n)
  9   from shap,line where -- n>nx and
10  bitand(s,power(2,n))=0 and (bitand(power(2,n1),s2)=power(2,n1) or bitand(power(2,n2),s2)=power(2,n2) ) and
11  lv<(select count(*) from line))
12  select count(unique s) from shap;

COUNT(UNIQUES)
--------------
            13

SQL> set timi on
SQL> with point (n,a,b) as(
  2  select level,ceil(level/3),mod(level-1,3)+1 from dual connect by level<=9),
  3  line (n,n1,n2) as(select rownum,p1.n,p2.n from point p1,point p2 where abs(p2.a-p1.a) + abs(p2.b-p1.b)=1 and p1.n<p2.n),
  4  shap (lv,nn,s,s2,nx) as(select 1,n,power(2,n),power(2,n1)+power(2,n2),n from line --s1 exists lines,s2 exists points
  5  union all
  6  select lv+1,n,s+power(2,n),
  7  s2+power(2,n1)+power(2,n2)-bitand(s2, power(2,n1)+power(2,n2)),  --BITOR(x,y) = (x + y) - BITAND(x, y)
  8  greatest(nx,n)
  9   from shap,line where -- n>nx and
10  bitand(s,power(2,n))=0 and (bitand(power(2,n1),s2)=power(2,n1) or bitand(power(2,n2),s2)=power(2,n2) ) and
11  lv<(select count(*) from line))
12  select count(unique s) from shap;
^Cwith point (n,a,b) as(
*
ERROR at line 1:
ORA-01013: user requested cancel of current operation


Elapsed: 00:00:41.89

〇〇

〇〇 发表于 2018-11-22 14:27
去掉n>nx条件有很多重复，4个线段能算，12个就不行了
SQL> with point (n,a,b) as(
  2  select level, ...

如果利用对称，1011就能变成1110，不知道对12条线段够不够，

solomon_007

17#

SQL> with point(n,
  2  x,
  3  y) as
  4   (select level n,
  5           ceil(level / 3),
  6           decode(mod(level, 3), 0, 3, mod(level, 3))
  7      from dual
  8    connect by level <= 9),
  9  line(n,
10  p1,
11  p2) as
12   (select rownum, p1.n, p2.n
13      from point p1, point p2
14     where abs(p1.x - p2.x) + abs(p1.y - p2.y) = 1
15       and p1.n < p2.n),
16  shape(lvl,
17  nlist,
18  val,
19  plist,
20  last_n) as
21   (select 1, cast(n as varchar2(100)), power(2, n), p1 || ',' || p2, n
22      from line
23    union all
24    select s.lvl + 1,
25           s.nlist || ',' || a.n,
26           s.val + power(2, a.n),
27           s.plist || ',' || a.p1 || ',' || a.p2,
28           a.n
29      from shape s, line a
30     where bitand(s.val, power(2, a.n)) = 0
31       and (instr(s.plist, a.p1) > 0 or instr(s.plist, a.p2) > 0)
32       and s.last_n < a.n)
33  select count(*) from shape
34  /
  COUNT(*)
----------
       940

〇〇

solomon_007 发表于 2018-11-22 15:36
17#

SQL> with point(n,

居然和n>nx的答案一样
SQL> with point (n,a,b) as(
  2  select level,ceil(level/3),mod(level-1,3)+1 from dual connect by level<=9),
  3  line (n,n1,n2) as(select rownum,p1.n,p2.n from point p1,point p2 where abs(p2.a-p1.a) + abs(p2.b-p1.b)=1 and p1.n<p2.n),
  4  shap (lv,nn,s,s2,nx) as(select 1,n,power(2,n),power(2,n1)+power(2,n2),n from line --s1 exists lines,s2 exists points
  5  union all
  6  select lv+1,n,s+power(2,n),
  7  s2+power(2,n1)+power(2,n2)-bitand(s2, power(2,n1)+power(2,n2)),  --BITOR(x,y) = (x + y) - BITAND(x, y)
  8  greatest(nx,n)
  9   from shap,line where  n>nx and
10  bitand(s,power(2,n))=0 and (bitand(power(2,n1),s2)=power(2,n1) or bitand(power(2,n2),s2)=power(2,n2) ) and
11  lv<(select count(*) from line))
12  select count(unique s) from shap;

COUNT(UNIQUES)
--------------
           940

Elapsed: 00:00:00.04

〇〇

solomon_007 发表于 2018-11-22 15:36
17#

SQL> with point(n,

按我的分析，2^5 +10 +11 +12应该不在里面

solomon_007

〇〇 发表于 2018-11-22 15:53
居然和n>nx的答案一样
SQL> with point (n,a,b) as(
  2  select level,ceil(level/3),mod(level-1,3)+ ...

答案可能不对，检验4个点方形的例子，答案不对，

SQL>
SQL> with point(n,x,y) as (select level n,ceil(level/2),decode(mod(level,2),0,2,mod(level,2)) from dual connect by level<=4),
  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,last_n) as (select 1,cast(n as varchar2(100)),power(2,n),p1||','||p2,n 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                                             a.n
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 s.last_n < a.n
14                                       )
15  select * from shape
16  /
       LVL NLIST                                                                                   VAL PLIST                                                                                LAST_N
---------- -------------------------------------------------------------------------------- ---------- -------------------------------------------------------------------------------- ----------
         1 1                                                                                         2 1,2                                                                                       1
         1 2                                                                                         4 1,3                                                                                       2
         1 3                                                                                         8 2,4                                                                                       3
         1 4                                                                                        16 3,4                                                                                       4
         2 1,2                                                                                       6 1,2,1,3                                                                                   2
         2 1,3                                                                                      10 1,2,2,4                                                                                   3
         2 2,4                                                                                      20 1,3,3,4                                                                                   4
         2 3,4                                                                                      24 2,4,3,4                                                                                   4
         3 1,2,3                                                                                    14 1,2,1,3,2,4                                                                               3
         3 1,2,4                                                                                    22 1,2,1,3,3,4                                                                               4
         3 1,3,4                                                                                    26 1,2,2,4,3,4                                                                               4
         4 1,2,3,4                                                                                  30 1,2,1,3,2,4,3,4                                                                           4
12 rows selected


明显的漏掉了，2，3，4 这中情形。。。

〇〇

solomon_007 发表于 2018-11-22 16:02
答案可能不对，检验4个点方形的例子，答案不对，

SQL>

就是s.last_n < a.n导致

instr(s.plist,a.p1) > 0还有可能把12当成1和2

solomon_007

〇〇 发表于 2018-11-22 16:04
就是s.last_n < a.n导致

instr(s.plist,a.p1) > 0还有可能把12当成1和2

instr(s.plist,a.p1) > 0还有可能把12当成1和2，这个不会，因为2*2 只有9个点，这个不是指边1-12

就是s.last_n < a.n导致，这个确实是的，跟里面的 rownum随机有关。。