Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
(Print version) Recursively generate parenthesization on split digits and operations solution in Clear category for Mathematically Lucky Tickets by Phil15
from itertools import product, combinations
# Manage operations on strings and integers.
from math import inf # Manage the division by zero.
add = lambda a, b: f"({a} + {b})" if type(a)==str else a + b
sub = lambda a, b: f"({a} - {b})" if type(a)==str else a - b
mul = lambda a, b: f"({a} * {b})" if type(a)==str else a * b
div = lambda a, b: f"({a} / {b})" if type(a)==str else (a / b if b!=0 else inf)
def parenthesizations(seq, op):
"""
Generate all possibles parenthesizations in SEQuence with OPerations
Work with all possibles types, if operations allow it.
>>> list(parenthesizations(['1','2','3'], [add, mul])) # 1+2*3 with ()
['1 + (2 * 3)', '(1 + 2) * 3']
"""
assert len(op) == len(seq) - 1, "Not the good number of operations"
if len(seq)==1:
yield seq[0]
else:
for i in range(1, len(seq)):
seq_left, seq_right = seq[:i], seq[i:]
op_left, op_middle, op_right = op[:i-1], op[i-1], op[i:]
for left in parenthesizations(seq_left, op_left):
for right in parenthesizations(seq_right, op_right):
yield op_middle(left, right)
def split(digits, indexes):
"""
Split digits string with indexes.
>>> split('012345', [2, 5])
[('01', 1), ('234', 234), ('5', 5)]
"""
return [(digits[start:end], int(digits[start:end]))
for (start, end) in zip([0] + indexes, indexes + [len(digits)])]
def checkio(digits, target=100):
"""Say if digits is lucky.
It's lucky if it can't be split and evaluated (with + - * /) to target.
Print the result."""
N = len(digits) # 6 here
# 1) Split digits into k parts. Descending k for complexity reason.
for k in range(N, 0, -1):
for indexes in combinations(range(1, N), k-1):
strs, ints = zip(*split(digits, list(indexes)))
# 2) Look all possibles operations.
for signs in product((add, sub, mul, div), repeat=k-1):
# 3) Look all possible parenthesizations.
for expr, result in zip(parenthesizations(strs, signs),
parenthesizations(ints, signs)):
if result==target:
print(f"{digits} is not lucky: {expr} = {target}")
return False
print(f"{digits} is lucky")
return True
Aug. 18, 2018
Comments:
