Problem 93
集合{1, 2, 3, 4}から一度ずつ数字を使って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}を使うと、31個の違う狙いの数を得ることができ、36がその最大で、1から28の各々の数が最初の表せない数に出会う前に得られる。
4つの異なる数字、a < b < c < dの集合で、1からnの連続した正の整数の最も長い集合となるものを求めよ。答えは文字列abcdで与えよ。
http://projecteuler.net/index.php?section=problems&id=93
例えば1,2,3,4という並びなら、まず2つに分けます。分け方は、
(1),(2,3,4)
(1,2),(3,4)
(1,2,3),(4)
の3つがあります。それぞれ分けた中で演算して出てきた数を演算すればすべての結果が出てきます。
ただし、例えば、
(1 / 2 + 3) * 4
のように分数の計算が必要な場合があるので、常に分数で値を持っておくほうがよいでしょう。しかし、Pythonの分数は非常に遅いので、(分子,分母)というタプルにして、演算も自分で定義したほうがよいです。ここでは、約分はせずに分母は必ず正ということにしています。
from itertools import permutations, takewhile, \ product, izip, count, combinations def gen_number(a): if len(a) == 1: yield a[0] else: for k in range(1, len(a)): for m, n, op in product(gen_number(a[:k]), gen_number(a[k:]), operators): if n[0] != 0 or op != div: yield op(m, n) def add(x, y): return (x[0] * y[1] + y[0] * x[1], x[1] * y[1]) def sub(x, y): return (x[0] * y[1] - y[0] * x[1], x[1] * y[1]) def mul(x, y): return (x[0] * y[0], x[1] * y[1]) def div(x, y): if y[0] < 0: y = (-y[0], -y[1]) return (x[0] * y[1], x[1] * y[0]) operators = (add, sub, mul, div) def last_of_consecutive_set(a): s = set(map(lambda f: f[0] / f[1], filter(lambda f: f[0] > 0 and f[0] % f[1] == 0, (f for b in permutations(a) for f in gen_number(b))))) a = list(s) a.sort() return len(list(takewhile(lambda t: t[0] == t[1], izip(a, count(1))))) N = 4 def longer(x, y): return x if x[1] >= y[1] else y a = reduce(longer, ((a, last_of_consecutive_set(a)) for a in combinations(((n, 1) for n in range(1, 10)), N))) print reduce(lambda x, y: x * 10 + y[0], a[0], 0)
