2022 PUZZLEUP

newkid · 发表于 2022-11-25 00:54

坐标设计：

11,12,13,14,15
21,22,23,24,25
31,32,33,34,35
41,42,43,44,45
51,52,53,54,55

待猜选项总共有20条，横竖各十种。用十个字母大小写来表示，如下：

A B C D E
F＃＃＃＃＃f
G＃＃＃＃＃g
H＃＃＃＃＃h
I＃＃＃＃＃i
J＃＃＃＃＃j
a b c d e

比如A就是第一列从上到下四个，小写a则是第一列从下至上的四个。

未知的格子用＃表示，已知没有的用Ｏ表示。

猜测原则：用二分法，所选的四个格子覆盖未知选项的一半。一开始二十种全部未知，所以第一步选择的四个格子就要覆盖十种。

第一步：猜11,22,23,55，覆盖10种

结果路径Y: A,F,G,g,B,b,C,c,j,e
＃＃＃＃Ｏ
＃＃＃＃＃
＃＃＃Ｏ＃
＃＃＃Ｏ＃
Ｏ＃＃＃＃

路径Y第二步：猜11,25,55,15 (15是故意放空的) 覆盖5种
结果路径YY: A,F,e,j,g
＃＃＃＃Ｏ
＃＃＃＃＃
＃ＯＯＯ＃
＃ＯＯＯ＃
Ｏ＃＃＃＃

路径YY第三步：猜11,25,15,51(15,51是故意放空的)覆盖3种

结果路径YYY: A,F,g
＃＃＃＃Ｏ
＃＃＃＃＃
＃ＯＯＯＯ
＃ＯＯＯＯ
ＯＯＯＯＯ

路径YYY第四步：猜11,15,51,55(15,51,55是故意放空的)覆盖2种

结果路径YYYY: A,F
＃＃＃＃Ｏ
＃ＯＯＯＯ
＃ＯＯＯＯ
＃ＯＯＯＯ
ＯＯＯＯＯ

路径YYYY第五步：猜12,51,52,53(后面三个是故意放空的)覆盖1种

结果路径YYYYY: 则答案为F (五步出结果)

＃＃＃＃Ｏ
ＯＯＯＯＯ
ＯＯＯＯＯ
ＯＯＯＯＯ
ＯＯＯＯＯ

结果路径YYYYN: 则答案为A (五步出结果)

＃ＯＯＯＯ
＃ＯＯＯＯ
＃ＯＯＯＯ
＃ＯＯＯＯ
ＯＯＯＯＯ

结果路径YYYN: 则答案为g (四步出结果)

ＯＯＯＯＯ
Ｏ＃＃＃＃
ＯＯＯＯＯ
ＯＯＯＯＯ
ＯＯＯＯＯ


结果路径YYN: e,j
ＯＯＯＯＯ
ＯＯＯＯ＃
ＯＯＯＯ＃
ＯＯＯＯ＃
Ｏ＃＃＃＃

路径YYN第四步：猜52,11,12,13(后面三个是故意放空的)覆盖1种

结果路径YYNY: 则答案为j (四步出结果)
ＯＯＯＯＯ
ＯＯＯＯＯ
ＯＯＯＯＯ
ＯＯＯＯＯ
Ｏ＃＃＃＃


结果路径YYNN: 则答案为e (四步出结果)
ＯＯＯＯＯ
ＯＯＯＯ＃
ＯＯＯＯ＃
ＯＯＯＯ＃
ＯＯＯＯ＃

结果路径YN: B,C,G,b,c
Ｏ＃＃ＯＯ
＃＃＃＃Ｏ
Ｏ＃＃ＯＯ
Ｏ＃＃ＯＯ
Ｏ＃＃ＯＯ

路径YN第三步：猜22,15,25,35(后面三个是故意放空的)覆盖3种
结果路径YNY: B,G,b
Ｏ＃ＯＯＯ
＃＃＃＃Ｏ
Ｏ＃ＯＯＯ
Ｏ＃ＯＯＯ
Ｏ＃ＯＯＯ

路径YNY第四步：猜24,15,25,35(后面三个是故意放空的)覆盖1种
结果路径YNYY: 则答案为G (四步出结果)

ＯＯＯＯＯ
＃＃＃＃Ｏ
ＯＯＯＯＯ
ＯＯＯＯＯ
ＯＯＯＯＯ


结果路径YNYN: B,b

Ｏ＃ＯＯＯ
Ｏ＃ＯＯＯ
Ｏ＃ＯＯＯ
Ｏ＃ＯＯＯ
Ｏ＃ＯＯＯ

路径YNYN第五步：猜12,15,25,35(后面三个是故意放空的)覆盖1种
结果路径YNYNY: 则答案为B (五步出结果)

Ｏ＃ＯＯＯ
Ｏ＃ＯＯＯ
Ｏ＃ＯＯＯ
Ｏ＃ＯＯＯ
ＯＯＯＯＯ

结果路径YNYNN: 则答案为b (五步出结果)

ＯＯＯＯＯ
Ｏ＃ＯＯＯ
Ｏ＃ＯＯＯ
Ｏ＃ＯＯＯ
Ｏ＃ＯＯＯ

结果路径YNN: C,c

ＯＯ＃ＯＯ
ＯＯ＃ＯＯ
ＯＯ＃ＯＯ
ＯＯ＃ＯＯ
ＯＯ＃ＯＯ

路径YNN第四步：猜13,15,25,35(后面三个是故意放空的)覆盖1种
结果路径YNNY: 则答案为C (四步出结果)

ＯＯ＃ＯＯ
ＯＯ＃ＯＯ
ＯＯ＃ＯＯ
ＯＯ＃ＯＯ
ＯＯＯＯＯ

结果路径YNNN: 则答案为c (四步出结果)

ＯＯＯＯＯ
ＯＯ＃ＯＯ
ＯＯ＃ＯＯ
ＯＯ＃ＯＯ
ＯＯ＃ＯＯ

结果路径N:

Ｏ＃＃＃＃
＃ＯＯ＃＃
＃＃＃＃＃
＃＃＃＃＃
＃＃＃＃Ｏ

路径N第二步：猜15,51,24,11 (11是故意放空的) 覆盖5种

结果路径NY: f,E,J,a,d (和路径YY拓扑等价，以下步骤略)

Ｏ＃＃＃＃
＃ＯＯ＃＃
＃ＯＯ＃＃
＃ＯＯ＃＃
＃＃＃＃Ｏ

结果路径NN: D,H,h,I,i (和路径YN拓扑等价，以下步骤略)

ＯＯＯ＃Ｏ
ＯＯＯ＃Ｏ
＃＃＃＃＃
＃＃＃＃＃
ＯＯＯ＃Ｏ

〇〇 · 发表于 2022-11-25 07:02

这解题报告可以出书

solomon_007 · 发表于 2022-11-25 16:12

〇〇发表于 2022-11-24 18:05
做了个数据结构，b是20种待猜的，t是每次猜的4个，如果返回否用not exists可以排除一部分,如果返回是，就在 ...

根据第2题，20种情况可以这样获得：

SQL>
SQL> with t as (select level n,ceil(level/5) r,mod(level-1,5)+1 c from dual connect by level <= 5*5),
  2    s(lvl,str,rpre,cpre,rlast,clast,cnt) as (select 1,cast(n as varchar2(1000)),null,null,r,c,0 from t
  3                      union all
  4                   select lvl + 1,
  5                            str||','||n,
  6                            rlast,
  7                            clast,
  8                            r,
  9                            c,
10                            s.cnt + case when r<>rpre and c<>cpre then 1 else 0 end
11                      from s,t
12                      where lvl < 4
13                      and abs(s.rlast - r) + abs(s.clast - c) = 1
14                      and t.n > (select n from t where r=s.rlast and c=s.clast)
15                      and s.cnt = 0
16                      )
17  select str from s where lvl=4 and cnt=0
18  /

STR
--------------------------------------------------------------------------------
2,3,4,5
2,7,12,17
3,8,13,18
4,9,14,19
5,10,15,20
6,7,8,9
6,11,16,21
7,8,9,10
7,12,17,22
8,13,18,23
9,14,19,24
10,15,20,25
11,12,13,14
12,13,14,15
16,17,18,19
17,18,19,20
21,22,23,24
22,23,24,25
1,2,3,4
1,6,11,16

20 rows selected

newkid · 发表于 2022-11-25 22:33

solomon_007 发表于 2022-11-25 16:12
根据第2题，20种情况可以这样获得：SQL> SQL> with t as (select level n,ceil(level/5) r,mod(level-1,5)+ ...

这部分比较无趣，有趣的在于怎么找出二分法的四个组合，你要不挑战一下？

solomon_007 · 发表于 2022-11-26 20:49

newkid 发表于 2022-11-25 22:33
这部分比较无趣，有趣的在于怎么找出二分法的四个组合，你要不挑战一下？

"怎么找出二分法的四个组合" 能解释一下吗？上面的你的解释没看明白。。

newkid · 发表于 2022-11-27 06:23

61的说明看明白了吗？
"四个组合"是指题目中说的每次猜测四个方格。总共25个方格，四个组合总有C(25,4)=12650种。比如我解题第一步选中的11,22,23,55四个方格，就是“四个组合”的一种。
每次你挑选的四个方格，应该尽量把未知的条数减少一半。比如一开始20条全是未知的，我挑选的那四个方格，可以把20条分成10+10两组，根据回答YES或者NO, 确定答案藏在其中的哪一组。
然后第二步就是再挑选四个方格，把剩下的10条划分成5+5组。这就是二分法，以此类推5次一定能找出答案。

〇〇 · 发表于 2022-11-27 09:58

从所有的4格组合中找出能筛选10个的
with b(n,s) as(values
(1,[1,2,3,4]),
(2,[2,3,4,5]),
(3,[6,7,8,9]),
(4,[7,8,9,10]),
(5,[11,12,13,14]),
(6,[12,13,14,15]),
(7,[16,17,18,19]),
(8,[17,18,19,20]),
(9,[21,22,23,24]),
(10,[22,23,24,25]),
(11,[1,6,11,16]),
(12,[6,11,16,21]),
(13,[2,7,12,17]),
(14,[7,12,17,22]),
(15,[3,8,13,18]),
(16,[8,13,18,23]),
(17,[4,9,14,19]),
(18,[9,14,19,24]),
(19,[5,10,15,20]),
(20,[10,15,20,25])
),
a as (select i from generate_series(1,25)t(i)),
t1 as(
select row_number()over()rn,[a.i,b.i,c.i,d.i]q from a,a b,a c,a d
where a.i>b.i and b.i>c.i and c.i>d.i), --select count() from t1
t as (select t1.rn,unnest(q)i from t1),
r as(
select t.rn,count(t.i)cnt from t,b where list_has(b.s,t.i)group by t.rn
)
select t1.* from r,t1 where cnt=10 and t1.rn=r.rn limit 10;
--select count(*) from r where cnt=10; --432

〇〇 · 发表于 2022-11-27 10:23

〇〇发表于 2022-11-27 09:58
从所有的4格组合中找出能筛选10个的with b(n,s) as(values(1,[1,2,3,4]),(2,[2,3,4,5]),(3,[6,7,8,9]),(4, ...

上面的逻辑有问题,改成下面的,速度很慢
with b(n,s) as(values
(1,[1,2,3,4]),
(2,[2,3,4,5]),
(3,[6,7,8,9]),
(4,[7,8,9,10]),
(5,[11,12,13,14]),
(6,[12,13,14,15]),
(7,[16,17,18,19]),
(8,[17,18,19,20]),
(9,[21,22,23,24]),
(10,[22,23,24,25]),
(11,[1,6,11,16]),
(12,[6,11,16,21]),
(13,[2,7,12,17]),
(14,[7,12,17,22]),
(15,[3,8,13,18]),
(16,[8,13,18,23]),
(17,[4,9,14,19]),
(18,[9,14,19,24]),
(19,[5,10,15,20]),
(20,[10,15,20,25])
),
a as (select i from generate_series(1,25)t(i)),
t1 as(
select row_number()over()rn,[a.i,b.i,c.i,d.i]q from a,a b,a c,a d
where a.i>b.i and b.i>c.i and c.i>d.i), --select count() from t1
t as (select t1.rn,unnest(q)i from t1),
r as(
select t.rn,count(*)cnt from b,t
where not exists(select 1 from t t2 where t.rn=t2.rn and t2.i in (select unnest(s)))group by t.rn
--select t.rn,count(t.i)cnt from t,b where list_has(b.s,t.i)group by t.rn
)
--select cnt,count(*) from r group by cnt;
--select count(*) from r where cnt=10;
select t1.* from r,t1 where cnt=40 and t1.rn=r.rn limit 10;

〇〇 · 发表于 2022-11-27 10:46

〇〇发表于 2022-11-27 09:58
从所有的4格组合中找出能筛选10个的with b(n,s) as(values(1,[1,2,3,4]),(2,[2,3,4,5]),(3,[6,7,8,9]),(4, ...

加了distinct,貌似对了
with b(n,s) as(values
(1,[1,2,3,4]),
(2,[2,3,4,5]),
(3,[6,7,8,9]),
(4,[7,8,9,10]),
(5,[11,12,13,14]),
(6,[12,13,14,15]),
(7,[16,17,18,19]),
(8,[17,18,19,20]),
(9,[21,22,23,24]),
(10,[22,23,24,25]),
(11,[1,6,11,16]),
(12,[6,11,16,21]),
(13,[2,7,12,17]),
(14,[7,12,17,22]),
(15,[3,8,13,18]),
(16,[8,13,18,23]),
(17,[4,9,14,19]),
(18,[9,14,19,24]),
(19,[5,10,15,20]),
(20,[10,15,20,25])
),
a as (select i from generate_series(1,25)t(i)),
t1 as(
select row_number()over()rn,[a.i,b.i,c.i,d.i]q from a,a b,a c,a d
where a.i>b.i and b.i>c.i and c.i>d.i), --select count() from t1
t as (select t1.rn,unnest(q)i from t1),
r as(
select t.rn,count(distinct b.n)cnt from t,b where list_has(b.s,t.i)group by t.rn
)
select t1.* from r,t1 where cnt=10 and t1.rn=r.rn limit 10;
--select cnt,count(*) from r group by cnt;

〇〇 · 发表于 2022-11-27 10:53

不清楚是否任意一个筛选10个长方形条的4格组合都能作为起点，然后下一步用y/n来分支

[每日一题] 2022 PUZZLEUP