テンパズルを解く
テンパズルを解くプログラムをPythonで書いた。
C:\>make10.py 1 1 5 8 8/(1-(1/5)) time: 0.0699999332428 s
のように使う。CPython 2.6で動作を確認した。
仕組みはいたって簡単で、後置記法の式を生成し計算して演算結果が10なら挿入記法に変換して表示するというもの。
そんなに複雑なことはしていないので詳しくは読めば分かる。
from __future__ import division
としているのがミソか。
ソースコードを以下に示す。
#!/usr/bin/env python # coding: utf-8 from __future__ import division def post2in(expr): stack = [] for elem in expr: if elem in ('+', '-', '*', '/'): top = stack.pop() snd = stack.pop() stack.append('('+snd+elem+top+')') else: stack.append(str(elem)) return stack.pop()[1:-1] def gen_expr(nums, size, expr): if size - 1 == len(nums) == 0: yield expr else: result = [] if size >= 2: for oper in ('+', '-', '*', '/'): for elem in gen_expr(nums[:], size - 1, expr+[oper]): yield elem for num in set(nums): copy = nums[:] copy.remove(num) for elem in gen_expr(copy, size + 1, expr+[num]): yield elem def calc_postfix_notation(expr): stack = [] for elem in expr: if elem == '+': stack.append(stack.pop() + stack.pop()) elif elem == '-': stack.append(-stack.pop() + stack.pop()) elif elem == '*': stack.append(stack.pop() * stack.pop()) elif elem == '/': temp = stack.pop() if temp == 0: # division by zero return 0 stack.append(stack.pop() / temp) else: stack.append(elem) return stack.pop() def main(): from time import time from sys import argv t = time() for expr in gen_expr(map(int, argv[1:]), 0, []): if calc_postfix_notation(expr) == 10: print(post2in(expr)) print 'time:', time() - t, 's' if __name__ == '__main__': main()