2022 PUZZLEUP

jihuyao

I am still thinking about odd number of people.  Do you think there exists a valid solution for 3-member group and 5 or 7 people?  Can you run your brutal force to get any result?  

newkid

如果要求两个数都大于零，即两两之间必须同时至少参加一个艺术组，一个体育组，那么六个人的答案是12:
ABC1,ABD1,AEF1,BEF1,CDE1,CDF1
ABE2,ABF2,ACD2,BCD2,CEF2,DEF2

六个人的20个三角形全部画满的做法，在前面第九题已经发过了。

五个人我相信是没有答案，等明天来改改程序看看。

newkid

不出所料，五个人是没有答案的，我上面的暴力法不能解七个人，但是我相信也是没有答案的。八个人至少有解，就是把178楼那个四面锥体改成六面锥体就行了。

jihuyao

newkid 发表于 2023-2-6 00:01
如果要求两个数都大于零，即两两之间必须同时至少参加一个艺术组，一个体育组，那么六个人的答案是12:ABC1, ...

In fact, there might be another approach for both pair>=0, eg, put A(B-F), B(C-F), C(D-F), D(E-F), E(F) in a half matrix, and pick some by adding one more person at each end and then find what are missing on art side and sport side and try to adding new group to match each other.  But there still a lot to explore this way.

jihuyao

jihuyao 发表于 2023-2-7 10:18
In fact, there might be another approach for both pair>=0, eg, put A(B-F), B(C-F), C(D-F), D(E-F), E ...

Continue on 3-member group with x people.  Finally break through something. Probably, no valid solution for 5/7 people (need proving it).  But already know 9 has valid answer.  Now I write a simple sql to test 8 and the answer is yes (which may not be the minimum but is valid.  Basically, ABCDEF(GH) can be processed separately, each in 6, {ABCDEF} and {HABCDG}.  The result from sql is as below.  I do think 10 should work the same (totoal 16 possible minimum if not true minimum).  So if I may, I would conclude for people>=8, one can break it down one way or another (6-based or 9-based) to obtain a valid (possible) minimum value.

        ID S1  S2
---------- --- ---
         1 DEA ABD
         1 CEF FBC
         1 DBF AEC
         1 ABC DEF
         2 CAG HDB
         2 CDH HAC
         2 HAB CDG
         2 BDG GAB

8 rows selected.



TOTAL_UNIQUE_GROUP
------------------
                16



Here given the sql for above results

with t as (select rownum n from dual connect by rownum<=3
), t0 as (select 1 id, 'ABCDEF' s from dual union all select 2 id, 'HABCDG' s from dual
), t1 as (select id, substr(s, 1, 3) s1, substr(s,4,3) s2 from t0
), t2 as (select id,
translate(s1, substr(s1, n, 1), substr(s2, 4-n, 1)) s2,
translate(s2, substr(s2, n, 1), substr(s1, 4-n, 1)) s1
from t1, t
), result as (
select id, s1, s2 from t1
union all
select id, s1, s2 from t2
), group_list as (
select s1 s from result union all select s2 s from result
), group_count as (
select count(distinct val) cnt
from (select power(2, ascii(substr(s, 1, 1))-64)+power(2, ascii(substr(s, 2, 1))-64)+power(2, ascii(substr(s, 3, 1))-64) val
from group_list)
)
--select * from result order by id
select cnt total_unique_group from group_count
/


NOTE:  In fact, no need to run {HABCDG}.  Just translate ABCDEF to HABCDG to get 2nd set result from 1st set result.

jihuyao

newkid 发表于 2023-2-6 23:44
不出所料，五个人是没有答案的，我上面的暴力法不能解七个人，但是我相信也是没有答案的。八个人至少有解， ...

Interesting.  It means as long as one can find a corresponding 3D object there should be a valid solution for m people.  I guess to find a maximum solution is easier???  Also to find a valid solution for 4-member group and 8 people or (12???) should not be too hard (at least to find a pattern should be quit helpful).

jihuyao

newkid 发表于 2023-2-6 23:44
不出所料，五个人是没有答案的，我上面的暴力法不能解七个人，但是我相信也是没有答案的。八个人至少有解， ...

Bye the way I did not get into too much on the geometry approach.  Is there any specific reason to use 3D object rather than 2D object, eg hexagon, pentagon, etc.

newkid

完全可以用2D的画线来表示答案，但是比较凌乱。六个人的答案“恰好”适合用3D表示，因为每个三角形都贴在物体的表面，而且每条边仅仅被两个不同颜色的三角形所覆盖。你看看我178楼的描述，这个物体是很容易想象出来的。
如果有穿过物体中心的连线或者三角形，那么3D表示法也会凌乱。
如果你能够跟随178的描述相像出这个三角形，那么任何偶数人数都可以套用，只是把棱锥底部多加几条边而已，它会越变越圆，越来越像陀螺。三角形总数是(N-2)*2。

所以8个人就是(8-2)*2=12个三角形，明显比你16个三角形的答案更小。
你的SQL基本上就是字符串拼凑的文字游戏，看不到计算的痕迹，你得先把你这种做法的道理讲清楚。

newkid

上次的写法剪枝手段单一，只是判断每条边被同一颜色的三角形覆盖不超过两次，其实对应每个三角形的三种上色 情形(0,1,2)的次数都可以加以限制。

--------------------- 改良过的暴力法几秒钟可以算出 7 个人，但是8个人还是无法算

drop table t;

----- 表T存储所有三角形，总共C(N,3)个
create table t as
with d as (
select replace(sys_connect_by_path(c,','),',') s from (
(select chr(64+level) c from dual connect by level<=7)
)
connect by nocycle c>prior  c and level<=3
)
,s as (  --------- 所有三角形的边，N个顶点总共C(N,2)条
select s,power(10,row_number() over(order by s)-1) h  ------ 每条边用十进制的一位表示, 总共需要C(N,2)位
      ,-row_number() over(order by s) id  ---------- 每条边在计数器中的位置，用负数表示，从右边算起，
  from d
where length(s)=2
)
--------- 所有三角形，N个顶点总共C(N,3)个
select /*+ materialize */ t1.s,t1.h,t1.rn,t1.id1,t1.id2,t1.id3
     ,sum(s.b) b   ------- 每个三角形的三个顶点所对应的三个二进制位
from (
select d.s
      ,sum(s.h) h ------- 每个三角形的三条边所对应的三个十进制位
      ,row_number() over(order by d.s) rn
      ,max(decode(s.s,substr(d.s,1,2),s.id))   id1   ------ 这个三角形对应的第一条边在计数器中的位置
      ,max(decode(s.s,substr(d.s,2,2),s.id))   id2   ------ 这个三角形对应的第二条边在计数器中的位置
      ,max(decode(s.s,substr(d.s,1,1)||substr(d.s,3,1),s.id))   id3   ------ 这个三角形对应的第三条边在计数器中的位置
  from d,s
where length(d.s)=3
       and s.s in (substr(d.s,1,2)  ---- 第一条边
                  ,substr(d.s,2,2)  ---- 第二条边
                  ,substr(d.s,1,1)||substr(d.s,3,1)  ---------- 第三条边
                  )
group by d.s
) t1
,(select s,power(2,row_number() over(order by s)-1) b from d where length(s)=1) s ---- N个顶点分别用一个二进制位表示
where instr(t1.s,s.s)>0
group by t1.s,t1.h,t1.rn,t1.id1,t1.id2,t1.id3
;


drop table r1;
drop table r2;

create table r1 (s varchar2(200),cnt1 number,cnt2 number,b1 number,b2 number,h0 number,h1 number,h2 number,cnt number);

create table r2 as select * from r1 where 1=0;


declare
   v_cnt number:=2;
   v_rowcount number;
   v_result varchar2(100);
   NUM number :=7;
   v_pad number :=NUM*(NUM-1)/2;  ---每条边一位，总共需要C(NUM,2)位
begin
      execute immediate 'truncate table r1';

insert into r1
select listagg(s||rn,',') within group(order by s) s  ----- 当前解法的所有三角形
      ,1 as cnt1   ------ 1组三角形总数
      ,1 as cnt2   ------ 2组三角形总数
      ,sum(decode(rn,1,b)) as b1   ------ 1组覆盖哪些顶点
      ,sum(decode(rn,2,b)) as b2   ------ 2组覆盖哪些顶点
      ,0 as h0   ------ 0组覆盖哪些边
      ,sum(decode(rn,1,h)) as h1   ------ 1组覆盖哪些边
      ,sum(decode(rn,2,h)) as h2   ------ 2组覆盖哪些边
      ,2 as cnt
  from t
where s in ('ABC','ABD') ------- 以ABC,ABD为起点，假设ABC分在1组，ABD分在2组
;

   loop
      v_cnt := v_cnt+1;
      execute immediate 'truncate table r2';

      insert into r2
select r.s||decode(n,0,null,','||t.s||n)         as s
      ,decode(n,1,cnt1+1,cnt1)  as cnt1
      ,decode(n,2,cnt2+1,cnt2)  as cnt2
      ,decode(n,1,r.b1+t.b-bitand(r.b1,t.b),r.b1) as b1 ----- 二进制的"OR"算法，表示覆盖哪些顶点
      ,decode(n,2,r.b2+t.b-bitand(r.b2,t.b),r.b2) as b2
      ,decode(n,0,r.h0+t.h,r.h0)  as h0 --------- 0组覆盖的每个边的累计
      ,decode(n,1,r.h1+t.h,r.h1)  as h1 --------- 1组覆盖的每个边的累计
      ,decode(n,2,r.h2+t.h,r.h2)  as h2 --------- 2组覆盖的每个边的累计
      ,V_CNT                      as cnt
  from r1 r,t,(select level-1 n from dual connect by level<=3) ----0: 这个三角形不属于任何组; 1:该三角形属于1组; 2:该三角形属于2组
      ,LATERAL ( ------ 把三条边对应的三种情形已经被覆盖的次数从三个计数器中抠出来
                select to_number(substr(lpad(r.h0,v_pad,'0'),t.id1,1)) as c01 ---- n=0的三边计数器
                      ,to_number(substr(lpad(r.h0,v_pad,'0'),t.id2,1)) as c02
                      ,to_number(substr(lpad(r.h0,v_pad,'0'),t.id3,1)) as c03
                      ,to_number(substr(lpad(r.h1,v_pad,'0'),t.id1,1)) as c11 ---- n=1的三边计数器
                      ,to_number(substr(lpad(r.h1,v_pad,'0'),t.id2,1)) as c12
                      ,to_number(substr(lpad(r.h1,v_pad,'0'),t.id3,1)) as c13
                      ,to_number(substr(lpad(r.h2,v_pad,'0'),t.id1,1)) as c21 ---- n=2的三边计数器
                      ,to_number(substr(lpad(r.h2,v_pad,'0'),t.id2,1)) as c22
                      ,to_number(substr(lpad(r.h2,v_pad,'0'),t.id3,1)) as c23
                  from DUAL
                ) b
where t.rn=V_CNT
       and (r.cnt1<NUM*(NUM-1)*(NUM-2)/12  ------- C(N,3)/2
          or r.cnt2<NUM*(NUM-1)*(NUM-2)/12
       )
       and (n=0 and c01<(NUM-2-greatest(c11,c21)*2)
                and c02<(NUM-2-greatest(c12,c22)*2)
                and c03<(NUM-2-greatest(c13,c23)*2)
            OR n=1 and c11<FLOOR((NUM-2-c01)/2)
                   and c12<FLOOR((NUM-2-c02)/2)
                   and c13<FLOOR((NUM-2-c03)/2)
            OR n=2 and c21<FLOOR((NUM-2-c01)/2)
                   and c22<FLOOR((NUM-2-c02)/2)
                   and c23<FLOOR((NUM-2-c03)/2)
           )
       -- and instr(r.h1,'3')=0 -------因为有六个顶点，每条边最多对应四个三角形(6-2=4)，索引每条边最多被每组覆盖两次，这个十进制位表示累计数，只能出现0,1,2
       -- and instr(r.h2,'3')=0
       ;
      
      v_rowcount :=sql%rowcount;
      if v_rowcount=0 then
         exit;
      end if;
      
      dbms_application_info.set_client_info ('cnt='||v_cnt||' rowcount='||v_rowcount);      

      select min(s) into v_result
      from (
      select *
      from r2
      where b1=power(2,NUM)-1
          and b2=power(2,NUM)-1
          and h1=h2
      order by cnt1+cnt2
      )
      where rownum=1;
      
      if v_result is not null then
         dbms_output.put_line('solution found:'||v_result);
         exit;
      end if;
      
      execute immediate 'truncate table r1';
      
      insert into r1 select * from r2;
      
      commit;
      
      
   end loop;
end;
/

solution found:ABC1,ABD2,ACE2,ADG1,AEF1,AFG2,BCF2,BDF1,CDE1,CDG2,CFG1,DEF2

PL/SQL procedure successfully completed.

Elapsed: 00:00:03.90


---- 检验条件2
WITH r AS (SELECT 'ABC1,ABD2,ACE2,ADG1,AEF1,AFG2,BCF2,BDF1,CDE1,CDG2,CFG1,DEF2' r from dual)
,t as (
select regexp_substr(r,'[^,]+',1,level) s
  from r
connect by level<=REGEXP_COUNT(r,',')+1
)
,d as (select t.s,substr(s,n,1) d, substr(s,-1) grp from t,(select level n from dual connect by level<=3))
select d,grp,count(*)
  from d
  group by d,grp
  order by 1,2
;


D    GRP    COUNT(*)
---- ---- ----------
A    1             3
A    2             3
B    1             2
B    2             2
C    1             3
C    2             3
D    1             3
D    2             3
E    1             2
E    2             2
F    1             3
F    2             3
G    1             2
G    2             2

14 rows selected.

---- 检验条件3
WITH r AS (SELECT 'ABC1,ABD2,ACE2,ADG1,AEF1,AFG2,BCF2,BDF1,CDE1,CDG2,CFG1,DEF2' r from dual)
,t as (
select regexp_substr(r,'[^,]+',1,level) s
  from r
connect by level<=REGEXP_COUNT(r,',')+1
)
,d as (select t.s
      ,decode(n,1,substr(s,1,2),2,substr(s,2,2),substr(s,1,1)||substr(s,3,1)) as e
      ,substr(s,-1) grp
  from t,(select level n from dual connect by level<=3)
)
select e,count(decode(grp,1,1)) c1,count(decode(grp,2,1)) c2
  from d
  group by e
  order by 1
;

E                C1         C2
-------- ---------- ----------
AB                1          1
AC                1          1
AD                1          1
AE                1          1
AF                1          1
AG                1          1
BC                1          1
BD                1          1
BF                1          1
CD                1          1
CE                1          1
CF                1          1
CG                1          1
DE                1          1
DF                1          1
DG                1          1
EF                1          1
FG                1          1

18 rows selected.

jihuyao

The sql I used is supported by the 6 -based logic which is self-contained to ensure condition 3 being met.  If 12 is the minimum for 8 people, there must be a hidden pattern waiting for further exploration.  I will try to follow all possible options on each step and see how it’s loop is closed for 8 people (it might be easier to get all possible combinations (C(8,3)) and try to match each other given 12 on one side and another 12 on the other side based on your result).  Anyway learnt a lot already.  Thanks for the topic.