sql算24点大赛

〇〇

24d4my.txt (8.45 KB, 下载次数: 0)

2023-12-26 16:30 上传

点击文件名下载附件

改写成mysql,思路也能用在oracle

newkid

评选结果在哪里看？

〇〇

把7楼引用的grubbyoo SQL改写成函数，较慢
```
create table w as
with  d
as(select level n from dual connect by level<=10),
data
as(select rownum id, a.n||','||b.n||','||c.n||','||d.n s from d a,d b,d c,d where a.n<=b.n and b.n<=c.n and c.n<=d.n)
select * from data;


\set SQLTERM /

create or replace function get24(csv varchar) return varchar
as
ret varchar;
begin
with test as (select rownum id, regexp_substr(csv, '[^,]+',1,rownum) n from dual connect by rownum < 5)
select  case when     end_out1=24  then '('||'('||n1||f1||n2||')'||f2||n3||')'||f3||n4||'='||'24'
             when     end_out2=24  then '('||n1||f1||n2||')'||f3||'('||n3||f2||n4||')'||'='||'24'
             when     end_out3=24  then n1||f3||'('||'('||n2||f1||n3||')'||f2||n4||')'||'='||'24'
             when    round(end_out4)=24  then n1||f3||'('||n2||f2||'('||n3||f1||n4||')'||')'||'='||'24'
             end  
                     
from
     ( select x2.*,d.n n4,f3,
             decode(f3, '+', c123 + d.n, '-', c123 - d.n, '*', c123 * d.n, '/', c123 / d.n) end_out1,
             decode(f3, '+', c12 + decode(f2, '*', n3 * d.n, '/', n3 / d.n),
                        '-', c12 - decode(f2, '*', n3 * d.n, '/', n3 / d.n),
                        '*', c12 * decode(f2, '+', n3 + d.n, '-', n3 - d.n),
                        '/', c12 / decode(f2, '+', n3 + d.n, '-', decode(n3,d.n,null,n3-d.n), '/', n3 / d.n) )             end_out2,
             decode(f3, '-', n1 - decode(f2, '+', c23 + d.n, '-', c23 - d.n, '*', c23 * d.n, '/', c23 / d.n),
                        '/', n1 / decode(f2, '+', decode(c23,-1*d.n,null,c23+d.n),
                                             '-', decode(c23,d.n,null,c23-d.n),
                                             '*', decode(c23,0,null,c23 * d.n),
                                             '/', decode(c23,0,null,c23 / d.n) ))                                             end_out3,
             decode(f3, '/', n1 / decode(f2, '/', n2 / decode(f1,'+',n3 + d.n,'-',decode(n3,d.n,null,n3- d.n),'*', n3 * d.n,'/', n3 / d.n),
                                             '-', decode(n2,decode(f1,'+',n3 + d.n,'-', decode(n3,d.n,null,n3- d.n),'*', n3 * d.n,'/', n3 / d.n) ,
                                                            null,n2-decode(f1,'+',n3 + d.n,
                                                                              '-',decode(n3,d.n,null,n3- d.n),
                                                                              '*', n3 * d.n,
                                                                              '/', n3 / d.n) ),
                        '-', n1 - decode(f2, '/', n2 / decode(f1,'+',n3 + d.n, '-', decode(n3,d.n,null,n3- d.n), '*', n3 * d.n, '/', n3 / d.n),
                                             '-', n2 - decode(f1,'+',n3 + d.n, '-', decode(n3,d.n,null,n3- d.n), '*', n3 * d.n, '/', n3 / d.n)) )) end_out4
                        
                                          
      from (select id1,id2,c.id id3,
                   x1.n1,x1.n2,c.n n3,
                   f1,f2,x1.c12,
                   decode(f2, '+', c12+ c.n, '-', c12 - c.n, '*', c12 * c.n, '/', c12 / c.n) c123,
                   decode(f1, '+', n2+ c.n,'-', n2- c.n, '*', n2* c.n, '/', n2 / c.n) c23
            from (select a.id id1,b.id id2,
                         a.n  n1, b.n n2,
                         f1,
                         decode(f1, '+', a.n + b.n, '-', a.n - b.n, '*', a.n * b.n, '/', a.n / b.n) c12
                    from test a,
                         test b,
                         (select substr('+-*/', rownum, 1) f1  from dual connect by rownum < 5) x
                   where a.id <> b.id)            x1,
                 test c,
                 (select substr('+-*/', rownum, 1) f2 from dual connect by rownum < 5) x
            where x1.id1 <> c.id
             and x1.id2 <> c.id)x2,
            test d,
            (select substr('+-*/', rownum, 1) f3 from dual connect by rownum < 5) x
       where id1<>d.id and   id2<>d.id  and   id3<>d.id ) x3
where (end_out1=24
    or end_out2=24
    or end_out3=24
    or round(end_out4)=24) and rownum=1 into ret;
return ret;
EXCEPTION
when ZERO_DIVIDE then
return csv|| 'zero';
WHEN OTHERS THEN
return csv||' err';
end;
/


\set SQLTERM ;
```
select get24(s) from w;

