車に乗っているときなど、対向車のナンバーを見て足したり引いたり、掛けたり割ったりして10を作る遊びを、やったことがあると思いますが、たまに難しい問題があって、モヤモヤすることがあります。それに、解けない組み合わせはいくつあるのか、というのも気になります。ということで、4つの0〜9の数字の組と、演算子の組み合わせすべてを試し、結果を表示するプログラムを書いてみることにします。
参考にしたもの:
どうやるか
参考の3つ目のサイトはPythonでやってます。ただ、数式を文字列にしてeval関数に渡しているので、実行速度は極端に遅くなります(プログラミング FAQ — Python 2.7ja1 documentation:を参照)。なので、参考サイト2つめにあるように、演算子を、減算・除算に関しては、順序の区別をつけた6つの演算子とします。すなわち、
from operator import add, sub, mul, div
def rsub(a, b):
return sub(b, a)
def rdiv(a, b):
return div(b, a)
o = [add, sub, rsub, mul, div, rdiv]
として演算子のリストをつくります。演算子の3回の使われ方は、a,b,c,dを数、o1,o2,o3を演算子とすると、
((a o1 b) o2 c) o3 d ・・・ 1
(a o1 b) o3 (c o2 d) ・・・ 2
の2通りのみです。
a,b,c,dの選び方は4!=24通りですが、1のとき、a,bを入れ替えたものは重複するので、組み合わせは24/2=12通りになります。具体的には以下のように書けば、文字列q('1337'など)から、('1337'での'3'ような)数字の重複を除いたすべての場合をリストXに格納できます。
from itertools import combinations
q = [float(i) for i in list(q)]
X = []
for a, b in combinations([0, 1, 2, 3], 2):
t = [0, 1, 2, 3]
t.remove(a)
t.remove(b)
x = (q[a], q[b], q[t[0]], q[t[1]])
if not x in X:
X.append(x)
x = (q[a], q[b], q[t[1]], q[t[0]])
if not x in X:
X.append(x)
2の時はa,bの組み合わせ、c,dの組み合わせ、(a,b)と(c，d)の組み合わせそれぞれについて入れ替えたものは考える必要がないので、3通りの数字の並びを考えれば良いことが分かります。数が少ないので、組み合わせを考えるより、ベタ書きしたほうがわかりやすいかもしれません。
X = [
(q[0], q[1], q[2], q[3]),
(q[0], q[2], q[1], q[3]),
(q[0], q[3], q[1], q[2]),
]
o1の選び方は、6つのものを3ヶ所に割り振るので6の3乗=216通り考えれば良いことになります。
from itertools import product
O = [i for i in product(range(6), repeat=3)]
で、すべての組み合わせが作れます。
あとは、Oのすべての組み合わせに対して、2つのパターンについてXの中身を用いて計算を行ない、10になったものを記録していけば良いことが分かります。その際、ZeroDivisionErrorが出るので、例外処理してやる必要があります。答えは文字列に変換し、見てわかりやすいものになるようにしてみました。また、計算機の性質上、若干の誤差が生じることがあるので、1を9の3乗で割った数(=0.0013717421124828531...)より小さい数(0.001)の誤差を許すことにしました。
制作物
実際に作ったものを以下に示します。IPython Notebook上で動かしていたので、関数の定義のみです。
from itertools import permutations, combinations, product
from operator import add, sub, mul, div
from ipython_doctester import test
# @test
def make10(q='1337', verbose=True):
"""Make 10 from 4 numbers(0~9).
q : String, ex) 1337
verbose: Bool, print the results or not
doctest code:
>>> make10()
((7/3)+1)*3
True
"""
q = [float(i) for i in list(q)]
def rsub(a, b):
return sub(b, a)
def rdiv(a, b):
return div(b, a)
o = [add, sub, rsub, mul, div, rdiv]
o_k = ['+', '-', '-', '*', '/', '/']
O = [i for i in product(range(6), repeat=3)]
TOL = 0.001
res = []
for o1, o2, o3 in O:
# ((a o1 b) o2 c) o3 d
X = []
for a, b in combinations([0, 1, 2, 3], 2):
t = [0, 1, 2, 3]
t.remove(a)
t.remove(b)
x = (q[a], q[b], q[t[0]], q[t[1]])
if not x in X:
X.append(x)
x = (q[a], q[b], q[t[1]], q[t[0]])
if not x in X:
X.append(x)
for a, b, c, d in X:
try:
result = o[o3](o[o2](o[o1](a, b), c), d)
except ZeroDivisionError:
continue
if abs(result - 10) < TOL:
if o1 == 2 or o1 == 5:
a, b = b, a
p1 = "(%d%s%d)" % (a, o_k[o1], b)
if o2 == 2 or o2 == 5:
p2 = "%d%s" % (c, o_k[o2]) + p1
else:
p2 = p1 + "%s%d" % (o_k[o2], c)
if o3 == 2 or o3 == 5:
p = "%d%s" % (d, o_k[o3]) + "(" + p2 + ")"
else:
p = "(" + p2 + ")" + "%s%d" % (o_k[o3], d)
res.append(p)
# (a o1 b) o3 (c o2 d)
X = [
(q[0], q[1], q[2], q[3]),
(q[0], q[2], q[1], q[3]),
(q[0], q[3], q[1], q[2]),
]
for a, b, c, d in X:
try:
result = o[o3](o[o1](a, b), o[o2](c, d))
except ZeroDivisionError:
continue
if abs(result - 10) < TOL:
if o1 == 2 or o1 == 5:
a, b = b, a
p1 = "(%d%s%d)" % (a, o_k[o1], b)
if o2 == 2 or o2 == 5:
c, d = d, c
p2 = "(%d%s%d)" % (c, o_k[o2], d)
if o3 == 2 or o3 == 5:
p = p2 + o_k[o3] + p1
else:
p = p1 + o_k[o3] + p2
res.append(p)
if verbose:
for r in res:
print r
if len(res) > 0:
return True
else:
return False
次に、これをすべての数の組み合わせに対して計算してみると、
import itertools
A = [''.join(i) for i in
itertools.combinations_with_replacement(
[str(x) for x in range(10)], 4)]
index_A = [make10(a, verbose=False) for a in A]
false = [a for i,a in enumerate(A) if not index_A[i]]
print len(false), false
結果は
163 ['0000', '0001', '0002', '0003', '0004', '0005', '0006', '0007', '0008', '0009', '0011', '0012', '0013', '0014', '0015', '0016', '0017', '0018', '0022', '0023', '0024', '0026', '0027', '0029', '0033', '0034', '0035', '0036', '0038', '0039', '0044', '0045', '0047', '0048', '0049', '0056', '0057', '0058', '0059', '0066', '0067', '0068', '0069', '0077', '0078', '0079', '0088', '0089', '0099', '0111', '0112', '0113', '0114', '0116', '0117', '0122', '0123', '0134', '0144', '0148', '0157', '0158', '0166', '0167', '0168', '0177', '0178', '0188', '0222', '0233', '0236', '0269', '0277', '0279', '0299', '0333', '0335', '0336', '0338', '0344', '0345', '0348', '0359', '0366', '0369', '0388', '0389', '0399', '0444', '0445', '0447', '0448', '0457', '0478', '0479', '0489', '0499', '0566', '0567', '0577', '0588', '0589', '0599', '0666', '0667', '0668', '0677', '0678', '0689', '0699', '0777', '0778', '0788', '0799', '0888', '1111', '1112', '1113', '1122', '1159', '1169', '1177', '1178', '1179', '1188', '1399', '1444', '1499', '1666', '1667', '1677', '1699', '1777', '2257', '3444', '3669', '3779', '3999', '4444', '4459', '4477', '4558', '4899', '4999', '5668', '5788', '5799', '5899', '6666', '6667', '6677', '6777', '6778', '6888', '6899', '6999', '7777', '7788', '7789', '7799', '7888', '7999', '8899']
となり、Wikipediaに載っていたものと同じ結果となっています。
まとめ
反復計算も10秒くらいかかってたのが2.5秒位になったし(とはいえ遅い)、組み合わせの書き方とか内包表記とか、やってていろいろ勉強になりました。演算子の数を増やしてベキやログを入れることもできるし、つながった文字列ではなく、空白を入れて2桁、3桁の数字を計算に使うようにも出来るでしょうね。
なにか間違いや、もっとこうしたらいいのでは?というのがあれば、ご指摘をおねがいします。