小町算 #3 - odz buffer

下のダメダメなのは捨てて、有理数を導入したまじめなのを。

import sys
import re
from rational import Rational

OPERATORS = '+ - * / '.split(' ')

NUM_PAT = re.compile(r'\d+')
def exp_eval(exp):
    r = Rational
    fixed_exp = NUM_PAT.sub(r'r(\g<0>)', exp)
    return eval(fixed_exp)

def komachi(numbers, result):
    return (exp for exp in list_exp(numbers) if exp_eval(exp) == result)

def list_exp(numbers):
    if len(numbers) == 1:
        yield str(numbers[0])
    else:
        for op in OPERATORS:
            for exp in list_exp(numbers[1:]):
                yield str(numbers[0]) + op + exp

def main():
    n = 0
    for exp in komachi(range(1, 9 + 1), 100):
        print exp + '=100'
        n += 1
    print '%d pattern(s) found' % n

if __name__ == '__main__':
    main()

rational.py は以下。Rational 以外のオペランドを指定するとエラーになるという手抜きっぷり。

def gcd(x, y):
    if y == 0: return x
    else: return gcd(y, x % y)

def lcm(x, y):
    return x * y / gcd(x, y)

class Rational(object):
    def __init__(self, numerator, denominator = 1):
        self.numerator = int(numerator)
        self.denominator = int(denominator)

        c = gcd(self.numerator, self.denominator)
        if c != 1:
            self.numerator /= c
            self.denominator /= c

    def __neg__(self):
        return Rational(-self.numerator, self.denominator)

    def __add__(self, other):
        denominator = lcm(self.denominator, other.denominator)
        a = denominator / self.denominator
        b = denominator / other.denominator
        return Rational(self.numerator * a + other.numerator * b, denominator)

    def __sub__(self, other):
        return self + (-other)

    def __mul__(self, other):
        return Rational(self.numerator * other.numerator, self.denominator * other.denominator)

    def __div__(self, other):
        return self * Rational(other.denominator, other.numerator)

    def __float__(self):
        return float(self.numerator) / self.denominator

    def __int__(self):
        return self.numerator / self.denominator

    def __eq__(self, other):
        if isinstance(other, Rational):
            return (self.numerator, self.denominator) == (other.numerator, other.denominator)
        elif isinstance(other, int):
            return self.denominator == 1 and self.numerator == other
        else:
            return float(self) == other
            
    def __str__(self):
        if self.denominator == 1:
            return str(self.numerator)
        else:
            return '%d/%d' % (self.numerator, self.denominator)

    def __repr__(self):
        return '%d/%d' % (self.numerator, self.denominator)

で、電卓版に対応するために演算子の優先順位を定義できるようにしてみたバージョン。実行時に -c を付けると電卓モード。

import sys
import operator
from rational import Rational

def join(a, b):
    return a * Rational(10) + b

OPERATORS = {
    '+': operator.add,
    '-': operator.sub,
    '*': operator.mul,
    '/': operator.div,
    '':  join,
}

OPERATOR_PRIORITIES_NORMAL = {
    '+': 2,
    '-': 2,
    '*': 1,
    '/': 1,
    '': 0,
}

OPERATOR_PRIORITIES_CALC = {
    '+': 1,
    '-': 1,
    '*': 1,
    '/': 1,
    '': 0,
}

def exp_eval(exp, priorities):
    level = 0
    exp = list(exp)

    while len(exp) > 1:
        res = []
        while exp:
            val = exp.pop(0)
            if isinstance(val, Rational):
                res.append(val)
            else:
                func = OPERATORS[val]
                priority = priorities[val]
                if priority == level:
                    res.append(func(res.pop(), exp.pop(0)))
                else:
                    res.append(val)
        level += 1
        exp = res

    return exp[0]

def list_exp(numbers):
    if len(numbers) == 1:
        yield numbers
    else:
        for op, func in OPERATORS.iteritems():
            for exp in list_exp(numbers[1:]):
                yield numbers[0:1] + [op] + exp

def komachi(numbers, result, operator_priorities):
    numbers = [Rational(i) for i in numbers]
    result = Rational(result)
    return (exp for exp in list_exp(numbers) if exp_eval(exp, operator_priorities) == result)

