2022 PUZZLEUP

solomon_007 · 发表于 2022-11-20 17:25

#5

SQL>
SQL>  with t(c) as (select 1 from dual union all select 2 from dual),
  2       r(n,str) as (select 3,x.c||y.c||z.c from t x,t y,t z
  3                   union all
  4                   select n + 1,
  5                         str||t.c
  6                   from r,t,lateral (select count(distinct substr(str||t.c,b,a)) uni_cnt,count(*) cnt
  7                                        from (select level b from dual connect by level <= r.n + 1) s,
  8                                              (select 3 + level - 1 a from dual connect by level <= r.n + 1 - 3) L
  9                                        where length(substr(str||t.c,b,a)) = a
10                                     ) s
11                   where n < 10
12                      and s.uni_cnt = s.cnt
13                   )
14  select length(max(to_number(str))) from r
15  /

LENGTH(MAX(TO_NUMBER(STR)))
---------------------------
                     10

solomon_007 · 发表于 2022-11-20 17:30

这应该属于修改之前的：

SQL>
SQL>  with t(c) as (select 1 from dual union all select 2 from dual),
  2       r(n,str) as (select 3,x.c||y.c||z.c from t x,t y,t z
  3                   union all
  4                   select n + 1,
  5                         str||t.c
  6                   from r,t,lateral (select count(distinct substr(str||t.c,b,a)) uni_cnt,count(*) cnt
  7                                        from (select level b from dual connect by level <= r.n + 1) s,
  8                                              (select 3 + level - 1 a from dual connect by level <= r.n + 1 - 3) L
  9                                        where length(substr(str||t.c,b,a)) = a
10                                     ) s
11                   where n < 20
12                      and s.uni_cnt = s.cnt
13                   )
14  select max(n) from r
15  /

MAX(N)
----------
      10

〇〇 · 发表于 2022-11-20 18:36

solomon_007 发表于 2022-11-20 17:30
这应该属于修改之前的： SQL> SQL> with t(c) as (select 1 from dual union all select 2 from dual), 2 ...

lateral join,oracle真先进,duckdb刚有

solomon_007 · 发表于 2022-11-20 21:40

〇〇发表于 2022-11-20 18:36
lateral join,oracle真先进,duckdb刚有

Oracle 也是 12.1C 才支持。 S 子查询引用左边r,t的字段报错了，才想到这个写法。

newkid · 发表于 2022-11-21 00:11

第一种翻译的写法：
with t (s,cnt)
as (
select cast(level as varchar2(40)),1 from dual connect by level<=2
union all
select t.s||n,t.cnt+1
  from t,(select level n from dual connect by level<=2)
where cnt<3
   or instr(t.s,substr(t.s,-2)||n)=0
)
select max(to_number(s)) from t;

MAX(TO_NUMBER(S))
-----------------
   2221211122

第二种，不知道何时见底，强加了个30位的限制，22秒才跑出来：

with t (s,cnt)
as (
select cast(level as varchar2(100)),1 from dual connect by level<=2
union all
select t.s||n,t.cnt+1
  from t,(select level n from dual connect by level<=2)
where cnt<3
   or not exists
      (select 1
         from dual
         where instr(substr(t.s,greatest(-level-1-level-2,-cnt)),substr(t.s,-level-1)||n)>0
         connect by level<=t.cnt-2
         )
   AND cnt<30
)
select to_char(max(to_number(s))) from t;

TO_CHAR(MAX(TO_NUMBER(S)))
-------------------------------------
222121122211212221211222111222

newkid · 发表于 2022-11-21 00:14

lateral view在12C之前也可以实现，但是要定义一个OBJECT TYPE, 然后用TABLE()写一个子查询。
我一支以为lateral view是增强的标量子查询，可以返回多行多列，后来才直到它不具备标量子查询的行间数据缓存，即使子查询的驱动条件没有变，还是会重新执行，希望未来的版本能够改善。

〇〇 · 发表于 2022-11-21 12:52

本帖最后由〇〇于 2022-11-21 12:59 编辑

