日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。
問９３「算術式」
集合 {1, 2, 3, 4} の各数字をちょうど一度用い, また四則演算 (+, －, *, /) と括弧を使うことにより, 異なる正の整数を作ることができる.
例えば,
8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) － 1
36 = 3 * 4 * (2 + 1)
12 + 34 のように数字をつなげることは許されないことに注意しよう.
集合 {1, 2, 3, 4} を使うと, 36 を最大とする 31 個の異なる数が得られる.
最初の表現できない数に会うまで, 1 から 28 の各数を得ることができる.
最長の連続した正の整数 1 から n の集合を得ることができる, 4 つの異なる数字 a < b < c < d を見つけよ. 答えを文字列 abcd として与えよ.
注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。
私の回答例は以下の通りです。
def f():
import itertools
r = 0
#括弧の位置 [0]a-[1]b[2]-[3]c[4]-d[5]
kakko = [("(((","",")","",")",")"), ("(","",")","(","",")"), ("","(","","",")","")]
for t in itertools.combinations(xrange(1, 10), 4):
D = {}
for b in itertools.permutations(t):
f = [str(i)+".0" for i in b]
for m in itertools.product("+-*/", repeat=3):
for k in kakko:
s0= k[0]+f[0]+m[0]+k[1]+f[1]+k[2]+m[1]+k[3]+f[2]+k[4]+m[2]+f[3]+k[5]
try: s1 = eval(s0)
except ZeroDivisionError: continue
if int(s1)==s1: D[int(s1)] = s0
for i in xrange(1, max(D.keys())+1):
if i not in D.keys(): break
if r<i-1: p, r, w = t, i-1, [D[j] for j in xrange(1,i)]
p = "".join([str(i) for i in p])
w = [s.replace(".0","")+"="+str(int(eval(s))) for s in w]
return p,r,w
ans, vol, pat = f()
print "ans:",ans
print "vol:",vol
print "pat:",pat
総当りです。１分ルールには間に合いました。
式の文字列として作り出し、eval関数で計算式として計算します。
・9個の数字から異なる４つを選ぶパターンは、重複なし組合せで、9C4 = 126通り。
・4つの異なる数字の並び順パターンは、重複なし順列で、4P4 = 4! = 24通り。
・四則演算を3回行うパターン数は、重複あり順列で、4の3乗で64通り。
・数字が4個のとき、カッコのパターン数は並1べ順替えを考慮すると以下の3通り。
例えば以下のとおり。
(((9 - 5)- 2)- 1) = 9-5-2-1 = 1
(9 - 5)-(2 - 1) = 9-5-2+1 = 3
9 -(5 - 2)- 1 = 9-5+2-1 = 5
126x24x64x3 = 580,608通りを総当りで試しました。
文字型で式を作成した後、eval関数で計算式そのものに変換して実行します。
割り算記号がどこに来ても切り捨てられないように、全ての数字の後ろに「.0」を追加しておきます。
割り算でゼロ除算になる場合は、try-exceptでつかまえて次のケースに進みます。
計算結果の小数有無判定はint関数結果と同じ値になるかで判定します。
計算結果が正の整数値の場合、辞書（連想配列）Dに式そのものをためていきます。
連続判定では、リストDのキーに1からの連続値があるところi番目の1つ前、i-1番目まで連続です。
最長判定では、変数rに連続パターン件数をとっておき、最長かどうかを判定します。
求められている数字の組のパターンの他、連続個数とその式も表示します。
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
ans: 1258
vol: 51
pat: ['(8-5)/(2+1)=1', '(8-5)-(2-1)=2', '(8-5)/(2-1)=3', '8-(5-2)-1=4','(((8-5)*2)-1)=5', '(8-5)*(2/1)=6', '(((8-5)*2)+1)=7', '(((8-5)+1)*2)=8', '(8-5)*(2+1)=9', '8+(5-2)-1=10', '8+(5-2)/1=11', '(8+5)-(2-1)=12', '(8+5)/(2-1)=13', '8+(5+2)-1=14', '8+(5+2)/1=15', '8+(5+2)+1=16', '8+(5*2)-1=17', '8+(5*2)/1=18', '8*(5/2)-1=19', '8*(5/2)/1=20', '8*(5/2)+1=21', '(8*2)+(5+1)=22', '8*(5-2)-1=23', '8*(5-2)/1=24', '8*(5-2)+1=25', '(8+5)*(2/1)=26', '(((8+5)*2)+1)=27', '(((8+5)+1)*2)=28', '(((8-2)*5)-1)=29', '8*(5-1)-2=30', '(((8-2)*5)+1)=31', '(((5-2)+1)*8)=32', '(((8-1)*5)-2)=33', '8*(5-1)+2=34', '(((8-2)+1)*5)=35', '(8-2)*(5+1)=36', '(((8*5)-2)-1)=37', '(8*5)-(2/1)=38', '(8*5)-(2-1)=39', '(8*5)/(2-1)=40', '(8*5)+(2-1)=41', '(8*5)+(2/1)=42', '(8*5)+(2+1)=43', '(((1/2)+5)*8)=44', '(((8+2)-1)*5)=45', '8*(5+1)-2=46', '(((8+1)*5)+2)=47', '(((5+2)-1)*8)=48', '(((8+2)*5)-1)=49', '8*(5+1)+2=50', '(((8+2)*5)+1)=51']
