puzzleup 2018

solomon_007

19 #

SQL> with function fn_val (p_nlist in varchar2)
  2    return int
  3    is
  4      l_res int := 0;
  5    begin
  6      with t as (
  7          select a.nlist,a.n,p1,p2
  8            from (
  9                  select nlist, regexp_substr(nlist, '[^,]+', 1, level) n
10                    from (select p_nlist nlist from dual)
11                  connect by level <= regexp_count(nlist, ',') + 1
12                 ) a,
13                 t_line b
14           where a.n = b.n),
15           s (lvl,nlist,val,sp,ep) as (select 1,n,power(2,n),p1,p2 from t
16                                 union all
17                               select s.lvl + 1,
18                                      s.nlist||','||t.n,
19                                      s.val + power(2,t.n),
20                                      s.sp,
21                                      case when s.ep = t.p1 then t.p2
22                                           when s.ep = t.p2 then t.p1
23                                      end
24                                 from s,t
25                                where bitand(s.val,power(2,t.n))=0
26                                  and (s.ep = t.p1 or s.ep = t.p2)
27                                 )
28          select sum(power(2,first_node))
29            into l_res
30            from (
31          select distinct substr(nlist,1,instr(nlist,',',1,1)-1) first_node
32           from s
33          where sp = ep
34          );
35      return l_res;
36    end;
37    t_point (n, x, y) as (
38        select level n,
39               ceil(level / 3),
40               decode(mod(level, 3), 0, 3, mod(level, 3))
41          from dual
42        connect by level <= 9),
43      t_line (n,p1,p2) as (
44        select rownum, p1.n, p2.n
45          from t_point p1, t_point p2
46         where abs(p1.x - p2.x) + abs(p1.y - p2.y) = 1
47           and p1.n < p2.n ),
48      shape (lvl,nlist,val,plist,rn) as (select 1,
49                                                cast(n as varchar2(100)),
50                                                power(2,n),
51                                                p1||','||p2,
52                                                1
53                                           from t_line
54                                        union all
55                                        select s.lvl + 1,
56                                               s.nlist||','||a.n,
57                                               s.val + power(2,a.n),
58                                               s.plist||','||a.p1||','||a.p2,
59                                               row_number() over(partition by s.lvl+1,s.val + power(2,a.n)
60                                                                 order by s.val + power(2,a.n)
61                                                                ) rn
62                                        from shape s,t_line a
63                                       where bitand(s.val,power(2,a.n))=0
64                                         and (instr(s.plist,a.p1) > 0
65                                              or instr(s.plist,a.p2) > 0)
66                                         and lvl < 12
67                                         and rn = 1),
68      t_shape (lvl,val,nlist) as (
69        select lvl,val,min(nlist) nlist
70          from shape
71         group by lvl,val
72         order by lvl,val )
73     select count(t.nlist)
74       from T_SHAPE t
75      where fn_val(t.nlist) = val
76  
77  /
COUNT(T.NLIST)
--------------
            42       

solomon_007

newkid 发表于 2018-12-6 22:20
脚趾头不够用了，得向老婆借：
jsu@JSU12P> exec :m:=2;

一个纯SQL好难写，还是用个函数算了。

基本思路： 根据17题的结果，如果一个形状是由一个或多个环组成，
那么，从该图中的任何一点出发至少能找到一个封闭路径，如果
图中所有的点都满足，那么就是符合该题结果的图，不管其有多少
个环。

newkid

我原来的做法是把M*N的格子看成M*N点阵，求出所有连续的格子构成封闭区域，然后再求互不重叠的区域组合。
没想到3X3的时候出现了"回"字型，不管实心空心，其灯管都是一样的。这样我求出来的形状就会有重复。我打算把形状的轮廓描绘出来再去重复，这样代码会更复杂些。
数学哥的答案怎么比我还多呢？你能不能用某种文本表示法贴出来？
加菲猫也做做3X3。

newkid

新算法的3X3结果：

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

Elapsed: 00:00:00.30

大家都来对对答案。

newkid

solomon_007 发表于 2018-12-7 20:31
一个纯SQL好难写，还是用个函数算了。

基本思路： 根据17题的结果，如果一个形状是由一个或多个环组 ...

你这SQL在我的12.2下报错：
ERROR at line 10:
ORA-06552: PL/SQL: ORA-00942: table or view does not exist

我看了一下你的函数里竟然引用了WITH子句里面的表t_line? 这样也行？

solomon_007

newkid 发表于 2018-12-8 03:56
你这SQL在我的12.2下报错：
ERROR at line 10:
ORA-06552: PL/SQL: ORA-00942: table or view does not ...

我是后来改成的一条SQL ，先的时候我也是分步算了，建了表的。
不合适的，函数里可以将t_line,直接改成子查询。

