这几年牛蛙写过的奇葩代码

udfrog · 发表于 2016-8-31 23:55

本帖最后由 udfrog 于 2016-9-1 17:24 编辑

之前自己整理过一个文档，存着自己这几年在pub上写过的有趣代码。今天又追加了几个今年写的，一并分享出来，如果有缘人喜欢，那就很好。
我这个人不是个着调的开发，从来不爱写注释，所以看着痛苦的话，抱歉了。格式也不够好。
这几年写下来，我也总在体会，我自认为我的sql写得很不同寻常，的好，最根本的原因就是我对问题建模所产生的数据结构有相当的优越性，那优秀的算法自然也就不难形成。

巧的是，论坛新开了打赏功能，我觉得挺有意思的，如果喜欢，可以尽情打赏

，让我尝个鲜。

1. Adjacent Digits

How many positive 10-digit integers are there with the property that for each digit N, the number of adjacent N's is at most N?

(Examples: 1223334444, 7777777822, 5999999999, 3434343434)

这个没去优化，在我的pc上大概要跑8分钟，也不清楚是否可以优化
with b as (
select level lv from dual connect by level<=9),
t1 (str) as (
select rpad(lv, level, lv)
from b
connect by level<=lv and prior lv=lv and prior dbms_random.value()>0
),
t as (
select * from t1 where length(str)<=5
),
r (str) as (
select  str
from t
union all
select  r.str||t.str
from t, r
where substr(r.str, -1, 1)!=substr(t.str, 1, 1)
and    length(r.str||t.str)<=5
),
r2 as (
select  str, substr(str, -1) trail, 5-nvl(length(rtrim(str, substr(str, -1))), 0) len
from r
where length(str)=5
),
r3 as (
select  str, substr(str, 1, 1) lead, 5-nvl(length(ltrim(str, substr(str, 1, 1))), 0) len
from r
where length(str)=5
)
select  56143*56143-count(*)
from r2, r3
where r2.trail=r3.lead
and    r2.len+r3.len>r2.trail;

2.Double Factored
Let''s call a number "double factored" if at least one of its prime factors repeats itself when factorised. What is the smallest positive integer that itself and its four neighbors (2 before, 1 before, the number itself, 1 after, 2 after) are double factored?
If the problem was asked for the number and its two neighbors (1 before, the number itself, 1 after) then the answer would be 49. (48=2x2x2x2x3 , 49=7x7, 50=2x5x5).

with df as (
select (rownum+1)*(rownum+1) df from dual connect by rownum<=20),
t as (
select rownum f from dual connect by rownum<=1000),
tmp as (
select  min(df*f) keep (dense_rank first order by df*f) r, row_number() over (order by df*f) rn
from  df, t
group by df*f)
select  min(a.r)-2
from  tmp a, tmp b
where a.r=b.r+4
and a.rn=b.rn+4;

3.Full Prime Number

All the numbers that can be read with two or more adjacent digits inside a prime number are also prime numbers. What is the greatest number having this property?

Exampe:6173 is such a number. Because 61, 17, 73, 617, 173 and 6173 are prime numbers

WITH t0 AS (
SELECT 2*ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM <= (100000)/2-1-1
),
t as(SELECT rn from t0
   where mod(rn,3)<>0
   and mod(rn,5)<>0
   and mod(rn,7)<>0
)
,p AS (
SELECT TO_CHAR(rn) n,LENGTH(rn) len
FROM (SELECT rn from t
      MINUS
      SELECT t1.rn * t2.rn
         FROM t t1, t t2
      WHERE t1.rn <= t2.rn
         AND t1.rn BETWEEN 11 AND SQRT(100000)
         AND t1.rn * t2.rn <100000
   )
WHERE rn>10
),
tmp (n, digit) as (
select  n, 2 digit
from  p
where len=2
union all
select  a.n||substr(b.n, -1) n, a.digit+1 digit
from  tmp a, tmp b, p
where a.digit=b.digit
and substr(a.n, 2)=substr(b.n, 1, b.digit-1)
and a.n||substr(b.n, -1)=p.n)
select max(to_number(n)) from tmp;

4.Prime Sums

All of the digits of a number are different. The sums of all neighboring three digits of this number are prime numbers. What is the largest number having these properties?

with b as (
select rownum-1 n from dual connect by rownum<=10),
p as (
select level n from dual where (level>=2 and mod(level, 2)<>0 and mod(level, 3)<>0 and mod(level, 5)<>0) or level in (2, 3, 5) connect by level<=23),
tmp as (
select    d1.n||d2.n||d3.n d
from    b d1, b d2, b d3, p
where    d1.n<>d2.n
and       d1.n<>d3.n
and       d2.n<>d3.n
and       d1.n+d2.n+d3.n=p.n),
t (d) as (
select    d
from    tmp
where    not d like '0%'
union all
select    t.d||substr(tmp.d, -1)
from    t, tmp
where    substr(t.d, -2)=substr(tmp.d, 1, 2)
and       instr(t.d, substr(tmp.d, -1))=0)
select max(to_number(d)) from t;

5.Test

35 students took a test of 100 problems.

-Each problem is solved by exactly one girl and one boy.
-There are at least one girl who solved exactly one problem, and at least one girl who solved exactly two problems.
-There are at least one boy who solved exactly four problems, and at least one boy who solved exactly five problems.
-The number of the problems solved by the girl who has solved the maximum number of problems is X.
-The number of the problems solved by the boy who has solved the maximum number of problems is Y.

If the minimum values for both X and Y are the same, find the number of girls who have taken the test.

select  n
from  (select rownum+2 n from dual connect by rownum<=35-2-2-1)
where ceil((100-9)/(35-n-2))=ceil((100-3)/(n-2));

6.Solve Problem: Complex Sequence Generation
One of the questions on the Roundtable discussion was: "On one of the forums (SQL.ru) sometimes one of the members challenge everybody by posting a task (Friday challenge) and seeking for the best solution. I remember we had something like that about year ago here as well. Can we bring that back?"
Our "Solve Problem" feature never went away - we just hadn't posted one for a while. And Faig's question spurred me to take action. So we now have up on the website the following coding challenge:
Oracle sequences generate the next integer value available in the sequence. But sometimes applications rely on keys with a more complex structure. In this challenge, a player from Islamabad asks for some help to generate an alpha-numeric value in a sequence that follows a very interesting set of rules (explained in the question). He writes:
I need to write a function with this header:
FUNCTION plch_next_key (from_this_key_in in varchar2) RETURN VARCHAR2in which the key is a 5 digit alpha-numeric sequence of values, each of which has two parts:

1. Letter part: letters from A-Z, a-z. The number of letters increase from left to right
2. Digit part: left filled with 0s to length 5, after letters.
The rightmost letter stays fixed, and the remainder (a number starting with 1) is incremented, is then left padded with 0s to length 5 (including letters), up to all 9s.
When you have all 9s and the rightmost letter is not z, then increment the rightmost letter through the sequence A-Z, a-z and the remaining digits are reset to 1 (padded left with 0s)s.
When the rightmost letter is z, but there are non-z letters to the left, the rightmost z and the other letters are incremented A-Z, a-z as needed, with the rightmost z's becoming A's and the 9s are reset to 1 (padded left with 0s).
When all letters are z and all digits are 9s, then replace each z with A, replace the first 9 with A, and the remaining digits are reset to 1 (padded left with 0s).
Here's a partial set of key ranges to illustrate these rules:
A0001...A9999B0001...B9999....Z0001...Z9999a0001...z9999AA001...AA999AB001...AB999....AZ001...AZ999Aa001...Az999BA001...BZ999Ba001...Bz999CA001...zz999AAA01...zzz99AAAA1...zzzz9AAAAA...zzzzzYour mission, if you choose to accept it, is to implement this function so that it performs efficiently and is easy to understand.

create or replace function plch_next_key(from_this_key_in in varchar2)
return varchar2
is
len int:=5;
v_digit varchar2(32);
v_char varchar2(32);
begin
v_char:=regexp_substr(from_this_key_in, '\D+');
v_digit:=regexp_substr(from_this_key_in, '\d+');
return case when replace(v_digit, '9') is not null then
v_char||lpad((v_digit+1), length(v_digit),'0')
else
substr(
regexp_substr(v_char, '(.*?)(.??)(z*)$', 1, 1, 'c', 1)||
nvl(replace(chr(ascii(regexp_substr(v_char, '(.*?)(.??)(z*)$', 1, 1, 'c', 2))+1), '[', 'a'), 'A')||
replace(regexp_substr(v_char, '(.*?)(.??)(z*)$', 1, 1, 'c', 3), 'z', 'A')||
rpad('0', length(v_digit)+nvl(sign(length(replace(v_char, 'z'))), 0)-2, '0')||'1',
1, len
)
end;
end;
/

7.Four Digits

You have a number where any digit appears at most twice. The sum of all neighboring four digits in this number is a square number.

What is the maximum possible value for this number?

Example: 205290 is such a number because no digit appears more than twice and 2+0+5+2, 0+5+2+9, and 5+2+9+0 are square numbers.

with t as (
  select to_char(level-1) l from dual connect by level<=10),
t2 as(
select
a.l||b.l||c.l||d.l v4 --??
from t a,t b,t c,t d
where a.l+b.l+c.l+d.l in(4,9,16,25)
and a.l<>0
),
r(vx,lv)as(
select cast(v4 as varchar(40)),1 from t2
union all
select vx||l,lv+1 from r,t
where
instr(vx,l,1,2)=0 --????2?,????????????
and substr(vx,-1,1)+substr(vx,-2,1)+substr(vx,-3,1)+l in(4,9,16,25)
and lv<=16)
select to_char(max(0+vx)) from r where regexp_substr(vx, '([[:digit:]])(\1){2}') is not null;

8.Ten Numbers

_
|_|_ _
|_|_|_|
|_|_|_|
|_|_|_|

Place each of the ten numbers between 1 and 10 in the squares so that no two adjacent squares (horizontally or vertically) should contain;

consecutive numbers,
numbers with the same parity (odd or even).

In how many different ways can this task be accomplished?

with t as (
select rownum n from dual connect by rownum<=8)
select count(*)*2
from t
where  level=8 and abs(connect_by_root(n)-n) in (3, 5, 7)
start with n in (2, 4, 6)
connect by nocycle abs(prior n -n) in (3, 5, 7);

9.Plastic Digits

There are four sets of plastic digits. Each set has four digits (1, 2, 3, 4) and each set has a different colour (red, blue, green, yellow). You will place these 16 digits into 4x4 table such that every two adjacent squares (vertically or horizontally) should have either the same color or the same number.>

In how many different ways can this placement be done?>

If the problem was asked for 2 digits, 2 colors and a 2x2 table, then the answer would be 8.


WITH d AS (
SELECT n,c,POWER(2,ROWNUM-1) AS id
FROM (SELECT LEVEL n FROM DUAL CONNECT BY LEVEL<=4)
   ,(SELECT 'R' c FROM DUAL UNION ALL SELECT 'B' c FROM DUAL UNION ALL SELECT 'G' c FROM DUAL UNION ALL SELECT 'Y' c FROM DUAL)
)
,t(cnt,bits,n0,c0,n1,c1,n2,c2,n3,c3) AS (
SELECT 1
   ,id
   ,null
   ,null
   ,null
   ,null
   ,null
   ,null
   ,n
   ,c
FROM d
where       rownum=1
UNION ALL
SELECT t.cnt+1
   ,t.bits+d.id
   ,nvl(t.n1, d.n)
   ,nvl(t.c1, d.c)
   ,t.n2
   ,t.c2
   ,t.n3
   ,t.c3
   ,d.n
   ,d.c
FROM t,d
WHERE cnt<16
      AND BITAND(t.bits,d.id)=0
      AND (MOD(t.cnt,4)=0 OR d.n=t.n3 OR d.c=t.c3)
      AND (t.cnt<4 OR d.n = t.n0 OR d.c = t.c0)
)
SELECT COUNT(*)*16 FROM t WHERE cnt=16;

10.Balls And Boxes

What is the number of different ways to distribute different colored ten balls into four different boxes?

-All boxes will have different number of balls.
-An empty box is allowed.

If the problem was asked for 3 balls (white, black, red) and 2 boxes, then the answer would be 8.
1. (empty) - (w,b,r), 2. (w,b,r) - (empty), 3. (w) - (b,r), 4. (b) - (w,r), 5. (r) - (b,w), 6. (b,r) - (w)
7. (w,r) - (b), 8. (b,w) - (r)

此解法刻意追求代码的趣味性，性能远非最优
with t as (
select  sign(bitand((level-1), 1))+sign(bitand((level-1), 2))+sign(bitand((level-1), 4))+sign(bitand((level-1), 8))+
  sign(bitand((level-1), 16))+sign(bitand((level-1), 32))+sign(bitand((level-1), 64))+sign(bitand((level-1), 128))+
  sign(bitand((level-1), 256))+sign(bitand((level-1), 512)) s, rownum-1 n from dual connect by level<=1024)
select  count(*)*24
from  t t1, t t2, t t3, t t4
where bitand(t1.n, t2.n)=0
and bitand(t1.n, t3.n)=0
and bitand(t1.n, t4.n)=0
and bitand(t2.n, t3.n)=0
and bitand(t2.n, t4.n)=0
and bitand(t3.n, t4.n)=0
and t1.n+t2.n+t3.n+t4.n=1023
and t1.s>t2.s
and t2.s>t3.s
and t3.s>t4.s;

11.Two Pawns

Five pieces are randomly selected from a standard chess set. If it is known that at least one of these pieces is a pawn, what is the probability that at least two of these five pieces are white pawns?

Note:In a standard chess set there are 8 pawns, 2 rooks, 2 bishops, 2 knights, 1 queen, and 1 king for each color (white and black) making a total of 32 pieces.

After simplification, enter your answer as a/b.

with t as (
select case when rownum<=8 then 0 when rownum<=16 then 1 else 2 end s, rownum n from dual connect by rownum<=32)
select  count(case when regexp_count(sys_connect_by_path(s, ','), '0')>=2 then 1 else null end)||'/'||count(*)
from  t
where level=5
connect by prior n<n and level<=5
start with s in (0, 1);

12.Digits

A number has different digits, and the digits of the sum of each neighboring two digits are not used in this number.

What is the largest number satisfying these conditions?

Example:
7692
7+6=13, 6+9=15, 9+2=11 (The digits 1, 3 and 5 are not used.)

with t as (
select to_char(rownum-1) n from dual connect by rownum<=10),
r(n, p, na) as (
select    n, n, n
from    t
union all
select    t.n, r.p||t.n, r.na||(r.p+t.n)
from    r, t
where    translate(r.p||t.n, (r.n+t.n)||'x', 'x')=r.p||t.n
and instr(r.p, t.n)=0
and instr(r.na, t.n)=0)
select    max(to_number(p)) from r;

13.       千王之王
52张牌，四张A，随机打乱后问，从左到右一张一张翻直到出现第一张A，请问平均要翻几张牌？

with b as (
select rownum n from dual connect by rownum<=51),
f (fac, n, lv) as (
select b.n, b.n, b.n from b where n>=2
union all
select    f.fac*b.n, f.n, f.lv-1
from    f, b
where    f.lv-1=b.n),
p (p, n, lv) as (
select    48, 48, 1
from    dual
union all
select    p.p*b.n, p.n-1, p.lv+1
from    p, b
where    p.n-1=b.n)
select    sum(b.n*nvl(p.p, 1)*f.fac)/sum(nvl(p.p, 1)*f.fac)
from    f, p, b
where    f.lv=1
and (52-f.n)=b.n
and b.n-1=p.lv(+)
and b.n<=49;

14.       构造最大数
给定只包含正数的数组，给出一个方法，将数组中的数拼接起来，得到的数，是最大的。

with a  as (
select 4 x from dual union all
select 94 x from dual union all
select 14 x from dual union all
select 9 x from dual union all
select 1 x from dual),
b as (
select  max(length(x)) len
from a)
select  listagg(x, '') within group (order by rpad(x, len*2, x) desc)
from a, b;