def main(calc_mode = False):
    if calc_mode:
        operator_priorities = OPERATOR_PRIORITIES_CALC
    else:
        operator_priorities = OPERATOR_PRIORITIES_NORMAL
    
    numbers = range(1, 9 + 1)
    result = 100

    n = 0
    for exp in komachi(numbers, result, operator_priorities):
        print '%s=%d' % (''.join(map(str, exp)), result)
        n += 1
    print '%d pattern(s) found' % n

if __name__ == '__main__':
    import optparse
    parser = optparse.OptionParser()
    parser.add_option('-c', action='store_true', dest='calc_mode')
    (opts, args) = parser.parse_args()

    main(calc_mode = opts.calc_mode)

結果。

% time python komachi4.py
123+45-67+8-9=100
123+4*5-6*7+8-9=100
123+4-5+67-89=100
123-45-67+89=100
123-4-5-6-7+8-9=100
12+34+5*6+7+8+9=100
12+34-5+6*7+8+9=100
12+34-5-6+7*8+9=100
12+34-5-6-7+8*9=100
12+3+4+5-6-7+89=100
12+3+4-56/7+89=100
12+3*45+6*7-89=100
12+3*4+5+6+7*8+9=100
12+3*4+5+6-7+8*9=100
12+3*4-5-6+78+9=100
12+3-4+5+67+8+9=100
12*3-4+5-6+78-9=100
12*3-4*5+67+8+9=100
12*3-4-5-6+7+8*9=100
12-3+4*5+6+7*8+9=100
12-3+4*5+6-7+8*9=100
12-3-4+5*6+7*8+9=100
12-3-4+5*6-7+8*9=100
12-3-4+5-6+7+89=100
12/3+4*5*6*7/8-9=100
12/3+4*5*6-7-8-9=100
12/3+4*5-6-7+89=100
12/3/4+5*6+78-9=100
1+234*5*6/78+9=100
1+234*5/6-7-89=100
1+234-56-7-8*9=100
1+23*4+56/7+8-9=100
1+23*4+5-6+7-8+9=100
1+23*4-5+6+7+8-9=100
1+23-4+56+7+8+9=100
1+23-4+56/7+8*9=100
1+23-4+5+6+78-9=100
1+23-4-5+6+7+8*9=100
1+2+34*5+6-7-8*9=100
1+2+34-5+67-8+9=100
1+2+3+4+5+6+7+8*9=100
1+2+3*4*56/7-8+9=100
1+2+3*4*5/6+78+9=100
1+2+3*4-5-6+7+89=100
1+2+3-45+67+8*9=100
1+2+3-4+5+6+78+9=100
1+2+3-4*5+6*7+8*9=100
1+2*34-56+78+9=100
1+2*3+4+5+67+8+9=100
1+2*3+4*5-6+7+8*9=100
1+2*3*4*5/6+7+8*9=100
1+2*3-4+56/7+89=100
1+2*3-4-5+6+7+89=100
1+2-3*4+5*6+7+8*9=100
1+2-3*4-5+6*7+8*9=100
1*234+5-67-8*9=100
1*23+4+56/7*8+9=100
1*23+4+5+67-8+9=100
1*23*4-56/7/8+9=100
1*23-4+5-6-7+89=100
1*23-4-56/7+89=100
1*2+34+56+7-8+9=100
1*2+34+5+6*7+8+9=100
1*2+34+5-6+7*8+9=100
1*2+34+5-6-7+8*9=100
1*2+34-56/7+8*9=100
1*2+3+45+67-8-9=100
1*2+3+4*5+6+78-9=100
1*2+3*4+5-6+78+9=100
1*2+3-4+5*6+78-9=100
1*2*34+56-7-8-9=100
1*2*3+4+5+6+7+8*9=100
1*2*3*4+5+6+7*8+9=100
1*2*3*4+5+6-7+8*9=100
1*2*3*4-5-6+78+9=100
1*2*3-45+67+8*9=100
1*2*3-4+5+6+78+9=100
1*2*3-4*5+6*7+8*9=100
1*2-3+4+56/7+89=100
1*2-3+4*5-6+78+9=100
1*2-3+4-5+6+7+89=100
1*2/3+4*5/6+7+89=100
1-23+4*5+6+7+89=100
1-23-4+5*6+7+89=100
1-23-4-5+6*7+89=100
1-2+3+45+6+7*8-9=100
1-2+3*4+5+67+8+9=100
1-2+3*4*5+6*7+8-9=100
1-2+3*4*5-6+7*8-9=100
1-2*3+4*5+6+7+8*9=100
1-2*3-4+5*6+7+8*9=100
1-2*3-4-5+6*7+8*9=100
1-2-34+56+7+8*9=100
1-2-3+45+6*7+8+9=100
1-2-3+45-6+7*8+9=100
1-2-3+45-6-7+8*9=100
1-2-3+4*56/7+8*9=100
1-2-3+4*5+67+8+9=100
1/2*34-5+6-7+89=100
1/2*3/4*56+7+8*9=100
1/2/3*456+7+8+9=100
101 pattern(s) found
python komachi4.py  37.97s user 0.00s system 99% cpu 38.083 total

