小町算（もどき）

W-ZERO3でPython Windows CE portを使って書いた。
うろ覚えで書いたらルールが微妙に違ってたけどまあいいや。

# -*- coding: utf-8 -*-

def solve_komachi(answer, *terms):
    for e in iter_komachi(terms):
        try:
            if e() == answer:
                yield e
        except ArithmeticError, e:
            pass

def iter_komachi(terms):
    n = len(terms)
    if n > 0:
        if n == 1:
            yield terms[0]
        else:
            for i in xrange(1, len(terms)):
                lhs = terms[:i]
                rhs = terms[i:]
                for l in iter_komachi(lhs):
                    for r in iter_komachi(rhs):
                        for op in operators:
                            yield expr(op, l, r)

class operator(object):
    def __init__(self, symbol, precedence, exchangeable, func):
        self.symbol       = symbol
        self.precedence   = precedence
        self.exchangeable = exchangeable
        self.func         = func

    def __call__(self, lhs, rhs):
        return self.func(lhs, rhs)

    def __repr__(self):
        return self.symbol

operators = [
    operator('+', 1, True,  lambda lhs, rhs: lhs + rhs),
    operator('-', 1, False, lambda lhs, rhs: lhs - rhs),
    operator('*', 2, True,  lambda lhs, rhs: lhs * rhs),
    operator('/', 2, False, lambda lhs, rhs: float(lhs) / rhs),
]

class expr(object):
    def __init__(self, op, lhs, rhs):
        self.op  = op
        self.lhs = lhs
        self.rhs = rhs

    def eval(self):
        lhs = self.lhs
        rhs = self.rhs
        if callable(lhs): lhs = lhs()
        if callable(rhs): rhs = rhs()
        return self.op(lhs, rhs)

    def __str__(self):
        op  = self.op
        lhs = self.lhs
        if isinstance(lhs, expr) and \
           lhs.op.precedence < op.precedence:
            lhs = "(%s)" % lhs
        rhs = self.rhs
        if isinstance(rhs, expr) and \
           (op.precedence > rhs.op.precedence or \
            ((op.precedence == rhs.op.precedence) and \
             (not op.exchangeable))):
            rhs = "(%s)" % rhs
        return "%s %s %s" % (lhs, op, rhs)

    __call__ = eval

def main(answer, *terms):
    tbl = {}
    for e in solve_komachi(answer, *terms):
        s = "%s = %d" % (e, answer)
        if not tbl.has_key(s):
            print s
            tbl[s] = True

if __name__ == '__main__':
    import sys
    main(*map(int, sys.argv[1:]))

実行例：

$ python komachi.py 10 1 2 3 4
1 + 2 + 3 + 4 = 10
1 * (2 * 3 + 4) = 10
1 * 2 * 3 + 4 = 10