Skip to content

Instantly share code, notes, and snippets.

@nishio
Created April 20, 2011 04:13
Show Gist options
  • Save nishio/930325 to your computer and use it in GitHub Desktop.
Save nishio/930325 to your computer and use it in GitHub Desktop.
# -*- coding: utf-8 -*-
nums = [1, 1, 7, 7]
from operator import add, sub, mul, div
ops = {"*": mul, "+": add, "-": sub, "/": div}
def split(nums):
N = len(nums)
if nums:
head = nums[0]
if N > 1:
for n1, n2 in split(nums[1:]):
yield n1, [head] + n2
yield [head] + n1, n2
else:
yield [], [head]
yield [head], []
eqs = {}
for n in nums:
eqs[(n, )] = {}
eqs[(n, )][float(n)] = n
def solve(nums):
"""
与えられたnumsと加減乗除の組み合わせでできる式を返す
"""
if len(nums) == 1:
return eqs[tuple(nums)]
key = tuple(sorted(nums))
if eqs.has_key(key):
return eqs[key] # memoize
result = {}
for n1, n2 in split(nums):
if not n1 or not n2: continue # []の場合はスキップ
eq_lhs = solve(n1)
eq_rhs = solve(n2)
for lhs in eq_lhs:
for rhs in eq_rhs:
for op in ops:
try:
value = ops[op](lhs, rhs)
except ZeroDivisionError:
continue
result[value] = (op, eq_lhs[lhs], eq_rhs[rhs])
eqs[key] = result
return result
for line in sorted(solve(nums).items()):
print line
"""
output:
...
(0.12244897959183675, ('/', ('-', 1, ('/', 1, 7)), 7))
(0.125, ('-', 1, ('/', 7, ('+', 7, 1))))
(0.13999999999999999, ('/', 1, ('+', ('/', 1, 7), 7)))
(0.14285714285714279, ('-', ('/', ('+', 7, 1), 7), 1))
(0.14285714285714285, ('/', ('+', 1, 1), ('+', 7, 7)))
...
"""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment