from fractions import Fraction
CACHE = {}
class Expression:
def __init__(self, val, path=None):
self.val = val
self.path = str(val) if path is None else path
def __eq__(self, other):
return self.val.__eq__(other.val)
def __ne__(self, other):
return self.val.__ne__(other.val)
def __hash__(self):
return self.val.__hash__()
def __neg__(self):
return Expression(-self.val, f'-{self.path}')
def __add__(self, other):
return Expression(self.val + other.val, f'({self.path}+{other.path})')
def __sub__(self, other):
return Expression(self.val - other.val, f'({self.path}-{other.path})')
def __mul__(self, other):
return Expression(self.val * other.val, f'({self.path}*{other.path})')
def __truediv__(self, other):
return Expression(self.val / other.val, f'({self.path}/{other.path})')
def __floordiv__(self, other):
return Expression(self.val // other.val, f'({self.path}//{other.path})')
def __str__(self):
return f'{self.val} = {self.path}'
def __lt__(self, other):
return self.val < other.val
def __bool__(self):
return self.val.__bool__()
def generate_split(lst):
for i in range(2**(len(lst) - 1), 2**len(lst)-1):
left = []
right = []
for el in lst:
if i%2:
left.append(el)
else:
right.append(el)
i //= 2
yield tuple(sorted(left)), tuple(sorted(right))
def product(set1, set2):
ret = set()
for n1 in set1:
for n2 in set2:
ret.update({n1+n2, n1-n2, n2-n1, -n1-n2, n1*n2})
if n1:
ret.add(n2/n1)
if n2:
ret.add(n1/n2)
return ret
def get_results(lst):
if len(lst) < 1:
return set()
if len(lst) == 1:
return set(lst)
lst = tuple(sorted(lst))
if lst in CACHE:
return CACHE[lst]
ret = set()
for l, r in generate_split(lst):
ret.update(product(get_results(l), get_results(r)))
CACHE[lst] = ret
return ret
if __name__ == '__main__':
inp = [Expression(Fraction(el)) for el in [1, 8, 9, 0, 6, 0]]
s = get_results(inp)
print(*(str(el) for el in sorted(s)), sep='\n')
print(len(s))
print(100 in s)
