2022 PUZZLEUP

jihuyao

newkid 发表于 2023-2-9 01:04
上次的写法剪枝手段单一，只是判断每条边被同一颜色的三角形覆盖不超过两次，其实对应每个三角形的三种上色 ...

My last reply seems delayed.  But I do get through the 8-based logic in following sql with 5 step (6-based logic with 4 steps is simpler without need to split rows in step3).  10/12-based logic should be similar to 8-based (revise step3).  It may be worth to comare 12-based result with 6-based result (process twice) for 12 people.  I am wondering that perform various-based logic for given number of people may cover all possible valid solutions (for condition 3) including minimum and maximum values.  Some sytematic work may tell more secrets.

Below shows the sql for 8-based logic flow for 3-member group and 8 people.  Using PL/SQL should be simpler with function perform repeating logic.


      SIDE GRP
---------- -----
         1 ABC
         1 ADG
         1 AEH
         1 BDF
         1 CEF
         1 FGH
         2 ABD
         2 ACE
         2 BCF
         2 AGH
         2 DFG
         2 EFH

12 rows selected.



TOTAL_UNIQUE_GROUP
------------------
                12




with t as (select rownum n from dual connect by rownum<=3
), t0 as (select 1 id, 'ABCDEFGH' s from dual
), step1 as (select substr(s, 1, 3) grp from t0
), step2a as (select replace(grp, substr(grp, n, 1)) pair from step1, t
), step2b as (select row_number() over (order by pair) rn, pair from step2a
), step2 as (select rn, pair||substr(s, 3+rn,1) grp from step2b, t0
), step3a as (select rn, replace(grp, substr(grp, n, 1)) pair from step2, t where n<=2
), step3b as (select dense_rank() over (order by substr(pair,1,1)) rn2, rn, pair from step3a
), step3c as (select pair||substr(s, 6+rn,1) grp from step3b, t0 where rn2=1
), step3d as (select replace(grp, substr(grp, n, 1)) pair from step3c, t where n<=2
), step3e as (
select substr(pair,1,1)||listagg(substr(pair, 2,1)) within group (order by rn) grp
from step3b where rn2>1 group by substr(pair, 1,1)
), step3f as (select grp from step3c union all select grp from step3e
), step3 as (select row_number() over (order by grp) rn, grp from step3f
), step4a as (select replace(grp, substr(grp, n, 1)) pair from step3, t where n<=2 and rn<=2
), step4b as (select substr(grp, 2) pair from step3 where rn>=3
), step4c as (select pair from step4a union all select pair from step4b
), step4d as (select dense_rank() over (order by substr(pair,1,1)) rn, pair from step4c
), step4 as (
select substr(pair,1,1)||listagg(substr(pair, 2,1)) within group (order by rn) grp
from step4d group by substr(pair, 1,1)
), step5a as (select substr(grp, 2, 1) member from step4 union select substr(grp, 3, 1) member from step4
), step5 as (select listagg(member) within group (order by member) grp from step5a
), result as (
select 1 side, grp s from step1 union all select 1, grp from step3 union all select 1, grp from step5
union all select 2, grp from step2 union all select 2, grp from step4
), 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 result)
)
--select side, s grp from result
select cnt total_unique_group from group_count
/

newkid

北京时间凌晨十二点到早上七点之间发帖都会被审核。你可以给我发个站内短信，我就会把你放出来。
等下周有空好好研究一下你的程序。

newkid

jihuyao 发表于 2023-2-11 10:45
My last reply seems delayed.  But I do get through the 8-based logic in following sql with 5 step (6 ...

你这个还是和185楼一样的文字游戏，就是按照某种规律凑出符合答案的三角形名称。我189楼的程序是有严密逻辑的，尝试了所有三角形的三种上色方法得到最小的解。

像你这种做法我也很容易写出来，比如偶数个数的，可以找到 (N-2)*2的答案（陀螺状的几何体）：

VAR N NUMBER;
EXEC :N:=8;


with v as (--- 所有顶点，AB去掉做陀螺的两个顶点，剩下的围城圆环，为了首位相接最后拼上一个字母C
(select substr(replace(sys_connect_by_path(chr(64+level),','),','),3)||'C' v
  from dual
  where level=:N
  connect by level<=:N)
)
select v1||v3,mod(grp1+grp2,2)
  from (
select substr(v,level,2) v3, mod(level,2) grp1
from v
connect by level<=:N-2
)
cross join (select 'A' v1,0 grp2 from dual union all select 'B',1 from dual);

V1||V3    MOD(GRP1+GRP2,2)
--------- ----------------
ACD                      1
BCD                      0
ADE                      0
BDE                      1
AEF                      1
BEF                      0
AFG                      0
BFG                      1
AGH                      1
BGH                      0
AHC                      0
BHC                      1

jihuyao

newkid 发表于 2023-2-12 06:29
你这个还是和185楼一样的文字游戏，就是按照某种规律凑出符合答案的三角形名称。我189楼的程序是有严密逻辑 ...

The logics for 6-based or 8-based or others does not guarantee the result is minimum.  It needs some systematic work to find the trend or pattern in order to decide which x-based logic should be used to obtain the minimum value for given N people.  But for any given x-based logic, its flow is exactly defined, eg, for 8-based step 2 adds 3 new people and step 3 adds 2 new people (for 10 people, one can add 4, for 12 people one can add 6) so in total 8 people (include 3 people in step 1 always) are involved in a loop which closes itself at last step (step 5 for 8-based).  This is guaranteed by its logic.  The sql used is just following some simple rules which can be easily see in a logic flow on paper (I could not copy/paste a photo object here somehow).

jihuyao

newkid 发表于 2023-2-12 02:49
北京时间凌晨十二点到早上七点之间发帖都会被审核。你可以给我发个站内短信，我就会把你放出来。等下周有空 ...

I have 2 locked up.  But no hurry.

My understanding now is that with geometry approach one can directly tell the minimum value for given 2*n people (n>=3) without really running the program.  That is very impressive.

Maybe you can find a hidden pattern for odd numbers (>=9) people.  Is there any specific obstacle for that in geometry approach?

newkid

你185楼说有9个人的答案，是多少？
我猜是(10-2)*2=16
偶数的规律我总结出来了，奇数的似乎就是加上4, 我也看出了点规律。

newkid

                 
当 N 为奇数，先用前述方法把 N-1 的陀螺状物体构造出来。

选择底座上四个点CDEF，考察两个三角形ACD和AEF(其实任何两个同颜色的三角形都可以, 不妨假设这两个是红色)
对这两个三角形进行替换, 颜色不变, ACD换成ACE, AEF换成ADF
替换后, AD和AE这两条边被两个三角形互换, 颜色依然保持平衡。
不平衡的边是CD,EF,各自缺少一条红色边; 而新增的两条交叉的边CE和DF只有红色,各自缺少一条蓝色边。
除此之外所有三角形的边都保持平衡。
为了更加容易想象,把EF扭转一下，位置对换,底座变成四边形CDFE, 这样就不会交叉,四条边刚好两种颜色交错出现。
经过上述拓扑等价变换，现在把最后一个点, N点加进去, 以CDFE为底座, 补进去四条边, 形成四个新的三角形,两红两蓝,颜色交错, 四条侧边的颜色正好相互平衡，而底部四条边和上一步骤的颜色恰好平衡。
NCD红色, NDF蓝色, NFE红色, NCE蓝色
这样的话,所有的点都被覆盖,所有的边都颜色平衡了。

奇数N写成SQL构造方法:


奇数:
VAR N NUMBER;
EXEC :N:=9;

create table r13 (tri varchar2(3),grp number);

insert into r13
with v as (--- 所有顶点，AB去掉做陀螺的两个顶点，剩下的围城圆环，为了首位相接最后拼上一个字母C
(select replace(sys_connect_by_path(chr(66+level),','),',')||'C' v
  from dual
  where level=:N-3
  connect by level<=:N-3)
)
,r1 as (
select v1||v3 tri,mod(grp1+grp2,2) grp
  from (
select substr(v,level,2) v3, mod(level,2) grp1
from v
connect by level<=:N-3
)
cross join (select 'A' v1,0 grp2 from dual union all select 'B',1 from dual)
)
select decode(tri,'ACD','ACE','AEF','ADF',tri) as tri
      ,grp
  from r1
UNION ALL SELECT CHR(64+:N)||'CD',1 FROM DUAL
UNION ALL SELECT CHR(64+:N)||'DF',0 FROM DUAL
UNION ALL SELECT CHR(64+:N)||'EF',1 FROM DUAL
UNION ALL SELECT CHR(64+:N)||'CE',0 FROM DUAL
;


select * from r13;

TRI        GRP
--- ----------
ACE          1
BCD          0
ADE          0
BDE          1
ADF          1
BEF          0
AFG          0
BFG          1
AGH          1
BGH          0
AHC          0
BHC          1
ICD          1
IDF          0
IEF          1
ICE          0

16 rows selected.

---- 检验条件2, 所有点都被两种颜色覆盖到,次数不限
WITH
d as (select tri,substr(tri,n,1) d,  grp from r13,(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             0          3
A             1          3
B             0          3
B             1          3
C             0          3
C             1          3
D             0          3
D             1          3
E             0          3
E             1          3
F             0          3
F             1          3
G             0          2
G             1          2
H             0          2
H             1          2
I             0          2
I             1          2

18 rows selected.


---- 检验条件3, 任意点构成的边被两种颜色覆盖次数一样多
WITH d1 as (select tri
      ,decode(n,1,substr(tri,1,2),2,substr(tri,2,2),substr(tri,1,1)||substr(tri,3,1)) as e
      ,grp
  from r13,(select level n from dual connect by level<=3)
)
,d as (
select least(substr(e,1,1),substr(e,2,1))||greatest(substr(e,1,1),substr(e,2,1)) e,grp from d1 ----将每条边两个字母进行排序
)
select e,count(decode(grp,1,1)) c1,count(decode(grp,0,1)) c2
  from d
  group by e
  order by 1
;


E                C1         C2
-------- ---------- ----------
AC                1          1
AD                1          1
AE                1          1
AF                1          1
AG                1          1
AH                1          1
BC                1          1
BD                1          1
BE                1          1
BF                1          1
BG                1          1
BH                1          1
CD                1          1
CE                1          1
CH                1          1
CI                1          1
DE                1          1
DF                1          1
DI                1          1
EF                1          1
EI                1          1
FG                1          1
FI                1          1
GH                1          1

24 rows selected.

jihuyao

newkid 发表于 2023-2-15 03:52
你185楼说有9个人的答案，是多少？我猜是(10-2)*2=16偶数的规律我总结出来了，奇数的似乎就是加上4, 我也看 ...

I found a valid one for 7, using 6-based logic.  9 also can use 6-based logic.
For 7 (ABCDEFG), remove DEF from both sides give total 2*8-2=14 (may not be the minimum but meet all conditions)

        RN S1  S2
---------- --- ---
         1 DEA ABD
         1 CEF FBC
         1 DBF AEC
         1 ABC DEF
         2 GEB DAF
         2 GAD DEG
         2 DEF GAB
         2 FAB BEF

8 rows selected.


TOTAL_UNIQUE_GROUP
------------------
                15


with t as (select rownum n from dual connect by rownum<=3
), t0 as (select 1 rn, 'ABCDEF' s from dual union all select 2 id, 'DEFGAB' s from dual
), t1 as (select rn, substr(s, 1, 3) s1, substr(s,4,3) s2 from t0
), t2 as (select rn,
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 rn, s1, s2 from t1
union all
select rn, 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 rn
select cnt total_unique_group from group_count
/


For 9 (ABCDEFGHI),  remove DEF from both sides give total 2*8-2=14 (may not be the minimum but meet all conditions)


        RN S1  S2
---------- --- ---
         1 DEA ABD
         1 CEF FBC
         1 DBF AEC
         1 ABC DEF
         2 GEI DHF
         2 GHD DEG
         2 DEF GHI
         2 FHI IEF

8 rows selected.


TOTAL_UNIQUE_GROUP
------------------
                15



So given any N people >=6, 6-based logic can be used though the result does ont guarantee it is minimum.

jihuyao

I tried math logic for samll N (eg 4, 5) with both sides have 1, 2, 3, ... groups (XYZ) and it gets no valid solution.  I also considered N=6 for completely brutal force with some constraint help, which looks not too bad.  I guess 6 can be solved by pure math logic analysis.  The hidden constaints being enforced by all given conditions include, both sides must have the same number of groups, and each person must appear the same times on both sides (besides at least once).

I have to spend more time to understand the geometry approach by reading those posts from the very beginning.  I am used to hang hard problems for weeks or even longer.

newkid

下面试图从另一个角度来求最小值。
任取一个三角形ABC, 假设为红色，那么为了取得平衡，AB边必须有另外一个蓝色三角形，AC边也必须有另外一个蓝色三角形，而且这两个蓝色三角形不能重叠，因为ABC只允许一种颜色。这样的话又会多出两条蓝边AD和AE,而为了和它们平衡，至少得有一个红色三角形ADE。所以对于任何一个顶点，它至少被四个三角形所覆盖。而且三角形总数必须是偶数。
因此理论上的最小值是 CEIL(N*4/(3*2))*2。实际上根据N的不同取值，不一定能够画出来。
当N=12, 最少就是16个，而分成两个六人组恰好满足。
现在有趣的是11人，它没办法分成两组，而按照我上面的画法, 11人的答案是20，难道11人比12人的答案更大？