puzzleup 2018

peter1166

newkid 发表于 2018-11-22 23:23
我算的是1759, 在和你对答案时，发现这个不在你的答案里面：
111110011100
不知道CONNECT BY为什么把它 ...

11
111
00
111
00

--  --
|  |   |
|  |   |

connect by 这种情况确实走不出来， 一个点为连接点拼接线段的方式连续走不出来， 必定有个线段要走两次， 这就被nocycle 过滤了。

我明天再尝试一下方块儿连接的方法行不行。

solomon_007

〇〇 发表于 2018-11-22 19:32
就是我在259楼说的

终于找到了跟 peter的差别了，他用的是线段首尾相连，而我们上面用的是跟前面任何一个线段相连，
但跟前面任何一个线段相连跑不出答案，（下面是考虑首尾相连后的修改）

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,p1,p2) as (select 1,cast(n as varchar2(100)),power(2,n),p1,p2 from line
  4                                      union all
  5                                      select s.lvl + 1,
  6                                             s.nlist||','||a.n,
  7                                             s.val + power(2,a.n),
  8                                             a.p1,
  9                                             a.p2
10                                        from shape s,line a
11                                       where bitand(s.val,power(2,a.n))=0
12                                         and lvl < 12
13                                         and (a.p1 = s.p1 or a.p1 = s.p2 or a.p2 = s.p1 or a.p2 = s.p2)
14                                       )
15   select sum(cnt)
16     from (select lvl, count(distinct val) cnt from shape group by lvl)
17  /
  SUM(CNT)
----------
      1609

newkid

我的写法：

VAR N NUMBER;
EXEC :N:=3;

WITH d AS (SELECT ROWNUM id,X, Y FROM (SELECT LEVEL x FROM DUAL CONNECT BY LEVEL<=:N),(SELECT LEVEL y FROM DUAL CONNECT BY LEVEL<=:N))
,e AS (
SELECT rownum id,d1.x x1,d1.y y1,d2.x x2,d2.y y2,power(2,rownum) b
  FROM d d1,d d2
WHERE d1.id<d2.id and (d1.x=d2.x and abs(d1.y-d2.y)=1 or d1.y=d2.y and abs(d1.x-d2.x)=1)
)
,c as (
select s1.b b1,s2.b b2,s1.b+s2.b b
  from e s1,e s2
where s1.id<s2.id
       and ((s1.x1,s1.y1) in ((s2.x1,s2.y1),(s2.x2,s2.y2))
            or
            (s1.x2,s1.y2) in ((s2.x1,s2.y1),(s2.x2,s2.y2))
           )
)                  
,t (b,rn) as (
select b,1 from e
union all
select t.b+c.b-bitand(t.b,c.b)  --- bitor
      ,row_number() over(partition by t.b+c.b-bitand(t.b,c.b) order by 1) rn
  from t,c
where t.rn=1  ------- 去重复
       and bitand(t.b,c.b) in (c.b1,c.b2)
)
select count(distinct b) from t;

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

Elapsed: 00:00:00.12

newkid

一开始用的方法是手工把所有相邻的线段写出来：

把12段从上到下，从左到右编号：

  1   2
3   4   5
  6   7
8   9  10
11  12

with s as (
SELECT level n,power(2,level) b from dual connect by level<=12
)
,c as (
select s1.b b1,s2.b b2,s1.b+s2.b b
  from s s1,s s2
where (s1.n,s2.n) in ((1,2),(1,3),(1,4) -------手工枚举所有相邻的线段对
                      ,(2,4),(2,5)
                      ,(3,6),(3,8)
                      ,(4,6),(4,7),(4,9)
                      ,(5,7),(5,10)
                      ,(6,7),(6,8),(6,9)
                      ,(7,9),(7,10)
                      ,(8,11)
                      ,(9,11),(9,12)
                      ,(10,12)
                      ,(11,12)
                      )
)                     
,t (b,rn) as (
select b,1 from s
union all
select t.b+c.b-bitand(t.b,c.b)  --- bitor
      ,row_number() over(partition by t.b+c.b-bitand(t.b,c.b) order by 1) rn
  from t,c
where t.rn=1  ------- 去重复
       and bitand(t.b,c.b) in (c.b1,c.b2)
)
select count(distinct b) from t;


改成 N 之后，N=4还是跑不出来，必须另想办法。

〇〇

peter的能画出111110000000我就觉得他对了，没想到还有newkid的图

〇〇

@newkid 用对称能算n=4吗

〇〇

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

VAR N NUMBER;

SQL> VAR N NUMBER;
SQL> EXEC :N:=4;

PL/SQL procedure successfully completed.

Elapsed: 00:00:00.01
SQL>
SQL> VAR rN NUMBER;
SQL> EXEC :rN:=3;

PL/SQL procedure successfully completed.

Elapsed: 00:00:00.01
SQL> /

COUNT(DISTINCTB)
----------------
           38910

Elapsed: 00:00:10.60

3*4还是比较快的

lugionline

快有什么用，要对
看这图能不能杀死pub

solomon_007

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

呵呵，都被你秒了

lugionline

发现我的社区积分竟然是-1，做这个论坛的真是个人才啊