puzzleup 2018

newkid

既然数学哥也同意了，那就没问题：

VAR M NUMBER;
VAR N NUMBER;
EXEC :M :=3;
EXEC :N :=3;

With d as ( -------所有点
select x,y,row_number() over(order by x,y) id
  from (select level-1 x from dual connect by level<=:M+1)
      ,(select level-1 y from dual connect by level<=:N+1)
)
,e as (------所有边
select rownum id
     , power(2,rownum) eb -------每条边用一位二进制表示
     , ee.*
from (SELECT  d1.x x1,d1.y y1,d2.x x2,d2.y y2
         FROM d d1,d d2
        WHERE d1.id<d2.id and (abs(d1.x-d2.x),abs(d1.y-d2.y)) in ((0,1),(1,0))
       order by d1.x,d2.x,d1.y,d2.y
        ) ee
)
,c as (------每个格子以其最小坐标的点做代表
select power(2,d.id) id  -------每个格子用一位二进制表示
      ,sum(e.eb) eb ---------这个格子的四条边的四个二进制位
      ,d.x
      ,d.y
  from d
      ,e  ------ 构成方块的四条边
where d.x<:M and d.y<:N
      and (e.x1,e.y1,e.x2,e.y2) in
            ((d.x,d.y,d.x,d.y+1)
            ,(d.x,d.y,d.x+1,d.y)
            ,(d.x+1,d.y,d.x+1,d.y+1)
            ,(d.x,d.y+1,d.x+1,d.y+1)) ---- 四条边的端点坐标
group by d.id,d.x,d.y
)
,connects as ( -------找出所有相邻的方格
select c1.id id1,c2.id id2,c1.id+c2.id cb,c1.eb eb1,c2.eb eb2
  from c c1,c c2
where c1.id<c2.id
       and (abs(c1.x-c2.x),abs(c1.y-c2.y)) in ((0,1),(1,0))
)
,closed(cb,eb,rn) as (  --------找出所有单个的封闭区域(由若干个相邻的方格构成)
----- cb:构成区域的所有方块，eb:该区域的外轮廓  rn:用于去重复
select id,eb,1 from c
union all
select closed.cb+connects.cb-bitand(closed.cb,connects.cb) ------- BITOR加上新的方格
      ,closed.eb+decode(bitand(closed.cb,connects.id1),0,connects.eb1,connects.eb2) ------- BIT XOR加上新的轮廓，用XOR是因为区域内部的段都不能点亮，只需要外轮廓
           -2*bitand(closed.eb,decode(bitand(closed.cb,connects.id1),0,connects.eb1,connects.eb2))
      ,row_number() over(partition by closed.cb+connects.cb-bitand(closed.cb,connects.cb)  order by 1) rn ---按照区域形状去重复
  from closed,connects
where closed.rn=1
       and (bitand(closed.cb,connects.id1),bitand(closed.cb,connects.id2))
            IN ((connects.id1,0),(0,connects.id2)) --- 两个连续的方格有一个在区域中，另一个在区域外
)
,area as (select distinct cb,eb from closed)
,shapes(bits,cb,eb) as ( -----所有封闭区域的组合
select cb,cb,eb from area
union all
select shapes.bits+area.cb,area.cb, shapes.eb+area.eb-bitand(shapes.eb,area.eb) ---BITOR 拼上新轮廓
from shapes,area
where shapes.cb<area.cb and bitand(shapes.bits,area.cb)=0
)
select count(DISTINCT eb) from shapes;

solomon_007

Perfect!

〇〇

newkid 发表于 2018-12-9 09:40
既然数学哥也同意了，那就没问题：

VAR M NUMBER;

COUNT(DISTINCTEB)
-----------------
            12711

Elapsed: 00:00:00.59
SQL> EXEC :M :=4

PL/SQL procedure successfully completed.

Elapsed: 00:00:00.00
SQL> /

COUNT(DISTINCTEB)
-----------------
           403352

Elapsed: 00:00:53.41
这个不用物理表还可以

newkid

〇〇 发表于 2018-12-10 08:43
COUNT(DISTINCTEB)
-----------------
            12711

你这个算的是4*3，不是4*4。

newkid

#20  CODE SETS

You will create code sets using A, B, C, D, E, F letters.

A set contains at least two codes.
Each letter is used exactly once by the code set.
Each code contains at least two letters.
When the order of codes in the set changes, it is still considered the same code set.
When the order of letters in a code changes, the code set is considered different.

How many different code sets can be created?

If the question were asked for A,B,C,D letters, the answer would be 12.

(AB, CD), (AB, DC), (AC, BD), (AC, DB), (AD, BC), (AD, CB), (BA, CD), (BA, DC), (CA, BD), (CA, DB), (DA, BC), (DA, CB).

