Instantly share code, notes, and snippets.

@davidlyness /digits.py Secret
Created Jun 19, 2016

Embed
What would you like to do?
# coding=utf-8
"""
This script is used to calculate properties of strings containing binary operators.
See https://lyness.io/experimenting-with-bracketing-and-binary-operators for more details.
"""
import itertools
def all_expressions(generic_expression, operation_combinations):
"""
Merges a source expression and combinations of binary operators to generate a list of all possible expressions.
@param ((str,)) operation_combinations: all combinations of binary operators to consider
@param str generic_expression: source expression with placeholder binary operators
@rtype: (str,)
"""
expression_combinations = []
for combination in operation_combinations:
expression_combinations.append(generic_expression.format(*combination))
return expression_combinations
def all_bracketings(expr):
"""
Generates all possible permutations of parentheses for an expression.
@param str expr: the non-bracketed source expression
@rtype: str
"""
if len(expr) == 1:
yield expr
else:
for i in range(1, len(expr), 2):
for left_expr in all_bracketings(expr[:i]):
for right_expr in all_bracketings(expr[i + 1:]):
yield "({}{}{})".format(left_expr, expr[i], right_expr)
def calculate_expressions(min_digits, max_digits, operations):
"""Perform all calculations with the given operations and in the range of digits specified.
@param (str,) operations: the operations considered as valid binary operators
@param int min_digits: the minimum number of digits to consider
@param int max_digits: the maximum number of digits to consider
"""
operations_string = "".join(operations)
print("\t".join(["Digit", "Operations", "Num operations", "Num digits", "Max value", "Max expression", "Min value",
"Min expression", "Smallest non-zero value", "Smallest non-zero expression", "Total expressions",
"Total valid expressions"]))
for num_digits in range(min_digits, max_digits + 1):
for digit in range(0, 10):
operation_iterable = itertools.product(*[operations] * (num_digits - 1))
operation_combinations = []
min_value = None
min_expression = None
max_value = None
max_expression = None
smallest_value = None
smallest_expression = None
expression_count = 0
valid_expression_count = 0
template = " ".join(str(digit) * num_digits)
for operation in operation_iterable:
operation_combinations.append(operation)
for bracketed_expression in all_bracketings(template):
for expression in all_expressions(bracketed_expression.replace(" ", "{}"), operation_combinations):
try:
value = eval(expression) # eval ONLY used here because we completely trust the input!
if max_value is None or value > max_value:
max_value = value
max_expression = expression
if min_value is None or value < min_value:
min_value = value
min_expression = expression
if value != 0 and (smallest_value is None or abs(value) < smallest_value):
smallest_value = abs(value)
smallest_expression = expression
valid_expression_count += 1
except ZeroDivisionError:
pass
expression_count += 1
print("\t".join([str(digit), operations_string, str(len(operations)), str(num_digits),
str(max_value), max_expression, str(min_value), min_expression, str(smallest_value),
str(smallest_expression), str(expression_count), str(valid_expression_count)]))
if __name__ == "__main__":
min_num_digits = 1
max_num_digits = 8
operation_set = ["+", "-", "*", "/"]
calculate_expressions(min_num_digits, max_num_digits, operation_set)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment