# 问题 #
为了更深入的测试语言，我做了一个经典问题——24点。
这个问题主要是测试递归，循环效率，还有数组和树的复制性能。
为了简化问题，方便测试，我的问题是这样描述的：
> 有一个数组，里面有多个正整数。有一个操作数组，其中每个都是双目操作符。找出以两者构成算式，其值等于给定值的所有表达式组合。
> 要求不得遗漏，可以有少量重复。例如可交换算符的交换同构暂不做排重。
实际运行的时候，取+-*/和3 4 6 8，运行100次，查看时间消耗。正确的单次输出结果应当是这样的。
> (((8 + 4) / 3) * 6) = 24
> (6 / (3 / (8 + 4))) = 24
> (((8 + 4) * 6) / 3) = 24
> (((8 / 4) + 6) * 3) = 24
> (((8 – 6) * 3) * 4) = 24
> (((8 – 6) * 4) * 3) = 24
> (((3 * 4) – 
* 6) = 24
* 6) = 24> ((8 – (6 / 3)) * 4) = 24
> (((4 + / 3) * 6) = 24
/ 3) * 6) = 24> (6 / (3 / (4 + 8))) = 24
> (((4 + * 6) / 3) = 24
* 6) / 3) = 24> (((8 / 4) + 6) * 3) = 24
> (((4 * 3) – * 6) = 24
* 6) = 24> (((8 – 6) * 3) * 4) = 24
> (((8 – 6) * 4) * 3) = 24
> ((8 – (6 / 3)) * 4) = 24
# python #
python的解很复杂，长达31行，以下是我写的解。当然，还有更简单的版本，我可以用eval来干这个事情，代码只有24行，但是确实给人很evil的感觉。
from itertools import combinations
class opt(object):
def __init__(self, name, func, ex=True):
self.name, self.func, self.exchangable = name, func, ex
def __str__(self): return self.name
def __call__(self, l, r): return self.func(l, r)
def fmt(self, l, r):
return '(%s %s %s)' % (fmt_exp(l), str(self), fmt_exp(r))
def eval_exp(e):
if not isinstance(e, tuple): return e
try: return e[0](eval_exp(e[1]), eval_exp(e[2]))
except: return None
def fmt_exp(e): return e[0].fmt(e[1], e[2]) if isinstance(e, tuple) else str(e)
def print_exp(e): print fmt_exp(e), eval_exp(e)
def chkexp(target):
def do_exp(e):
if abs(eval_exp(e) – target) < 0.001: print fmt_exp(e), '=', target
return do_exp
def iter_all_exp(f, ops, ns, e=None):
if not ns: return f(e)
for r in set(ns):
ns.remove(r)
if e is None: iter_all_exp(f, ops, ns, r)
else:
for op in ops:
iter_all_exp(f, ops, ns, (op, e, r))
if not op.exchangable:
iter_all_exp(f, ops, ns, (op, r, e))
ns.append(r)
opts = [
opt('+', lambda x, y: x+y),
opt('-', lambda x, y: x-y, False),
opt('*', lambda x, y: x*y),
opt('/', lambda x, y: float(x)/y, False),]
if __name__ == '__main__':
for i in xrange(100): iter_all_exp(chkexp(24), opts, [3, 4, 6, 8])
以下是100次的时间：
> real 0m2.259s
> user 0m2.248s
> sys 0m0.004s
# common lisp #
lisp来解这个问题简直是作弊，难怪被叫做人工智能语言。
(defun chkexp (target)
(lambda (e)
(if (equal (ignore-errors (eval e)) target) (print e))))
(defun exchangeable (op)
(not (member op '(- /))))
(defun iter-all-exp (f ops ns &optional e)
(cond
((not ns) (funcall f e))
((not e) (dolist (r (remove-duplicates ns))
(iter-all-exp f ops (remove r ns :count 1) r)))
(t (dolist (r (remove-duplicates ns))
(let ((nss (remove r ns :count 1)))
(dolist (op ops)
(iter-all-exp f ops nss `(,op ,e ,r))
(if (not (exchangeable op))
(iter-all-exp f ops nss `(,op ,r ,e)))))))))
(iter-all-exp (chkexp 24) `(+ – * /) `(3 4 6 8))
只有短短17行。原因在于，lisp本身的ast即是用数据结构表示的，因此根本不需要我做eval函数，也不需要画蛇添足的弄自定义算符，直接用系统算符上。显示，打印，都是现成的。需要写的只有主体逻辑。结果也很特别：
> (* (- (* 3 4) 6)
6) > (* (- 8 (/ 6 3)) 4)
> (* (- (* 4 3) 6)
6) > (* (/ (+ 4 3) 6)
3) 6) > (/ 6 (/ 3 (+ 4 8)))
> (/ (* (+ 4 6) 3)
6) 3) > (* (+ (/ 8 4) 6) 3)
> (* (- 8 (/ 6 3)) 4)
> (* (* (- 8 6) 3) 4)
> (* (* (- 8 6) 4) 3)
> (* (/ (+ 8 4) 3) 6)
> (/ 6 (/ 3 (+ 8 4)))
> (/ (* (+ 8 4) 6) 3)
> (* (+ (/ 8 4) 6) 3)
> (* (* (- 8 6) 3) 4)
> (* (* (- 8 6) 4) 3)
不但行数只有一半，速度也很让人吐血，比python快了近一倍，这是100次的结果。
Evaluation took:
1.379 seconds of real time
1.372086 seconds of total run time (1.372086 user, 0.000000 system)
[ Run times consist of 0.012 seconds GC time, and 1.361 seconds non-GC time. ]
99.49% CPU
3,628,800 forms interpreted
4,127,047,350 processor cycles
102,577,080 bytes consed
# go #
# lua #
lua的代码是所有语言中最罗嗦的，足足长达60行，超过python许多。
function find_item(tbl, obj)
for i, v in pairs(tbl) do
if v == obj then return i end
end
return nil
end
function remove_duplicates (tbl)
local newtbl = {}
for i, v in pairs(tbl) do
if find_item(newtbl, v) == nil then
table.insert(newtbl, v)
end
end
return newtbl
end
function fmt_exp (e)
if type(e) ~= 'table' then
return tostring(e)
else
return '(' .. fmt_exp(e[3]) .. e[1] .. fmt_exp(e[4]) .. ')'
end
end
function eval_exp (e)
if type(e) ~= 'table' then
return tonumber(e)
else
return e[2](eval_exp(e[3]), eval_exp(e[4]))
end
end
function chkexp (target)
return function (e)
if eval_exp(e) == target then
print(fmt_exp(e))
end
end
end
function iter_all_exp (f, ops, ns, e)
if table.maxn(ns) == 0 then return f(e) end
for i, r in pairs(remove_duplicates(ns)) do
table.remove(ns, find_item(ns, r))
if e == nil then
iter_all_exp(f, ops, ns, r)
else
for op, fp in pairs(ops) do
iter_all_exp(f, ops, ns, {op, fp, e, r})
if find_item(exchangable, op) == nil then
iter_all_exp(f, ops, ns, {op, fp, r, e})
end
end
end
table.insert(ns, r)
end
end
exchangable = {'+', '*'}
opts = {
['+'] = function (a, b) return a + b end,
['-'] = function (a, b) return a – b end,
['*'] = function (a, b) return a * b end,
['/'] = function (a, b) return a / b end,
}
iter_all_exp(chkexp(24), opts, {3, 4, 6, 8})
其实lua的代码很好看，自然语言风格，语言写出来后都能看懂。然而lua秉持了最小化内核的方针，死活不提供一些很常用的函数。我上来近15行全在写常用函数，查找某个值在表中的位置，还有除去表中的重复元素。实现下来，效率也不是特别高，基本和python相当。
> real 0m2.222s
> user 0m2.184s
> sys 0m0.000s