2022 PUZZLEUP

〇〇

newkid 发表于 2022-11-22 00:20
才两秒多，鸭子这么猛？最多能算到几位？

39位，18秒>        AND cnt<39
> )
> select max(s::hugeint)::varchar from t;
┌──────────────────────────────────────────┐
│ CAST(max(CAST(s AS HUGEINT)) AS VARCHAR) │
│                 varchar                  │
├──────────────────────────────────────────┤
│ 122212112221121222121122211122121122212  │
└──────────────────────────────────────────┘
Run Time (s): real 18.571 user 26.520170 sys 0.967206
49位，bigint溢出了
不用类型转换
with recursive t (s,cnt)
as (
select * from (values('1',1),('2',2))
union all
select t.s||n,t.cnt+1
  from t,(select n from (values(1),(2))t(n))
where cnt<3
       or not exists
          (select 1
           from generate_series(1,100)x(level)
           where level<=t.cnt-2 and instr(substr(t.s,greatest(-level-1-level-2,-cnt)),substr(t.s,-level-1)||n)>0
           )
       AND cnt<49
)
select max(length(s)) from t;
┌────────────────┐
│ max(length(s)) │
│     int64      │
├────────────────┤
│             49 │
└────────────────┘
Run Time (s): real 62.255 user 510.731674 sys 11.044871
59跑了一小时>        AND cnt<59
> )
> select max(length(s)) from t;
┌────────────────┐
│ max(length(s)) │
│     int64      │
├────────────────┤
│             59 │
└────────────────┘
Run Time (s): real 2999.401 user 11756.219760 sys 239.742337

〇〇

是我翻译错了？应该是低版本的bugv0.4.0 da9ee490d
Use ".open FILENAME" to reopen on a persistent database.
D .timer on
D with recursive t (s,cnt)
> as (
> select * from (values('1',1),('2',2))
> union all
> select t.s||n,t.cnt+1
> from t,(select n from (values(1),(2))t(n))
> where cnt<3
> or not exists
> (select 1
> from generate_series(1,50)x(level)
> t-2 and instr(substr(t.s,greatest(-level-1-level-2,-cnt)),substr(t.s,-level-1)||n)>0
> )
> AND cnt<45
> )
> select s from t where length(s)=21 limit 10 ;
┌───────────────────────┐
│           s           │
├───────────────────────┤
│ 111111111111111111111 │
│ 211111111111111111111 │
│ 121111111111111111111 │
│ 221111111111111111111 │
│ 112111111111111111111 │
│ 212111111111111111111 │
│ 122111111111111111111 │
│ 222111111111111111111 │
│ 111211111111111111111 │
│ 211211111111111111111 │
└───────────────────────┘
Run Time: real 11.773 user 22.410743 sys 1.821752


v 0.6.0 又快又没错
> select s from t where length(s)=21 limit 10 ;
┌───────────────────────┐
│           s           │
│        varchar        │
├───────────────────────┤
│ 221211121221112212111 │
│ 122211121221112212111 │
│ 111221121221112212111 │
│ 112221121221112212111 │
│ 212221121221112212111 │
│ 112212112221112212111 │
│ 122212112221112212111 │
│ 112122112221112212111 │
│ 212111212221112212111 │
│ 122111212221112212111 │
├───────────────────────┤
│        10 rows        │
└───────────────────────┘
Run Time (s): real 0.248 user 0.140401 sys 0.031200二者的执行计划
040_exp.txt (18.93 KB, 下载次数: 4)

2022-11-22 16:56 上传

点击文件名下载附件

060_exp.txt (20.37 KB, 下载次数: 5)

2022-11-22 16:56 上传

点击文件名下载附件

〇〇

Oracle 最后一步写select s from t where length(s)=21 fetch first 10 ;会不会快？

〇〇

第6题
GUESSING GAME

GUESSING GAME

You and your friend are playing a guessing game. Your friend chooses four adjacent squares (all vertically or all horizontally) of a 5x5 chessboard. You will try to find these squares. At each step, you will tell your friend any four squares, and he will answer "yes" if at least one of the squares matches, otherwise "no".

No matter what squares your friend chooses, what is the minimum number of steps required to be sure to find these four squares?
百度翻译
猜谜游戏

猜谜游戏

你和你的朋友在玩猜谜游戏。你的朋友在5x5棋盘上选择四个相邻的方格（全部垂直或全部水平）。你将尝试找到这些正方形。在每一步，你都会告诉你的朋友任何四个方块，如果至少有一个方块匹配，他会回答“是”，否则回答“否”。

无论你的朋友选择哪一个方格，确保找到这四个方格所需的最少步数是多少？

〇〇

如果是3x3的棋盘猜1x2方格，最多3次，先猜2和4，如果不是，排除后只剩下689，再猜2次

newkid

要找出一个方法不难，但是要证明是最少次数就很不容易。

newkid

5步能凑出来，这也是理论上最少的，因为总共20种，用二分法，2^4=16, 所以4次是不行的。

〇〇

如果要实现二分法，每次要尽量均匀地把格子分开

〇〇

做了个数据结构，b是20种待猜的，t是每次猜的4个，如果返回否用not exists可以排除一部分,如果返回是，就在剩下的中再换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])
),
t(x) as (values([1,6,7,8])),
t1 as (select unnest(x)i from t)
select * from b where not exists(select 1 from t1 where i in (select unnest(s)));

n   s
--  ----------------
2   [2, 3, 4, 5]
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]
17  [4, 9, 14, 19]
18  [9, 14, 19, 24]
19  [5, 10, 15, 20]
20  [10, 15, 20, 25]

newkid

写程序的价值本来是要帮你找出一种猜测的策略，现在你这个[1,6,7,8]是手工定的，而且也没法给出下一步要猜什么，所以没什么意义。

20条可以用20 bit表示，所有猜测有C(25,4)=12650种可以事先算出被哪几个比特覆盖。
每次猜测就是用bitand叠加，使得1的个数是原先的一半。如果实时计算一个二进制数有几个1也比较费劲，所以也得事先算好存起来，总共才2^20个。

我昨天本来是想写一个程序，没想到答案很容易用肉眼就找到了，所以就没动手。

我随便挑了个11,22,23,55作为起点，刚好覆盖了10条，剩下的步骤就很顺利了，每步都很容易地一分为二。