Mathematically Lucky Tickets (Mine) - 115810で100を作る
どんな問題？
Mathematically Lucky Tickets
http://www.checkio.org/mission/mathematically-lucky-tickets/
6桁の数字がラッキーナンバーかどうかを判定せよ。6桁を分割して、いくつかの数字を作り、各数字を四則演算して結果が100になる組み合わせが無ければラッキーとなる。
括弧を追加して演算子の優先順位を指定できる。ただし、数字の順番は変更してはならない。
引数は、6桁の数字が文字列で与えられる。
戻り値は、ラッキーナンバーならTrue、でなければFalseを返す。
例題：
checkio('000000') == True checkio('707409') == True checkio('595347') == False # (5 + ((9 * 5) + (3 + 47))) = 100 checkio('271353') == False # (2 - (7 * (((1 / 3) - 5) * 3))) = 100
ちょっと前のGoogleのCMで見た、「1,1,5,8で10を作る」みたいな問題だなぁ。
Nexus 7 : 10 Puzzle - YouTube
どうやって解く？
まず、四則演算の前に、6桁の数字を分割する必要がある。例えば、123456 なら 1,2,3,4,5,6、123,45,6、12,34,56、、、などなど多くの分割パターンがある。
数字を分割したら、次は演算子（＋－＊／）の組み合わせを考える。12,34,56 と分割したなら、 12+34+56、12*34/56、12-34/56、12*34-56、、、などがあり、さらに演算子の優先順位も指定できるので、(12*34)-56 と 12*(34-56) とは別パターンとなる。なんだか、ものすごい組み合わせになりそうだ。
まず6桁の数字を分割する方法は、「1,2,3,4,5,6」の5つのコンマがあり、それぞれのコンマを消すか残すかだと考えればいい。全部で 25 の組み合わせがある。すべての分割パターンを求める関数がこちら。
from itertools import product def get_all_groups(size): def get_range(split): split_index = [i + 1 for i in range(size - 1) if split[i]] return zip([0] + split_index, split_index + [size]) # list of (start,stop) return [get_range(split) for split in product([True, False], repeat=size - 1)]
sizeには数字の桁数(=6)を指定する。これで、(開始index,終了index)のリストが得られるので、
numbers_list = [[int(data[i:j]) for i, j in g] for g in get_all_groups(6)]
とすれば、すべての分割パターンの数字リストが取得できる。
次に、数字を1つ選び、右隣の数字と四則演算を行って、2つの数字を1つにまとめる。DFSで結果が100になるまで続ける。
四則演算は、operatorモジュールのadd,sub,mul,truedivを使った。割り算の場合だけ0除算エラーにならないように事前に右辺が0かどうかをチェックしている。
どういう計算式で100になったかを知りたいので、数字の演算と同時に、計算式(expr)も作成するようにした。
from operator import add, sub, mul, truediv def checkio(data): numbers_list = [[int(data[i:j]) for i, j in g] for g in get_all_groups(6)] stack = [([int(s) for s in numbers], [s for s in numbers]) for numbers in numbers_list] while stack: numbers, expr = stack.pop() if len(numbers) == 1: if numbers[0] == 100: print('{} -> {} = 100'.format(data, expr[0])) return False else: for i in range(len(numbers) - 1): for func, op in [(add, '+'), (sub, '-'), (mul, '*'), (truediv, '/')]: if numbers[i + 1] == 0 and func == truediv: # div by zero continue new_numbers, new_expr = numbers[:], expr[:] new_numbers[i:i + 2] = [func(numbers[i], numbers[i + 1])] new_expr[i:i + 2] = ['({}{}{})'.format(expr[i], op, expr[i + 1])] stack.append((new_numbers, new_expr)) return True
これで、あれこれ試すと、
012345 -> ((01+(23-4))*5) = 100 123456 -> (1+((2+(3+4))*(5+6))) = 100 314159 -> ((31*4)-(15+9)) = 100
のように表示される。面白いなぁ。
まとめ
実際の解答には計算式は必要ないので、不要な部分を削除したのがこちら。
from itertools import product from operator import add, sub, mul, truediv def get_all_groups(size): def get_range(split): split_index = [i + 1 for i in range(size - 1) if split[i]] return zip([0] + split_index, split_index + [size]) # list of (start,stop) return [get_range(split) for split in product([True, False], repeat=size - 1)] def checkio(data): numbers_list = [[int(data[i:j]) for i, j in g] for g in get_all_groups(6)] while numbers_list: numbers = numbers_list.pop() if len(numbers) == 1: if numbers[0] == 100: return False else: for i in range(len(numbers) - 1): for func in [add, sub, mul, truediv]: if numbers[i + 1] == 0 and func == truediv: # div by zero continue new_numbers = numbers[:] new_numbers[i:i + 2] = [func(numbers[i], numbers[i + 1])] numbers_list.append(new_numbers) return True
http://www.checkio.org/mission/mathematically-lucky-tickets/publications/natsuki/python-3/first/
公開後に見直してみると、ちょっとわかりづらいので、一部修正。
def get_groups(data): for split in product([True, False], repeat=5): split_index = [i + 1 for i in range(5) if split[i]] ranges = zip([0] + split_index, split_index + [6]) # list of (start,stop) yield [int(data[i:j]) for i, j in ranges] def checkio(data): numbers_list = list(get_groups(data)) …
この方がわかりやすかったかな。