% time python komachi4.py -c
123+45-67+8-9=100
123+4-5+67-89=100
123-45-67+89=100
123-45/6+78+9=100
123-4-5-6-7+8-9=100
12+3+4+5-6-7+89=100
12+3+4+5/6+7+89=100
12+3*4-56+7+89=100
12+3*4/5+6-7+89=100
12+3-4+5+67+8+9=100
12*3-4+5-6+78-9=100
12-3+4+5*6-7+8-9=100
12-3*4+56+7-8+9=100
12-3-4+5-6+7+89=100
12-3-4*5+6+78-9=100
12/3+4-5*6-7+89=100
12/3*4+5+6*7-89=100
1+23+4+5-6*7-89=100
1+23-4+56+7+8+9=100
1+23-4+5+6+78-9=100
1+23-4*5+6-7-8+9=100
1+23-4*5-6+7+8-9=100
1+23-4-5*6-7+8+9=100
1+2+34-5+67-8+9=100
1+2+3+4+5*6-7+8+9=100
1+2+3+4*5+67-8-9=100
1+2+3*4-5-6+78+9=100
1+2+3-4+5+6+78+9=100
1+2+3-4+5/6*78+9=100
1+2+3-4*5-6+7+89=100
1+2*3+4+5*6-7+8-9=100
1+2*3*4+56+7-8+9=100
1+2*3-4+5-6+7+89=100
1+2*3-4*5+6+78-9=100
1+2/3+4+5-6+7+89=100
1+2/3+4*5+6+78-9=100
1*23+4+5+67-8+9=100
1*23-4+5-6-7+89=100
1*23-4+5/6+7+89=100
1*2+34+56+7-8+9=100
1*2+3+45+67-8-9=100
1*2+3*4+56+7+8+9=100
1*2+3*4+5+6+78-9=100
1*2+3*4*5+6-7-8+9=100
1*2+3*4*5-6+7+8-9=100
1*2+3*4-5*6-7+8+9=100
1*2*34+56-7-8-9=100
1*2*3+4+5*6-7+8+9=100
1*2*3+4*5+67-8-9=100
1*2*3*4-5-6+78+9=100
1*2*3-4+5+6+78+9=100
1*2*3-4+5/6*78+9=100
1*2*3-4*5-6+7+89=100
1*2-3+4*5*6-7+8+9=100
1*2-3+4-5+6+7+89=100
1*2/3/4+5*6+78-9=100
1*2/3/4-5+6*78+9=100
1-2+3*4-5*6-7+89=100
1-2+3-4+5*6-7+89=100
1-2*3-4+5+6+7+89=100
1-2/3+4*5*6+7-8-9=100
1-2/3-4+5*6+7+89=100
1/2+3*4+5-6+78+9=100
1/2+3*4*5+6+7+8+9=100
1/2+3-4+5*6*7-89=100
1/2*34-5+6-7+89=100
1/2-3*4/5+6+7+89=100
1/2/3*456+7+8+9=100
68 pattern(s) found
python komachi4.py -c  34.96s user 0.01s system 99% cpu 35.011 total