puzzleup 2018

solomon_007

solomon_007 发表于 2018-11-22 16:19
instr(s.plist,a.p1) > 0还有可能把12当成1和2，这个不会，因为2*2 只有9个点，这个不是指边1-12

就是 ...

一个方格的情形正确答案这样写才对：

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                                       )
14  select sum(cnt)
15    from (select lvl, count(distinct val) cnt from shape group by lvl)
16  /
  SUM(CNT)
----------
        13

但对应2*2，这样可能算不出来

peter1166

1609 ?

peter1166

--------------------------------------
设，如有4个点，4个线段

1   2

4   3

   a
d     b
   c
   
线段：前点，后点
   
a: 1 ,2
b: 2, 3
c: 3, 4
d: 1, 4

   
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,  3, 4 FROM dual UNION ALL
SELECT 'd' n,  1, 4 FROM dual
)
SELECT  DISTINCT TRANSLATE(TRANSLATE('abcd',replace(sys_connect_by_path(n,',') ,',',''),'1111'),'abcd','0000') str
FROM t
CONNECT BY  NOCYCLE
    x IN (PRIOR x,PRIOR y)
OR  y IN (PRIOR x,PRIOR y)
;

STR
----------------
0010
1000
1100
0110
1001
1011
0001
0011
1110
0111
0100
1111
1101


13 rows selected


-------------------------------------------------------------------------------------------------------------------
设，如有9个点，12个线段


1   2   3

4   5   6

7   8   9

  a    b
c   d     e
  f    g  
h   i     j
  k    l
   
线段：前点，后点
   
a: 1 ,2
b: 2, 3
c: 1, 4
d: 2, 5
e: 3 ,6
f: 4, 5
g: 5, 6
h: 4, 7
i: 5 ,8
j: 6, 9
k: 7, 8
l: 8, 9

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
)
SELECT  -- DISTINCT TRANSLATE(TRANSLATE('abcdefghijkl',replace(sys_connect_by_path(n,',') ,',',''),'111111111111'),'abcdefghijkl','000000000000') str
        COUNT(DISTINCT TRANSLATE(TRANSLATE('abcdefghijkl',replace(sys_connect_by_path(n,',') ,',',''),'111111111111'),'abcdefghijkl','000000000000') ) cnt
FROM t
CONNECT BY  NOCYCLE
    x IN (PRIOR x,PRIOR y)
OR  y IN (PRIOR x,PRIOR y)
;


       CNT
----------
      1609
      

〇〇

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为什么把它 ...

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