注：关于此算法rpad(x, len*2, x)的证明，在101楼
http://www.itpub.net/forum.php?mod=viewthread&tid=1804279&page=11#pid21599534

15.       编码任务
假设有一个池塘，里面有无穷多的水。现有2个空水壶，容积分别为5升和6升。如何只用这2个水壶从池塘里取得3升的水（最后，这三升水，在其中一个壶里）

with
t(n1, n2, n3, n4, lv) as (
select 5, 0, 6, 0, 1
from DUAL
union all
select decode(t.n1, 0, 5, decode(t.n2, 6, t.n1, greatest(t.n1-(6-t.n2), 0))) n1,
decode(t.n1, 0, t.n2, decode(t.n2, 6, 0, least(t.n1+t.n2, 6))) n2,
decode(t.n3, 0, 6, decode(t.n4, 5, t.n3, greatest(t.n3-(5-t.n4), 0))) n3,
decode(t.n3, 0, t.n4, decode(t.n4, 5, 0, least(t.n3+t.n4, 5))) n4,
t.lv+1
from t
where --t.lv+1 <=42
t.n1!=3
and t.n2!=3
and t.n3!=3
and t.n4!=3
)
select *
from t;

16. 三只青蛙的换位游戏
百度一个可用的链接 http://www.3366.com/flash/32099.shtml

with t as (
select round(2.5-level) pos, to_char(ceil(level/2)) c
from dual
  connect by level<=4
),
r (s, x_pos, path) as (
  select '222x111' s, 4, ''
  from dual
  union all
  select substr(replace(r.s, 'x', t.c), 1, x_pos+t.pos-1)||'x'||substr(replace(r.s, 'x', t.c), x_pos+t.pos+1), x_pos+t.pos, path||to_char(x_pos+t.pos)||'#'
  from t, r
  where substr(r.s, x_pos+t.pos, 1)=t.c
  and x_pos+t.pos between 1 and 7
)
select *
from r
where s='111x222';

17. 第三届sql大赛第一题
题目链接 http://www.itpub.net/thread-1943911-1-1.html

相当得意的一段代码
insert into TICTACTOE
with b as (
select level||'' n, decode(level, 1,111,2,1001,3,10100001,4,10010,5,111100,6,10010000,7,1100010,8,1001000,11000100) v from dual connect by level<=9
),
r(p, xp, op, i, w) as (
select n, v, 0, 0, ''
from b
union all
select p||n, decode(i, 1, v, 0)+xp, decode(i, 1, 0, v)+op, mod(i+1, 2),
case when instr(decode(i, 1, v, 0)+xp, '3')>0 then 'X' else case when instr(decode(i, 1, 0, v)+op, '3')>0 then 'O' else null end end
from r, b
where instr(r.p, n)=0
and w is null
)
select p, translate(translate('123456789', p, 'XOXOXOXOX'), '123456789', '---------'), nvl(w, 'D')
from r
where w is not null or length(p)=9;

18. 12个人带7种颜色帽子，出现不少于3个相同的概率
qingyun搞来的一个题目 http://www.itpub.net/thread-1905121-1-1.html

直接贴newkid不厌其烦帮我改两步来加速的版本
with t as (
select  power(10, level-1) n
from dual
connect by level<=7
),
t2 (comb, lv) as (
select  n, 1
from t
union all
select  t.n+t2.comb, t2.lv+1
from t, t2
where instr(t.n+t2.comb, '3')=0
and    t2.lv<=2
)
,t3 as (
select  comb, count(*) cnt
from t2
where lv=3
group by comb
)
,t4 AS (
SELECT a.comb+b.comb comb,sum(a.cnt*b.cnt) as cnt
  from t3 a,t3 b
where  translate(a.comb+b.comb, 'x012', 'x') is null
group by a.comb+b.comb
)
select  TO_CHAR(power(7, 12)-sum(a.cnt*b.cnt))
from t4 a, t4 b
where translate(a.comb+b.comb, 'x012', 'x') is null;