小町算 in Python DouKaku?

古典的なパズルである小町算を解くプログラムを作成してください。

小町算とは：

1□2□3□4□5□6□7□8□9＝100

四角の中に、空白、＋、－、×、÷のいずれかを一つ入れ、等式が成り立つようにするパズルです。

解答例：

1－2－3＋4×56÷7＋8×9＝100

1＋234×5÷6－7－89＝100

参考：　http://ja.wikipedia.org/wiki/%E5%B0%8F%E7%94%BA%E7%AE%97

evalやそれに類するものを使うか否かは自由です。
割り算の際には小数点以下の切捨てが起こらないのが望ましいです。(必須ではない)
- 切捨てが起こる場合の解答例：1÷2÷3＋4＋5÷6＋7＋89＝100
余裕があれば括弧を含むようにしてもいいかもしれません。

手元で20数行ほどのPythonスクリプトを書いてみたところ、101個の解答が得られました。

pythonでナイーブな実装。
括弧なしで101個でした。

def komachi():
    num = range(1,10)
    ope = ["",".0+",".0-",".0*",".0/"]
    c = 1
    for x in xrange(5**8):
        formula = str(num[0])
        for n in range(1,9):
            formula += ope[x%5] + str(num[n])
            x /= 5
        if eval(formula) == 100:
           print formula,c
           c += 1
           

komachi()

順当な遅さです。

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

from __future__ import division
import re

E = '1%s2%s3%s4%s5%s6%s7%s8%s9==100'
A = ['', '+', '-', '*', '/']
F = lambda n: [[i] + l for i in A for l in F(n-1)] if n > 1 else [[i] for i in A]
R = lambda s: s.replace('+', u'＋').replace('-', u'－').replace('*', u'×').replace('/', u'÷').replace('==', u'＝')

print '\n'.join([R(E % tuple(l)) for l in F(8) if eval(E % tuple(l))])

日記の方に一度書いたソースですが、そのまま載せます。

from __future__ import division
import itertools

def permutation(*args):
    D = dict([(id(L), L) for L in args])
    def permutation_(*args):
        if not args:
            yield []
        elif len(args) == 1:
            D[id(args[0])], g = itertools.tee(D[id(args[0])])
            for x in g:
                yield [x]
        else:
            D[id(args[0])], g = itertools.tee(D[id(args[0])])
            for x in g:
                for y in permutation_(*args[1:]):
                    yield [x] + y
    return permutation_(*args)

c = itertools.count(1)
ops = ['+', '-', '*', '/', '']
L = ['1', ops, '2', ops, '3', ops, '4', ops, '5', ops, '6', ops, '7', ops, '8', ops, '9']
for exp in permutation(*L):
    exp = ''.join(exp)
    if eval(exp) == 100:
        print exp, c.next()

DouKaku?

小町算

Posted feedbacks - Python

Index

Feed

Other

Link

Pathtraq