〇〇

[ 本帖最后由 〇〇 于 2023-12-28 08:34 编辑 ]\n\n[ 本帖最后由 〇〇 于 2023-12-28 08:29 编辑 ]\n\n 24.cpp.txt (2.1 KB, 下载次数: 4)

2023-12-28 08:33 上传

点击文件名下载附件

这个递归函数比较快，还能扩展到其它个数算其他数值，不知能否改成SQL
[url]https://www.jb51.net/article/172480.htm[/url]
#include<iostream>#include<cmath>//#includeusing namespace std;const double PRECISION = 1E-6;const int COUNT_OF_NUMBER = 4;const int NUMBER_TO_BE_CAL = 24;double number[COUNT_OF_NUMBER];string expression[COUNT_OF_NUMBER];bool Search(int n){if (n == 1) {if ( fabs(number[0] - NUMBER_TO_BE_CAL) < PRECISION ) {cout << expression[0] << endl;return true;} else {return false;}}for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {double a, b;string expa, expb;a = number[i];b = number[j];number[j] = number[n - 1];expa = expression[i];expb = expression[j];expression[j] = expression[n - 1];expression[i] = '(' + expa + '+' + expb + ')';number[i] = a + b;if ( Search(n - 1) ) return true;expression[i] = '(' + expa + '-' + expb + ')';number[i] = a - b;if ( Search(n - 1) ) return true;expression[i] = '(' + expb + '-' + expa + ')';number[i] = b - a;if ( Search(n - 1) ) return true;expression[i] = '(' + expa + '*' + expb + ')';number[i] = a * b;if ( Search(n - 1) ) return true;if (b != 0) {expression[i] = '(' + expa + '/' + expb + ')';number[i] = a / b;if ( Search(n - 1) ) return true;}if (a != 0) {expression[i] = '(' + expb + '/' + expa + ')';number[i] = b / a;if ( Search(n - 1) ) return true;}number[i] = a;number[j] = b;expression[i] = expa;expression[j] = expb;}}return false;}int main(){char buffer0[20];char buffer1[20];char buffer2[20];char buffer3[20];
for (int a= 1; a<=10; a++)for (int b= a; b<=10; b++)for (int c= b; c<=10; c++)for (int d= c; d<=10; d++){        number[0] = a;itoa(a, buffer0, 10);expression[0] = buffer0;number[1] = b;itoa(b, buffer1, 10);expression[1] = buffer1;number[2] = c;itoa(c, buffer2, 10);expression[2] = buffer2;number[3] = d;itoa(d, buffer3, 10);expression[3] = buffer3;Search(COUNT_OF_NUMBER);}/*for (int i = 0; i < COUNT_OF_NUMBER; i++) {char buffer[20];int x;cin >> x;number[i] = x;itoa(x, buffer, 10);expression[i] = buffer;}
if ( Search(COUNT_OF_NUMBER) ) {cout << "Success." << endl;} else {cout << "Fail." << endl;}*/}

newkid

递归的思路很简单，十几年前的老帖里面就有了。不论多少张牌，最后的结果来自两个操作数，每个又可以继续拆解。

〇〇

poke24Sql.txt (4.58 KB, 下载次数: 0)

2023-12-28 13:04 上传

点击文件名下载附件

poke24Sql_4 (1).txt (4.07 KB, 下载次数: 0)

2023-12-28 13:04 上传

点击文件名下载附件

基于其他人的生成算法代码修改的mysql版本

〇〇

结果 https://mp.weixin.qq.com/s/mnwUh7yTkt3dz8YJZdWJ5A

newkid

恭喜本版版主获得第三第四名！文章里面没有选手的SQL，只有思路介绍？
这次题目取值只限1-10，所以答案很有限，测试却有百万数据，里面大量都是重复的。有些人把所有答案先求出来再查表，不知道出题者原意是否如此。第一名把1-10映射质因子再求乘积的思路很新颖。我想的办法是 10^N1+10^N2+10^N3+10^N4

〇〇

昨天在微信群里见到这个代码，反着推，好像效率挺高
WITH RECURSIVE tmp_num ( n) AS (
  SELECT 1
  UNION ALL
  SELECT n +1
  FROM tmp_num
  WHERE n < 10),
tmp_100 (n) as (
  SELECT 1
  UNION ALL
  SELECT n +1
  FROM tmp_100
  WHERE n < 100),
tmp_cards as (
select a.*,pow(10,a.c1)+pow(10,a.c2)+pow(10,a.c3)+pow(10,a.c4) id1
from cards a
) ,
tmp_cards1 as (
  select pow(10,a.n)+pow(10,b.n)+pow(10,c.n)+pow(10,d.n) id,
  a.n c1,b.n c2,c.n c3,d.n c4
  from tmp_num a ,tmp_num b ,tmp_num c ,tmp_num d
  order by pow(10,a.n)+pow(10,b.n)+pow(10,c.n)+pow(10,d.n)
) ,
tmp_calc (n,r,op) as (
  select n,24-n,'+' from tmp_100
  union all
  select n,24+n,'-' from tmp_100
  union all
  select n,24*n,'/' from tmp_100
  union all
  select n,24/n,'*' from tmp_100
  union all
  select n,n/24,'%' from tmp_100
),
tmp_ab(x,y,n,op,s) as (
  select a.n c,b.n d,a.n+b.n n,'+' op,CONCAT('(',a.n,'+',b.n,')') s
  from tmp_100 a ,tmp_100 b
  union all
  select a.n c,b.n d,a.n-b.n n,'-' op,CONCAT('(',a.n,'-',b.n,')') s
  from tmp_100 a ,tmp_100 b
  union all
  select a.n c,b.n d,a.n*b.n n,'*' op,CONCAT('(',a.n,'*',b.n,')') s
  from tmp_100 a ,tmp_100 b
  union all
  select a.n c,b.n d,a.n/b.n n,'/' op,CONCAT('(',a.n,'/',b.n,')') s
  from tmp_100 a ,tmp_100 b
  ),
tmp_fraction  (x,y,z,n,s) as
  (select a.n,b.n,c.n,c.n-a.n/b.n,
    CONCAT('(',c.n,'-(',a.n,'/',b.n,'))')
    from tmp_num a ,tmp_num b,tmp_num c
    where a.n/b.n REGEXP '^[0-9]*\.[0-9]*$' = 1
    union all
    select a.n,b.n,c.n,c.n+a.n/b.n,
    CONCAT('(',c.n,'+(',a.n,'/',b.n,'))')
    from tmp_num a ,tmp_num b,tmp_num c
    where a.n/b.n REGEXP '^[0-9]*\.[0-9]*$' = 1),
tmp_ab_cd(id,s) as (
   select pow(10,b.x)+ pow(10,b.y)+ pow(10,c.x)+ pow(10,c.y),
    case a.op when '%' then CONCAT(c.s,'/',b.s) else CONCAT(b.s,a.op,c.s) end  
    from tmp_calc a
    left join tmp_ab b on b.n = a.r
    left join tmp_ab c on c.n = a.n
    where b.x<11 and b.y<11 and c.x<11 and c.y <11
),
tmp_abc_d(id,s) as (
  select pow(10,c.x)+ pow(10,c.y)+ pow(10,b.y)+ pow(10,a.n),
     case a.op when '%' then CONCAT(a.n,'/',CONCAT('(',c.s,b.op,b.y,')')) else CONCAT(CONCAT('(',c.s,b.op,b.y,')'),a.op,a.n) end s
    from tmp_calc a
    left join tmp_ab b on a.r = b.n
    left join tmp_ab c on c.n = b.x
    where b.y<11 and c.x<11 and c.y <11 and a.n<11
),
tmp_fr1 as (
    select pow(10,b.x)+ pow(10,b.y)+ pow(10,b.z)+ pow(10,a.n),
      case a.op when '%' then  CONCAT(a.n,'/',b.s) else CONCAT(a.n,a.op,b.s) end
    from tmp_calc a ,tmp_fraction b
    where  a.r=b.n and a.n <11
),
tmp_abcd (id,s) as (
  select id,s from (
    select * from tmp_ab_cd
    union all
    select * from tmp_abc_d
    union all
    select * from tmp_fr1) a
  group by id
  order by id
    )
select a.id,a.c1,a.c2,a.c3,a.c4,b.s result from tmp_cards a
left join tmp_abcd b on a.id1 = b.id
解释
常规思路一般几种方式：
方式1：列出所有算法进行计算；
方式2：逐步分解括弧，按优先级逐步计算，得到最终结果=24的公式；
方式3：预先算好所有公式，然后按4个数字的组合ID进行检索
方式1和方式2我都尝试过，也写成功，其中方式2最快优化到2000条记录370ms左右（V3版本）
方式3虽然速度很快，虽然规则允许，但我认为有投机取巧的嫌疑
本方法通过避免大量四则运算，将24点算法转换成可以通过查找参数表的
方式直接检索出表达式，速度相比V3提升一倍多（V3 370ms，V4
120ms)
一、总体思路

尽量降低四则运算次数，使用三个参数表来组合各种24点算法
优点:
1、扩充性强，比如不是计算24点，是计算28点、35点，修改参数表24数字为相应数值即可，再比
如，目前是1-10，如果计算1-13，修改另一个参数表100为169(13*13)，数字列表10修改成13即可。唯
一麻烦点的扩充是选4个数变成5个6个等情况的时候，需要调整的略多，但也是可以调整出来的。
2、不用考虑浮点运算，一般情况下都需要在24左右测算一个数字，再进行between，该方法不需要这
样判断。
tmp_num: 1-10数字序列
tmp_100 : 1-100数字序列
tmp_cards: 为cards表加上一个组合ID，用pow(10,c1)+pow(10,c2)+pow(10,c3)+pow(10,c4)计算
二、准备
tmp_num ( n) AS (
1
SELECT 1
2
UNION ALL
3
SELECT n +1
4
FROM tmp_num
5
WHERE n < 10
6
tmp_100 (n) as (
1
SELECT 1
2
UNION ALL
3
SELECT n +1
4
FROM tmp_100
5
WHERE n < 100)
6
tmp_cards as (
1
select pow(10,c1)+pow(10,c2)+pow(10,c3)+pow(10,c4) id1 , a.* from cards a)
2
三、参数表

tmp_calc:一个整数和24四折运算关系，结果保存为r，需要考虑n/24，计算符合用%代表,记录数
4000
因为是1-10计算，需要计算到100,，如果调整成13个数，则100要调整成169（13*13）
tmp_ab 1-100所有数字，任意两个数四折运算的结果表,合计100*4*100=40000条记录。
x、y：参与运算的两个数
n：两个数的计算结果
op：操作符
s：计算表达式
tmp_calc (n,r,op) as (
1
select n,24-n,'+' from tmp_100
2
union all
3
select n,24+n,'-' from tmp_100
4
union all
5
select n,24*n,'/' from tmp_100
6
union all
7
select n,24/n,'*' from tmp_100
8
union all
9
select n,n/24,'%' from tmp_100
10
)
11
tmp_ab(x,y,n,op,s) as (
1
select a.n c,b.n d,a.n+b.n n,'+' op,CONCAT('(',a.n,'+',b.n,')') s
2
from tmp_100 a ,tmp_100 b
3
union all
4
select a.n c,b.n d,a.n-b.n n,'-' op,CONCAT('(',a.n,'-',b.n,')') s
5
from tmp_100 a ,tmp_100 b
6
union all
7
select a.n c,b.n d,a.n*b.n n,'*' op,CONCAT('(',a.n,'*',b.n,')') s
8
from tmp_100 a ,tmp_100 b
9
union all
10
select a.n c,b.n d,a.n/b.n n,'/' op,CONCAT('(',a.n,'/',b.n,')') s
11
from tmp_100 a ,tmp_100 b
12
)
13

tmp_fraction：三个数计算结果是小数的情况，在计算1555，3388等组合的时候需要，合计记录
数2000条。
ps：该形态没有考虑乘除以及（a+b)-c，经过测试，已经能解决问题了，所以就不添加SQL语
句了。
三个参数表合计记录数46000，也就是4.6万次四折运算，已经大幅度降低了计算次数
按括弧可分为两类 (A op B) op (C op D) 简称AB_CD ((A op B) op C) op D 简称 ABC_D 其中ABC
形态有AB_C和C_AB ABC_D形态有ABC_D和D_ABC
合计5种形态
经过测试所有计算公式均可通过这三个参数表组合检索得到，实际上只需要检索
AB_CD、ABC_D和小数形态
所有形态计算结果查找都是从TMP_CALC出发，然后left join 相关中间表进行检索，使用
TMP_CALC的形态是至少有一个整数。ABC_D和小数形态，都是符合条件的，麻烦点的是AB_CD形
态。
AB_CD形态【(A op1 B) op2 （C op3 B）】，两个部分AB和CD，两个整数运算出现小数的**
可能性是除法，最大值是9/2=4.5
op2为加减时，op1和op3不能同时为加减，否则可以转换成ABC_D形态
op2为乘除时，op1和op3不能同时为乘除，否则也可以转换成ABC_D形态
剔除以上两种组合后，有两种可能性
tmp_fraction (x,y,z,n,s) as
1
(select a.n,b.n,c.n,c.n-a.n/b.n,
2
CONCAT('(',c.n,'-(',a.n,'/',b.n,'))')
3
from tmp_num a ,tmp_num b,tmp_num c
4
where a.n/b.n REGEXP '^[0-9]*\.[0-9]*$' = 1
5
union all
6
select a.n,b.n,c.n,c.n+a.n/b.n,
7
CONCAT('(',c.n,'+(',a.n,'/',b.n,'))')
8
from tmp_num a ,tmp_num b,tmp_num c
9
where a.n/b.n REGEXP '^[0-9]*\.[0-9]*$' = 1)
10
四、计算形态
五、计算过程
前提说明：

op2为乘除，则op1、op2,至少有一个是加减，两个整数加减，可以使用TMP_CALC
op2为加减，op1、op3有可能同时出现小数，但小数最大是4.5，两个4.5加减不可能
>=24，所以可以使用TMP_CALC
AB_CD形态
tmp_calc关联两个tmp_ab表，一个关联整数，另一个关联计算24点需要的数，同时参与运算
tmp_ab的数都在1-10范围内。
ABC_D形态
A表和B表关联；把ABC当做一个整体，其结果必然在tmp_calc的r列范围内
B表和C表关联：也就是ABC计算，把AB当做一个整体，其结果在AB表的计算结果内
同时参与运算的四个数在1-10范围内
小数形态
补充完善ABC_D和AB_CD形态不能计算的一些公式
tmp_ab_cd(id,s) as (
1
select pow(10,b.x)+ pow(10,b.y)+ pow(10,c.x)+ pow(10,c.y),
2
case a.op when '%' then CONCAT(c.s,a.op,b.s) else CONCAT(b.s,a.op,c.s) end
3
from tmp_calc a
4
left join tmp_ab b on b.n = a.r
5
left join tmp_ab c on c.n = a.n
6
where b.x<11 and b.y<11 and c.x<11 and c.y <11
7
)
8
tmp_abc_d(id,s) as (
1
select pow(10,c.x)+ pow(10,c.y)+ pow(10,b.y)+ pow(10,a.n),
2
case a.op when '%' then CONCAT(a.n,'/',CONCAT('(',c.s,b.op,b.y,')')) else
CONCAT(CONCAT('(',c.s,b.op,b.y,')'),a.op,a.n) end s
3
from tmp_calc a
4
left join tmp_ab b on a.r = b.n
5
left join tmp_ab c on c.n = b.x
6
where b.y<11 and c.x<11 and c.y <11 and a.n<11
7
),
8
tmp_fr1 as (
1
select pow(10,b.x)+ pow(10,b.y)+ pow(10,b.z)+ pow(10,a.n),
2

三个结合组合
通过group by 缩减结果范围，可以让最后的left join效率进一步提高
统计数据，结果为566个公式
最终检索
case a.op when '%' then CONCAT(a.n,'/',b.s) else CONCAT(a.n,a.op,b.s) end
3
from tmp_calc a ,tmp_fraction b
4
where a.r=b.n and a.n <11
5
),
6
tmp_abcd (id,s) as (
1
select id,s from (
2
select * from tmp_ab_cd
3
union all
4
select * from tmp_abc_d
5
union all
6
select * from tmp_fr1) a
7
group by id
8
)
9
select count(1) from tmp_abcd
1
select a.id,a.c1,a.c2,a.c3,a.c4, b.s "result"
2
from tmp_cards a
3
left join tmp_abcd b on b.id =a.id1
4

newkid

〇〇 发表于 2024-1-11 08:14
昨天在微信群里见到这个代码，反着推，好像效率挺高WITH RECURSIVE tmp_num ( n) AS (  SELECT 1  UNION AL ...

他说方法三“投机取巧”，其实他自己也是用的先凑出来再查表的方法。如果我是出题方，应该输入四个绑定变量，然后循环调用SQL来测试，而不是把大量重复的几百万个测试用例放在表里。
他用的POWER(10)的方法和我说的一样，因为二进制有进位的问题。