puzzleup 2018

〇〇

solomon_007 发表于 2018-11-22 16:33
一个方格的情形正确答案这样写才对：

SQL> with point(n,x,y) as (select level n,ceil(level/2),deco ...

就是我在259楼说的

〇〇

peter1166 发表于 2018-11-22 19:10
--------------------------------------
设，如有4个点，4个线段

非常高效
       CNT
----------
      1609
已用时间:  00: 00: 00.51

〇〇

把peter的参数化了
var nc number
var nr number
exec :nc:=3
exec :nr:=3
with point (n,a,b) as(
select level,ceil(level/:nc),mod(level-1,:nc)+1 from dual connect by level<=:nc*:nr),
t(n,x,y)as(select chr(rownum+64),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),
s(s,c) as(select listagg(n) within group(order by 1),count(*) from t)
SELECT  count(DISTINCT TRANSLATE(TRANSLATE(s,replace(sys_connect_by_path(n,',') ,',',''),lpad('1',c,'1')),s,lpad('0',c,'0'))) str
FROM t,s
CONNECT BY  NOCYCLE
    x IN (PRIOR x,PRIOR y)
OR  y IN (PRIOR x,PRIOR y)
order by 1;
但是也就算到3x4,更大没敢试
       STR
----------
      1609
已用时间:  00: 00: 00.54
SQL> exec :nr:=4
PL/SQL 过程已成功完成。
已用时间:  00: 00: 00.00
SQL> /
       STR
----------
     30074
已用时间:  00: 00: 41.29

peter1166

〇〇 发表于 2018-11-22 20:23
把peter的参数化了
var nc number
var nr number

谢谢 OO 对程序的改进。
确实 4*4  5分钟都没算出来。
大的数 CONNECT BY 就不好用了。

newkid

peter1166 发表于 2018-11-22 22:00
谢谢 OO 对程序的改进。
确实 4*4  5分钟都没算出来。
大的数 CONNECT BY 就不好用了。

我算的是1759, 在和你对答案时，发现这个不在你的答案里面：
111110011100
不知道CONNECT BY为什么把它滤掉。

newkid

我本来在248楼发的贴是这样：

"
#17 DIGITAL DISPLAY

A 2x2 digital display consists of 12 segments. You will create a shape by turning some of the segments on. Rules:

At least one of the segments will be on.
When multiple segments are on, those segments will form a connected shape.

How many different shapes can be created?

For example, for a square-shaped display with 4 segments, the answer would be 13.
1 shape with all segments on; 4 shapes for one, two or three turned on segments each.

一个2x2的数字显示屏由12段组成（形状如汉字的"田"，由12段发光二极管构成）。 你可以通过点亮一些段来创建形状。规则：

至少有一段被点亮。
当多个段被点亮时，这些段将构成连通的形状。

总共可以创建多少种不同的形状？

例如，对于具有4个段的方形显示屏，答案为13。
所有段都点亮，这是1种形状；
一段，两段或三段点亮，每种情形各有4种形状。  
-----------------
这个是可以用SQL玩出来的。
"

就因为发了两个图片，这个人工智障鉴黄师就把帖子关了小黑屋，一整天了还没放出来。简直就是个变态色情狂！

newkid

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

跟踪了一下你的代码，明白了，你这做法有个缺陷，拼接上的边一定要和上一次的边连续。我列出的那个形状不是这样，它可能是和上上次的边连续。

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