概述
最近,组织了一个24点SQL编程的比赛,笔者是主办方,也是评委。既然是做评委,自己也先挑战了一下,因为对MySQL更为熟悉,故选择了MySQL作为编程SQL。周末花了一些时间挑战一下,这里记录一下自己的解法以及思路。
24点问题,是一个有趣的问题。他的扩展问题(即把牌数/计算值进行更改),很可能也是一个NP-完全问题,他与subset sum problem问题有一些些类似。如果参考subset sum problem问题的解法(例如做一些动态优化解),则可以实现还比较优的解。
不过,这一次的比赛,是要求在一条SQL里面实现,并且限制了SQL长度为10KB,所以就大大限制了实现的方式。不过最为直接的两个思路还是,“暴力的枚举”计算和“预计算结果再做哈希求解”。即便如此,在写SQL过程中,还是遇到了如下挑战需要解决:
- 使用单条SQL进行暴力枚举的时候,如何在没有for/while等循环控制,如何遍历所有的可能性
- 哈希数组的空间占用比较大,可能会超过10KB,如何去压缩或者减少需要构建的数组
另外,实现过程中,可能涉及到浮点数计算、除数为零等问题的处理,也是非常容易出错的。
另一个角度,这些,也是这道题,有趣的地方。
“一条SQL算24点”的题目回顾
这次的题目,与一般意义上24点略有一些不同:
- 首先,要求一条SQL内完成;对于穷举、哈希的实现本身就有挑战了。需要对SQL比较熟悉,否则很难写出正确、高性能的SQL
- SQL大小限制为10KB,所以,并不能简单的穷举,简单的CASE WHEN 10KB肯定是不够的
- 4个数字,被限制为1~10,而不是13,所以搜索空间是相对来说少了一些的,让10KB以内哈希成为可能