4つの数字で10を作るゲーム解説

皆さんもきっと昔一度はやったことがあるかと思います。車のナンバープレートや切符に書かれた4桁の数字と四則演算のみを使って10を作るゲームを。スイカやパスモの普及率が高くなってからこのゲームが絶滅してしまうのではないかと冷や冷やしていましたが、先日ツイッターのタイムライン上にこのゲームについての話題が溢れている時間帯がありました。せっかくの機会なのでプログラムで解いてみます。問題の前提条件としては、「数字の順番は入れ替えても良い」「四則演算しか使ってはいけない」「括弧は使用可能」というのが私の周りでのルールでしたので、今回もそれに従ってみます。


ちなみにこの問題は高校生の頃解いたことがあるのですが、結論から言ってしまうと
「1〜9までの異なる4種類の数字の組み合わせで、10を作れないものは無い」
です。


さらに、一番難しい(方法が少ない)のは
「3 4 7 8」
の組み合わせです。


ある人はこのようなプログラムで解いていました。

from itertools import permutations

QUESTION = '1234'

for x, y, z in permutations('+-*/', 3):
    for a, b, c, d in permutations(QUESTION):
        f = ('%s' * 7) % (a, x, b, y, c, z, d)
        if eval(f) == 10:
            print f

これで解けるものが大半ですが、実はこれでは解けないものがあります。
それが例えば 3, 4, 7, 8 の組み合わせです。


で、なぜ解けないのかと言うと理由は2つあり、「演算を全て整数で行っているから」「演算順序を規定する括弧を使用していないから」です。


例えば上記プログラムで QUESTION = '3478' としてみると、

3+7-4/8
3+8-7/4
4+8-7/3
7+3-4/8
8+3-7/4
8+4-7/3
3-4/8+7
3-7/4+8
4-7/3+8
7-4/8+3
8-7/3+4
8-7/4+3
8/3*7-4

という出力が得られますが、どれも不正解です。


そこで、以下のような浮動小数点を使うプログラムにするか、あるいは分数演算を使用して解くのがよりスマートな方法となります。


浮動小数点を使った場合はこのような感じでしょうか。

QUESTION = '3478'

TOL = 0.001

PATTERNS = [
    '%s%s%s%s%s%s%s',
    '(%s%s%s)%s%s%s%s',
    '(%s%s%s%s%s)%s%s',
    '%s%s(%s%s%s)%s%s',
    '%s%s(%s%s%s%s%s)',
    '%s%s%s%s(%s%s%s)',
    '(%s%s%s)%s(%s%s%s)',
]

from itertools import permutations

for x, y, z in permutations('+-*/', 3):
    for a, b, c, d in permutations(QUESTION):
        a, b, c, d = ['%s.0' % n for n in [a, b, c, d]]
        for pattern in PATTERNS:
            f = pattern % (a, x, b, y, c, z, d)
            try:
                result = eval(f)
            except ZeroDivisionError:
                continue
            if abs(result - 10) < TOL:
                print f

出力結果は

(3.0-7.0/4.0)*8.0
8.0*(3.0-7.0/4.0)

となり、正しい結果が得られました。ちなみに TOL という定数は Tolerance の略ですが、これは1を1桁の数字の最大値9で3回割った値(=0.00137...)より少し小さい値にするのが妥当でしょう。


また、分数演算を使った場合は以下のようになります。

QUESTION = '3478'

PATTERNS = [
    '%s%s%s%s%s%s%s',
    '(%s%s%s)%s%s%s%s',
    '(%s%s%s%s%s)%s%s',
    '%s%s(%s%s%s)%s%s',
    '%s%s(%s%s%s%s%s)',
    '%s%s%s%s(%s%s%s)',
    '(%s%s%s)%s(%s%s%s)',
]

class Fraction(object):
    """
        Fraction(10, 3) means 10/3
    """
    
    def __init__(self, a, b=1):
        if isinstance(a, int):
            self._a = a
            self._b = b
            self._normalize()
        elif isinstance(a, Fraction):
            self._a = a._a
            self._b = a._b
        else:
            assert False, 'Invalid argument.[%s]' % a
    
    def __str__(self):
        if self._b == 1:
            return str(self._a)
        return '%d/%d' % (self._a, self._b)
    
    def _normalize(self):
        d = Fraction._gcd(self._a, self._b)
        self._a /= d
        self._b /= d
        if self._b < 0:
            self._a *= -1
            self._b *= -1
    
    @classmethod
    def _gcd(cls, a, b):
        r = a % b
        while r != 0:
            a, b = b, r
            r = a % b
        return b
    
    def __add__(self, rhs):
        rhs = Fraction(rhs)
        ret = Fraction(0)
        ret._a = self._a * rhs._b + self._b * rhs._a
        ret._b = self._b * rhs._b
        ret._normalize()
        return ret
    
    def __radd__(self, lhs):
        return self + lhs
    
    def __sub__(self, rhs):
        rhs = Fraction(rhs)
        ret = Fraction(0)
        ret._a = self._a * rhs._b - self._b * rhs._a
        ret._b = self._b * rhs._b
        ret._normalize()
        return ret
    
    def __rsub__(self, lhs):
        return self - lhs
    
    def __mul__(self, rhs):
        rhs = Fraction(rhs)
        ret = Fraction(0)
        ret._a = self._a * rhs._a
        ret._b = self._b * rhs._b
        ret._normalize()
        return ret
    
    def __rmul__(self, lhs):
        return self * lhs
    
    def __div__(self, rhs):
        rhs = Fraction(rhs)
        ret = Fraction(0)
        ret._a = self._a * rhs._b
        ret._b = self._b * rhs._a
        ret._normalize()
        return ret
    
    def __rdiv__(self, lhs):
        return self / lhs
    
    def __abs__(self):
        return Fraction(abs(self._a), abs(self._b))
    
    def __eq__(self, rhs):
        rhs = Fraction(rhs)
        return self._a == rhs._a and self._b and rhs._b

from itertools import permutations

for x, y, z in permutations('+-*/', 3):
    for a, b, c, d in permutations(QUESTION):
        fa, fb, fc, fd = ['Fraction(%s)' % n for n in [a, b, c, d]]
        for pattern in PATTERNS:
            f = pattern % (fa, x, fb, y, fc, z, fd)
            try:
                result = eval(f)
            except ZeroDivisionError:
                continue
            if result == 10:
                print pattern % (a, x, b, y, c, z, d)

出力結果は

(3-7/4)*8
8*(3-7/4)

となり、正しく動いていそうです。


なお、上記で使用した分数クラスFractionはコインランドリーで乾燥待ちの間に書いた適当なクラスなので、ご利用は自由ですがご自身の責任で使ってください。単体テストすら書いていませんので、バグがありそうな気がします。というか分数クラスくらい誰かが用意してくれていそうなので、是非それを使いましょう(笑)。


また、PATTERNSのあたりがちょっと気持ち悪く感じる方がいるかと思いますが、その感情を大事にしてください(笑)。乾燥待ちの時間ではそこを自動化する余力はありませんでしたので、興味のある方は数字が4つではなく9個になってもプログラムの修正がほぼ不要なように編集してみてはいかがでしょうか。きっと楽しめるかと思います。括弧の付け方が何通りあるか、などは数学の世界では歴史のある話題なので、あわせて調べてみても面白いかもしれませんね。楽をしたい方は括弧が不要の逆ポーランド記法で実装してみるのが良いかと思います。