答えを与えると、ランダムに式を生成するプログラム

30分プログラム、その643。にインスパイアされて、答えからランダムに式を生成するプログラムを作ってみました。
例えば、42を与えると「1+41」とか「6*7」とかを生成してくれます。あと、どれくらいの深さまで部分式を展開するかも指定できるようにしました。
とりあえず四則演算には対応してます。意外なことに、除算は簡単で、乗算は難しかったです。

使い方

$ python expr.py 42
42 = ((5 * 22) - (138 - 70))
$ python expr.py 42
42 = ((10 + 8) + ((2 / 1) * (35 - 23)))

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-
#
# expr.py -
#
# Copyright(C) 2009 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2009/08/18 20:01:02
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#
import random
import sys

# ------------------------------
# AST
# ------------------------------
class Value:
    def __init__(self,n):
        self.value = n

    def is_value():
        return True

    def __repr__(self):
        return str(self.value)

    def map(self,f):
        return f(self.value)

class Expr:
    def __init__(self,op,left,right):
        self.op = op
        self.left = left
        self.right = right

    def is_value():
        return False

    def __repr__(self):
        return "(%s %s %s)" % (str(self.left),str(self.op),str(self.right))

    def map(self,f):
        return Expr(self.op,
                    self.left.map(f),
                    self.right.map(f))


# ------------------------------
# Generator
# ------------------------------
class Generator:
    def __init__(self):
        random.seed()

    def gen(self,n,depth):
        table = [self.id,self.add,self.sub,self.mul,self.div]
        expr = random.choice(table)(n)

        if depth == 0:
            return expr
        else:
            return expr.map(lambda e: self.gen(e,depth-1))

    def expr__(self,op,left,right):
        return Expr(op,Value(left),Value(right))

    def id(self,n):
        return Value(n)

    def add(self,n):
        if n > 2:
            right = random.randint(2,n-1)
            left  = n - right
            return self.expr__('+',left,right)
        else:
            return Value(n)

    def sub(self,n):
        right = random.randint(n,2*n)
        left  = right + n
        return self.expr__('-',left,right)

    def mul(self,n):
        if n > 0:
            xs = range(1,n)
            random.shuffle(xs)

            for x in xs:
                if n % x == 0:
                    return self.expr__('*',n/x,x)
        else:
            return Value(n)

    def div(self,n):
        if n > 0:
            right = random.randint(1,n)
            left  = n * right
            return self.expr__('/',left,right)
        else:
            return Value(n)


# ------------------------------
# main
# ------------------------------
if __name__ == '__main__':
    gen = Generator()
    for arg in sys.argv[1:]:
        n = int(arg)
        print '%d = %s' % (n,gen.gen(n,depth=2))

参考

• 過去の30分プログラム