solomon_007

newkid 发表于 2018-12-7 22:22
我原来的做法是把M*N的格子看成M*N点阵，求出所有连续的格子构成封闭区域，然后再求互不重叠的区域组合。
...

我觉得，3*3 的情形，17题的结论对于本题 3*3 的情形可能不能直接引用，因为17题称有效形状要连续，
但本题 3*3 的情形，如果是分离的多个环，17题的有效形状就不可能会包含这样的情形。 我上面的
函数的判断好像也无效了。比如两个独立的环，一条线连接，端点在环上，但这个线不在。

newkid

我没用17题思路，拼接边不如拼接方块。你可以继续你的尝试。

solomon_007

solomon_007 发表于 2018-12-8 09:10
我是后来改成的一条SQL ，先的时候我也是分步算了，建了表的。
不合适的，函数里可以将t_line,直接改 ...

改成下面这样，重复啰嗦地效的SQL:

SQL> with function fn_val (p_nlist in varchar2)
  2          return int
  3          is
  4            l_res int := 0;
  5          begin
  6            with t as (
  7                select a.nlist,a.n,p1,p2
  8                  from (
  9                        select nlist, regexp_substr(nlist, '[^,]+', 1, level) n
10                          from (select p_nlist nlist from dual)
11                        connect by level <= regexp_count(nlist, ',') + 1
12                       ) a,
13                       (
14                       select row_number() over(order by p1.n,p2.n) as n, p1.n p1, p2.n p2
15                         from (
16                                select level n,
17                                       ceil(level / 3) x,
18                                       decode(mod(level, 3), 0, 3, mod(level, 3)) y
19                                  from dual
20                                connect by level <= 9
21                               ) p1,
22                             (
23                              select level n,
24                                     ceil(level / 3) x,
25                                     decode(mod(level, 3), 0, 3, mod(level, 3)) y
26                                from dual
27                              connect by level <= 9
28                             ) p2
29                        where abs(p1.x - p2.x) + abs(p1.y - p2.y) = 1
30                          and p1.n < p2.n
31                       ) b
32                 where a.n = b.n),
33                 s (lvl,nlist,val,sp,ep) as (select 1,n,power(2,n),p1,p2 from t
34                                       union all
35                                     select s.lvl + 1,
36                                            s.nlist||','||t.n,
37                                            s.val + power(2,t.n),
38                                            s.sp,
39                                            case when s.ep = t.p1 then t.p2
40                                                 when s.ep = t.p2 then t.p1
41                                            end
42                                       from s,t
43                                      where bitand(s.val,power(2,t.n))=0
44                                        and (s.ep = t.p1 or s.ep = t.p2)
45                                       )
46                select sum(power(2,first_node))
47                  into l_res
48                  from (
49                select distinct substr(nlist,1,instr(nlist,',',1,1)-1) first_node
50                 from s
51                where sp = ep
52                );
53            return l_res;
54          end;
55         t_point (n, x, y) as (
56              select level n,
57                     ceil(level / 3),
58                     decode(mod(level, 3), 0, 3, mod(level, 3))
59                from dual
60              connect by level <= 9),
61            t_line (n,p1,p2) as (
62              select row_number() over(order by p1.n,p2.n), p1.n, p2.n
63                from t_point p1, t_point p2
64               where abs(p1.x - p2.x) + abs(p1.y - p2.y) = 1
65                 and p1.n < p2.n ),
66            shape (lvl,nlist,val,plist,rn) as (select 1,
67                                                      cast(n as varchar2(100)),
68                                                      power(2,n),
69                                                      p1||','||p2,
70                                                      1
71                                                 from t_line
72                                              union all
73                                              select s.lvl + 1,
74                                                     s.nlist||','||a.n,
75                                                     s.val + power(2,a.n),
76                                                     s.plist||','||a.p1||','||a.p2,
77                                                     row_number() over(partition by s.lvl+1,s.val + power(2,a.n)
78                                                                       order by s.val + power(2,a.n)
79                                                                      ) rn
80                                              from shape s,t_line a
81                                             where bitand(s.val,power(2,a.n))=0
82                                               and (instr(s.plist,a.p1) > 0
83                                                    or instr(s.plist,a.p2) > 0)
84                                               and lvl < 12
85                                               and rn = 1),
86            t_shape (lvl,val,nlist) as (
87              select lvl,val,min(nlist) nlist
88                from shape
89               group by lvl,val
90               order by lvl,val )
91           select count(t.nlist)
92             from T_SHAPE t
93            where fn_val(t.nlist) = val
94  /
COUNT(T.NLIST)
--------------
            42

lugionline

有道理，那的确是多算了
全搜了一遍，12711 是正确的