问题

为了更深入的测试语言，我做了一个经典问题——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) - 8) * 6) = 24
((8 - (6 / 3)) * 4) = 24
(((4 + 8) / 3) * 6) = 24
(6 / (3 / (4 + 8))) = 24
(((4 + 8) * 6) / 3) = 24
(((8 / 4) + 6) * 3) = 24
(((4 * 3) - 8) * 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) 8) 6)
(* (- 8 (/ 6 3)) 4)
(* (- (* 4 3) 8) 6)
(* (/ (+ 4 8) 3) 6)
(/ 6 (/ 3 (+ 4 8)))
(/ (* (+ 4 8) 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