|
from math import sqrt |
|
from time import perf_counter |
|
|
|
class Expression: |
|
def __init__(self, value, expression_str, n_count): |
|
self.value = value |
|
self.expression_str = expression_str |
|
self.n_count = n_count |
|
|
|
def __repr__(self): |
|
return "%s = %s" % (self.value, self.expression_str) |
|
|
|
class Operator: |
|
def __init__(self, operation, str_func): |
|
self.operation = operation |
|
self.str_func = str_func |
|
|
|
def __call__(self, *args): |
|
try: |
|
return Expression( |
|
self.operation(*[float(a.value) for a in args]), |
|
self.str_func(*[a.expression_str for a in args]), |
|
sum(a.n_count for a in args), |
|
) |
|
except Exception as e: |
|
return None |
|
|
|
class Solver: |
|
def __init__(self, n, max_intermediate_value=1e10): |
|
# Initialise generic private attributes |
|
self._n = n |
|
self._max_intermediate_value = max_intermediate_value |
|
self._next_n_length = 2 |
|
n_expression = Expression(n, str(n), 1) |
|
self._value_dict = {n: n_expression} |
|
self._new_value_list = [n_expression] |
|
self._old_value_list = [] |
|
|
|
# Initialise factorial dictionary |
|
self._factorial_dict = {1: 1} |
|
f = 1 |
|
while self._factorial_dict[f] <= max_intermediate_value: |
|
f += 1 |
|
self._factorial_dict[f] = f * self._factorial_dict[f - 1] |
|
|
|
# Initialise lists of operations |
|
self._commutative_op_list = [ |
|
Operator(lambda a, b: a + b, lambda a, b: "(%s) + (%s)" % (a, b)), |
|
Operator(lambda a, b: a * b, lambda a, b: "(%s) * (%s)" % (a, b)), |
|
] |
|
self._non_commutative_op_list = [ |
|
Operator(lambda a, b: a - b, lambda a, b: "(%s) - (%s)" % (a, b)), |
|
Operator(lambda a, b: a / b, lambda a, b: "(%s) / (%s)" % (a, b)), |
|
Operator(lambda a, b: a ** b, lambda a, b: "(%s) ^ (%s)" % (a, b)), |
|
] |
|
self._unary_op_list = [ |
|
Operator(lambda a: sqrt(a), lambda a: "sqrt(%s)" % a), |
|
Operator(lambda a: self._factorial_dict[a], lambda a: "(%s)!" % a), |
|
] |
|
|
|
def solve(self, target, target_n_count=10): |
|
self._target = target |
|
self._target_n_count = target_n_count |
|
while True: |
|
print( |
|
"Step = %i, dictionary size = %i, with %i new expressions" |
|
% ( |
|
self._next_n_length, |
|
len(self._value_dict), |
|
len(self._new_value_list), |
|
), |
|
end="", |
|
) |
|
self._temp_new_value_dict = dict() |
|
# Add next multi-n string to appropriate iterables |
|
multi_n_string = str(self._n) * self._next_n_length |
|
multi_n_expression = Expression( |
|
int(multi_n_string), |
|
multi_n_string, |
|
self._next_n_length, |
|
) |
|
self._validate(multi_n_expression) |
|
self._next_n_length += 1 |
|
for op in self._unary_op_list: |
|
print(".", end="", flush=True) |
|
for e in self._new_value_list: |
|
self._validate(op(e)) |
|
for op in self._commutative_op_list: |
|
print(".", end="", flush=True) |
|
for i, e in enumerate(self._new_value_list): |
|
for j, e2 in enumerate(self._new_value_list): |
|
if j >= i: |
|
self._validate(op(e, e2)) |
|
for e2 in self._old_value_list: |
|
self._validate(op(e, e2)) |
|
for op in self._non_commutative_op_list: |
|
print(".", end="", flush=True) |
|
for e in self._new_value_list: |
|
for e2 in self._new_value_list: |
|
self._validate(op(e, e2)) |
|
for e2 in self._old_value_list: |
|
self._validate(op(e, e2)) |
|
self._validate(op(e2, e)) |
|
|
|
print() |
|
|
|
self._old_value_list += self._new_value_list |
|
self._new_value_list = list(self._temp_new_value_dict.values()) |
|
|
|
if len(self._new_value_list) == 0: |
|
return None |
|
|
|
if target in self._value_dict: |
|
if self._value_dict[target].n_count <= target_n_count: |
|
return self._value_dict[target].n_count |
|
|
|
|
|
def _validate(self, expression): |
|
if expression is None: |
|
return |
|
value = expression.value |
|
is_valid = ( |
|
not isinstance(value, complex) |
|
and (value > 0) |
|
and (value <= self._max_intermediate_value) |
|
and (value == int(value)) # Sometimes remove this, EG for 64 # 2 |
|
and (expression.n_count <= self._target_n_count) |
|
) |
|
if is_valid: |
|
value = int(value) |
|
if value in self._value_dict: |
|
previous_n_count = self._value_dict[value].n_count |
|
if expression.n_count >= previous_n_count: |
|
return |
|
self._value_dict[value] = expression |
|
self._temp_new_value_dict[value] = expression |
|
|
|
if value == self._target: |
|
print( |
|
"\nFound target with %i \"n\"s! %s" |
|
% (expression.n_count, expression) |
|
) |
|
|
|
if __name__ == "__main__": |
|
t_start = perf_counter() |
|
|
|
Solver(n=2, max_intermediate_value=1e6).solve(target=64, target_n_count=3) |
|
|
|
print("Script finished in %.3f secs" % (perf_counter() - t_start)) |