newkid 发表于 2022-11-21 00:11
第一种翻译的写法：with t (s,cnt)as (select cast(level as varchar2(40)),1 from dual connect by level

30不是底,sqlite 3.40
.timer on
with recursive t1 as(select '1' n union all select '2'),
t3 as(select t1.n||t1a.n||t1b.n s from t1,t1 t1a,t1 t1b),
t as(select 1 lv, t3.s from t3
union all
select lv+1, t.s||t1.n str from t,t1 where not exists(select 1 from --t3 a,
(select value c from generate_series(1,30))c,
(select value d from generate_series(1,30))d
where --求一个字符串s所有长度>=3的子串
length(substr(s,c,d))>=3
and c<=length(s)
and c+d<=length(s)+1
--从子串的下一位开始比较
and instr(substr(t.s||t1.n,c+1),substr(s,c,d)) between 1 and length(substr(s,c,d))
)and lv<=30)
select max(length(s)) from t;
33
Run Time : real 229.472 user 229.321470 sys 0.000000

--duckdb 0.6.0
with recursive t1 as(select n from (values('1'),('2'))t(n)),
t3 as(select t1.n||t1a.n||t1b.n s from t1,t1 t1a,t1 t1b),
t as(select 1 lv, t3.s from t3
union all
select lv+1, t.s||t1.n str from t,t1 where not exists(select 1 from --t3 a,
(select c from generate_series(1,30)c(c)),
(select d from generate_series(1,30)d(d))
where --求一个字符串s所有长度>=3的子串
length(substr(s,c,d))>=3
and c<=length(s)
and c+d<=length(s)+1
--从子串的下一位开始比较
and instr(substr(t.s||t1.n,c+1),substr(s,c,d)) between 1 and length(substr(s,c,d))
)and lv<=30)
select s from t where length(s)=33;

┌───────────────────────────────────┐
│                s                │
│             varchar             │
├───────────────────────────────────┤
│ 221211221112221211122121122111211 │
│ 211121221112221211122121122111211 │
│ 221121221112221211122121122111211 │
│ 111212221112221211122121122111211 │
│ 211212221112221211122121122111211 │
│ 121112212112221211122121122111211 │
│ 221112212112221211122121122111211 │
│ 222112212112221211122121122111211 │
│ 121112122112221211122121122111211 │
│ 221112122112221211122121122111211 │
│                ·                │
│                ·                │
│                ·                │
│ 221121222111221121222121122211212 │
│ 211122121112221121222121122211212 │
│ 121122121112221121222121122211212 │
│ 221122121112221121222121122211212 │
│ 111222121112221121222121122211212 │
│ 211222121112221121222121122211212 │
│ 121222121112221121222121122211212 │
│ 221211221112221121222121122211212 │
│ 211121221112221121222121122211212 │
│ 221121221112221121222121122211212 │
├───────────────────────────────────┤
│    50568 rows (20 shown)    │
└───────────────────────────────────┘
Run Time (s): real 42.219 user 50.263522 sys 0.296402

〇〇 · 发表于 2022-11-21 13:09

newkid 发表于 2022-11-21 00:11
第一种翻译的写法：with t (s,cnt)as (select cast(level as varchar2(40)),1 from dual connect by level

把你的改写成duckdb语法
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<30
)
select max(s::hugeint)::varchar from t;
┌──────────────────────────────────────────┐
│ CAST(max(CAST(s AS HUGEINT)) AS VARCHAR) │
│                varchar                │
├──────────────────────────────────────────┤
│ 122212112221121222121122211122          │
└──────────────────────────────────────────┘
Run Time (s): real 2.308 user 3.354021 sys 0.000000

solomon_007 · 发表于 2022-11-21 13:56

〇〇发表于 2022-11-17 09:36
连续4个的序列重复必然导致连续3个的序列重复，只要保证3个就行了？

对啊，先还没注意到你这个句话，看了你们的才知道，你们只判断了3位，我是老老实实把整个字符串分解出所有可能，除了自身。

newkid · 发表于 2022-11-22 00:20

〇〇发表于 2022-11-21 13:09
把你的改写成duckdb语法with recursive t (s,cnt)as (select * from (values('1',1),('2',2))union allsele ...

才两秒多，鸭子这么猛？最多能算到几位？

[每日一题] 2022 PUZZLEUP