你用A，B，C，D，E，F字母创建代码集。

一个集合少包含两个代码。
每个字母在集合中恰好被使用一次。
每个代码至少包含两个字母。
当集合中的代码顺序发生变化时，它仍被视为相同的代码集。
当代码中的字母顺序发生变化时，代码集会被视为不同。

总共可以创建多少个不同的代码集？


如果询问A，B，C，D字母的问题，答案将是12。

（AB，CD），（AB，DC），（AC，BD），（AC，DB），（AD，BC），（AD，CB），（BA，CD），（BA，DC），（CA ，BD），（CA，DB），（DA，BC），（DA，CB）。

--------------
这道题很弱，白送加菲猫一个章。
我记得以前就出过，懒得找了。

solomon_007

20#

n=4

SQL> with t as (select chr(64+level) c,power(2,level) b from dual connect by level <= 4),
  2       code(lvl,str,bsum) as (select 1,c,b from t
  3                           union all
  4                         select lvl + 1,
  5                                str||t.c,
  6                                bsum + t.b
  7                           from code,t
  8                          where bitand(bsum,t.b) = 0 ),
  9       valid_code(str,bsum) as (select str,bsum from code where lvl between 2 and 2),
10       set_code(lvl,set_str,set_sum) as (select 1,'('||str,bsum from valid_code
11                                          union all
12                                         select lvl + 1,
13                                                set_str||','||valid_code.str,
14                                                set_sum + bsum
15                                           from set_code,valid_code
16                                          where bitand(set_sum,bsum) = 0
17                                            and set_sum < 30 )    -- 2^1 + 2^2 + ... + 2^4 = 30
18  select sum(res)
19    from (
20          select lvl,count(set_str||')')/(case when lvl = 2 then 2 else 2 end) res
21            from set_code
22           where lvl >= 2
23             and set_sum = 30  
24           group by lvl
25         )
26  /
  SUM(RES)
----------
        12


n=6

SQL> with t as (select chr(64+level) c,power(2,level) b from dual connect by level <= 6),
  2       code(lvl,str,bsum) as (select 1,c,b from t
  3                           union all
  4                         select lvl + 1,
  5                                str||t.c,
  6                                bsum + t.b
  7                           from code,t
  8                          where bitand(bsum,t.b) = 0 ),
  9       valid_code(str,bsum) as (select str,bsum from code where lvl between 2 and 4),
10       set_code(lvl,set_str,set_sum) as (select 1,'('||str,bsum from valid_code
11                                          union all
12                                         select lvl + 1,
13                                                set_str||','||valid_code.str,
14                                                set_sum + bsum
15                                           from set_code,valid_code
16                                          where bitand(set_sum,bsum) = 0
17                                            and set_sum < 126 )   -- 2^1 + 2^2 + ... + 2^6 =126
18  select sum(res)
19    from (
20          select lvl,count(set_str||')')/(case when lvl = 2 then 2 else 6 end) res     -- n=6,lvl 只能是2和3，重复数就是 2！和 3！，lvl=4的不存在，因为集合中如果有4个及以上的CODE，那长度至少为8了。
21            from set_code
22           where lvl >= 2
23             and set_sum = 126
24           group by lvl
25         )
26  /
  SUM(RES)
----------
      1200

solomon_007

newkid 发表于 2018-12-12 23:04
#20  CODE SETS

You will create code sets using A, B, C, D, E, F letters.

随便送个章章

今年的PUZZLE又结束了，几乎都没人玩了  

newkid

随便转了个弗兰奇。
我的写法：

EXEC :N:=6;

with c as (
select CHR(ascii('A')+level-1) as c,power(2,level-1) as id from dual connect by level<=:N
)
,codes(b,cnt,c) as (
select id,1,cast(c as varchar2(20)) from c
union all
select b+id,cnt+1,codes.c||c.c from codes,c where bitand(b,id)=0 and cnt<:N-1
)
,sets(b,c,last_code) as (
select b,cast(c as varchar2(200)),c from codes where cnt>1
union all
select sets.b+codes.b,sets.c||','||codes.c,codes.c
from sets,codes where bitand(sets.b,codes.b)=0 and sets.last_code<codes.c and codes.cnt>1
)
select COUNT(*) from sets where b=power(2,:N)-1;

lugionline

在MMA的强大攻势下，完全不堪一击

In[2]:= 6!*(1/1! + 1/2! + 1/3!)
Out[2]= 1200

solomon_007

newkid 发表于 2018-12-13 06:23
随便转了个弗兰奇。
我的写法：

的确，2指数应该按0算起，这样就是 2^n-1 算总和；
另外，sets.last_code<codes.c  加个排序就不重复了；
学习了！