puzzleup 2021

newkid

dhhb 发表于 2021-10-2 10:59
暴力法对答案：3 种颜色都用上， 5个全联通1320， 分成2，3 两组: 960

比我算出来的少很多，代码贴一下看看？

newkid

〇〇 发表于 2021-10-2 12:33
2,3两组可以手算，3有121 131 123 132 四种，2有 12 13 两种，换颜色，组合后再乘以4个方向

最后算出多少？

〇〇

abc可以和任何不同的2个搭配，6x(6+6)x8, aba只能和非ab组合搭配，6x(4+4)x8,共960

solomon_007

newkid 发表于 2021-10-2 20:17
举个例子，你的答案中有：00**0123图案：001010123右上角的 1 是孤立的。

我不得不求助一个函数了。。。

SQL>  with function f (p_v in varchar2)
  2   return int
  3   is
  4     l_adj_sum int:=0;
  5     l_cnt     int:=0;
  6   begin
  7     for i in 1..9 loop
  8  
  9       if to_number(substr(p_v,i,1)) > 0 then
10           with a(n,x,y) as (select level n,
11                               ceil(level/3) x,
12                               decode(mod(level,3),0,3,mod(level,3)) y
13                          from dual
14                         connect by level<=9)
15              select sum(to_number(substr(p_v,a2.n,1)))
16                into l_adj_sum
17                from a a1,a a2
18               where abs(a1.x-a2.x) + abs(a1.y-a2.y) =1
19                 and a1.n = i;
20  
21            if l_adj_sum > 0 then
22              l_cnt := l_cnt + 1;
23            end if;
24        end if;
25  
26     end loop;
27  
28     if 9-regexp_count(p_v,0)=l_cnt then
29       return 1;
30     else
31       return 0;
32     end if;
33  end;
34  t(c) as (select level-1 from dual connect by level <= 3+1),
35         s(n,v) as (select 1,cast(c as varchar2(10)) from t
36                     union all
37                    select n+1,
38                           s.v||t.c
39                      from s,t
40                     where n < 3*3
41                       and case when t.c > 0 then
42                                     case when mod(n+1,3)=1 then
43                                              case when ceil((n+1)/3) = 1 then 1
44                                                   when ceil((n+1)/3) > 1 and t.c <> substr(s.v,-3,1) then 1
45                                                   else 0
46                                              end
47                                         else
48                                              case when ceil((n+1)/3) = 1 and t.c <> substr(s.v,-1,1) then 1
49                                                   when ceil((n+1)/3) > 1 and t.c <> substr(s.v,-3,1) and t.c <> substr(s.v,-1,1) then 1
50                                                   else 0
51                                              end
52                                    end
53                               else 1
54                          end = 1
55                      )
56   select count(v)
57     from s
58    where regexp_count(v,0)=(3*3-(2*3-1))
59      and n=3*3
60      and instr(v,'1')>0
61      and instr(v,'2')>0
62      and instr(v,'3')>0
63      and f(v)=1
64  /

  COUNT(V)
----------
      2826

〇〇

你的2,3形有几个  substr(v,4,3)=000 or substr2,1||5,1||8,1=000

dhhb

newkid 发表于 2021-10-2 20:17
比我算出来的少很多，代码贴一下看看？

重新算了下, 5个全联通:1866， 分成2，3  ：960 ，合计，2826.

solomon_007

newkid 发表于 2021-10-2 20:17
举个例子，你的答案中有：00**0123图案：001010123右上角的 1 是孤立的。

把 函数中得 SQL 换掉，要快一点：

SQL>
SQL>  with function f (p_v in varchar2)
  2   return int
  3   is
  4     l_adj_sum int :=0;
  5     l_cnt     int :=0;
  6     x         int :=0;
  7     y         int :=0;
  8   begin
  9     for i in 1..9 loop
10  
11       if to_number(substr(p_v,i,1)) > 0 then
12           /*with a(n,x,y) as (select level n,
13                               ceil(level/3) x,
14                               decode(mod(level,3),0,3,mod(level,3)) y
15                          from dual
16                         connect by level<=9)
17              select sum(to_number(substr(p_v,a2.n,1)))
18                into l_adj_sum
19                from a a1,a a2
20               where abs(a1.x-a2.x) + abs(a1.y-a2.y) =1
21                 and a1.n = i;*/
22  
23            x:=ceil(i/3);
24            y:=case when mod(i,3)=0 then 3 else mod(i,3) end;
25  
26            l_adj_sum:=   case when x-1 between 1 and 3 then substr(p_v,(3*(x-2)+y),1)   else 0 end
27                        + case when x+1 between 1 and 3 then substr(p_v,(3*x+y),1)       else 0 end
28                        + case when y-1 between 1 and 3 then substr(p_v,(3*(x-1)+y-1),1) else 0 end
29                        + case when y+1 between 1 and 3 then substr(p_v,(3*(x-1)+y+1),1) else 0 end;
30  
31            if l_adj_sum > 0 then
32              l_cnt := l_cnt + 1;
33            end if;
34        end if;
35  
36     end loop;
37  
38     if 9-regexp_count(p_v,0)=l_cnt then
39       return 1;
40     else
41       return 0;
42     end if;
43  end;
44  t(c) as (select level-1 from dual connect by level <= 3+1),
45         s(n,v) as (select 1,cast(c as varchar2(10)) from t
46                     union all
47                    select n+1,
48                           s.v||t.c
49                      from s,t
50                     where n < 3*3
51                       and case when t.c > 0 then
52                                     case when mod(n+1,3)=1 then
53                                              case when ceil((n+1)/3) = 1 then 1
54                                                   when ceil((n+1)/3) > 1 and t.c <> substr(s.v,-3,1) then 1
55                                                   else 0
56                                              end
57                                         else
58                                              case when ceil((n+1)/3) = 1 and t.c <> substr(s.v,-1,1) then 1
59                                                   when ceil((n+1)/3) > 1 and t.c <> substr(s.v,-3,1) and t.c <> substr(s.v,-1,1) then 1
60                                                   else 0
61                                              end
62                                    end
63                               else 1
64                          end = 1
65                      )
66   select count(v)
67     from s
68    where regexp_count(v,0)=(3*3-(2*3-1))
69      and n=3*3
70      and instr(v,'1')>0
71      and instr(v,'2')>0
72      and instr(v,'3')>0
73      and f(v)=1
74  /

  COUNT(V)
----------
      2826

〇〇

花几秒钟

solomon_007

〇〇 发表于 2021-10-3 12:06
花几秒钟

SQL> set timing on
SQL>
SQL>
SQL> with function f (p_v in varchar2)
  2    return int
  3    is
  4      l_adj_sum int :=0;
  5      l_cnt     int :=0;
  6      x         int :=0;
  7      y         int :=0;
  8    begin
  9      for i in 1..9 loop
10  
11        if to_number(substr(p_v,i,1)) > 0 then
12  
13             x:=ceil(i/3);
14             y:=case when mod(i,3)=0 then 3 else mod(i,3) end;
15  
16             l_adj_sum:=   case when x-1 between 1 and 3 then substr(p_v,(3*(x-2)+y),1)   else 0 end
17                         + case when x+1 between 1 and 3 then substr(p_v,(3*x+y),1)       else 0 end
18                         + case when y-1 between 1 and 3 then substr(p_v,(3*(x-1)+y-1),1) else 0 end
19                         + case when y+1 between 1 and 3 then substr(p_v,(3*(x-1)+y+1),1) else 0 end;
20  
21             if l_adj_sum > 0 then
22               l_cnt := l_cnt + 1;
23             end if;
24         end if;
25  
26      end loop;
27  
28      if 9-regexp_count(p_v,0)=l_cnt then
29        return 1;
30      else
31        return 0;
32      end if;
33   end;
34   t(c) as (select level-1 from dual connect by level <= 3+1),
35          s(n,v) as (select 1,cast(c as varchar2(10)) from t
36                      union all
37                     select n+1,
38                            s.v||t.c
39                       from s,t
40                      where n < 3*3
41                        and case when t.c > 0 then
42                                      case when mod(n+1,3)=1 then
43                                               case when ceil((n+1)/3) = 1 then 1
44                                                    when ceil((n+1)/3) > 1 and t.c <> substr(s.v,-3,1) then 1
45                                                    else 0
46                                               end
47                                          else
48                                               case when ceil((n+1)/3) = 1 and t.c <> substr(s.v,-1,1) then 1
49                                                    when ceil((n+1)/3) > 1 and t.c <> substr(s.v,-3,1) and t.c <> substr(s.v,-1,1) then 1
50                                                    else 0
51                                               end
52                                     end
53                                else 1
54                           end = 1
55                       )
56    select count(v)
57      from s
58     where regexp_count(v,0)=(3*3-(2*3-1))
59       and n=3*3
60       and instr(v,'1')>0
61       and instr(v,'2')>0
62       and instr(v,'3')>0
63       and f(v)=1
64  
65  /

  COUNT(V)
----------
      2826

Executed in 0.393 seconds

solomon_007

函数SQL版的：

SQL>  with function f (p_v in varchar2)
  2     return int
  3     is
  4       l_adj_sum int:=0;
  5       l_cnt     int:=0;
  6     begin
  7       for i in 1..9 loop
  8  
  9         if to_number(substr(p_v,i,1)) > 0 then
10             with a(n,x,y) as (select level n,
11                                 ceil(level/3) x,
12                                 decode(mod(level,3),0,3,mod(level,3)) y
13                            from dual
14                           connect by level<=9)
15                select sum(to_number(substr(p_v,a2.n,1)))
16                  into l_adj_sum
17                  from a a1,a a2
18                 where abs(a1.x-a2.x) + abs(a1.y-a2.y) =1
19                   and a1.n = i;
20  
21              if l_adj_sum > 0 then
22                l_cnt := l_cnt + 1;
23              end if;
24          end if;
25  
26       end loop;
27  
28       if 9-regexp_count(p_v,0)=l_cnt then
29         return 1;
30       else
31         return 0;
32       end if;
33    end;
34    t(c) as (select level-1 from dual connect by level <= 3+1),
35           s(n,v) as (select 1,cast(c as varchar2(10)) from t
36                       union all
37                      select n+1,
38                             s.v||t.c
39                        from s,t
40                       where n < 3*3
41                         and case when t.c > 0 then
42                                       case when mod(n+1,3)=1 then
43                                                case when ceil((n+1)/3) = 1 then 1
44                                                     when ceil((n+1)/3) > 1 and t.c <> substr(s.v,-3,1) then 1
45                                                     else 0
46                                                end
47                                           else
48                                                case when ceil((n+1)/3) = 1 and t.c <> substr(s.v,-1,1) then 1
49                                                     when ceil((n+1)/3) > 1 and t.c <> substr(s.v,-3,1) and t.c <> substr(s.v,-1,1) then 1
50                                                     else 0
51                                                end
52                                      end
53                                 else 1
54                            end = 1
55                        )
56     select count(v)
57       from s
58      where regexp_count(v,0)=(3*3-(2*3-1))
59        and n=3*3
60        and instr(v,'1')>0
61        and instr(v,'2')>0
62        and instr(v,'3')>0
63        and f(v)=1
64  /

  COUNT(V)
----------
      2826

Executed in 3.585 seconds