import itertools
def test(expression, n):
"""Given an expression, returns a tuple of all possible results"""
results = []
for input_ in itertools.product([0, 1], repeat=n):
for i in range(n):
locals()[chr(ord("A")+i)] = input_[i]
results.append(int(eval(expression)))
return tuple(results)
def solve(n):
assert n <= 26
solution_dict = {}
for expression in ["0", "1"] + [chr(ord("A")+x) for x in range(n)]:
solution_dict[test(expression, n)] = expression
while len(solution_dict) < 2**(2**n):
update_dict = {}
for key1 in solution_dict:
expression1 = solution_dict[key1]
if len(expression1) > 1:
expression1 = "({})".format(expression1)
for key2 in solution_dict:
expression2 = solution_dict[key2]
if len(expression2) > 1:
expression2 = "({})".format(expression2)
new_expression = "{}<{}".format(expression1, expression2)
results = test(new_expression, n)
if results not in solution_dict:
update_dict[results] = new_expression
elif len(new_expression) < len(solution_dict[results]):
update_dict[results] = new_expression
solution_dict.update(update_dict)
for result in sorted(solution_dict):
print(solution_dict[result])
solve(n=2)
aW1wb3J0IGl0ZXJ0b29scwoKZGVmIHRlc3QoZXhwcmVzc2lvbiwgbik6CiAgICAiIiJHaXZlbiBhbiBleHByZXNzaW9uLCByZXR1cm5zIGEgdHVwbGUgb2YgYWxsIHBvc3NpYmxlIHJlc3VsdHMiIiIKCiAgICByZXN1bHRzID0gW10KCiAgICBmb3IgaW5wdXRfIGluIGl0ZXJ0b29scy5wcm9kdWN0KFswLCAxXSwgcmVwZWF0PW4pOgogICAgICAgIGZvciBpIGluIHJhbmdlKG4pOgogICAgICAgICAgICBsb2NhbHMoKVtjaHIob3JkKCJBIikraSldID0gaW5wdXRfW2ldCiAgICAgICAgICAgIAogICAgICAgIHJlc3VsdHMuYXBwZW5kKGludChldmFsKGV4cHJlc3Npb24pKSkKCiAgICByZXR1cm4gdHVwbGUocmVzdWx0cykKCmRlZiBzb2x2ZShuKToKICAgIGFzc2VydCBuIDw9IDI2CiAgICAKICAgIHNvbHV0aW9uX2RpY3QgPSB7fQoKICAgIGZvciBleHByZXNzaW9uIGluIFsiMCIsICIxIl0gKyBbY2hyKG9yZCgiQSIpK3gpIGZvciB4IGluIHJhbmdlKG4pXToKICAgICAgICBzb2x1dGlvbl9kaWN0W3Rlc3QoZXhwcmVzc2lvbiwgbildID0gZXhwcmVzc2lvbgoKICAgIHdoaWxlIGxlbihzb2x1dGlvbl9kaWN0KSA8IDIqKigyKipuKToKICAgICAgICB1cGRhdGVfZGljdCA9IHt9CiAgICAgICAgCiAgICAgICAgZm9yIGtleTEgaW4gc29sdXRpb25fZGljdDoKICAgICAgICAgICAgZXhwcmVzc2lvbjEgPSBzb2x1dGlvbl9kaWN0W2tleTFdCiAgICAgICAgICAgIAogICAgICAgICAgICBpZiBsZW4oZXhwcmVzc2lvbjEpID4gMToKICAgICAgICAgICAgICAgIGV4cHJlc3Npb24xID0gIih7fSkiLmZvcm1hdChleHByZXNzaW9uMSkKICAgICAgICAgICAgICAgIAogICAgICAgICAgICBmb3Iga2V5MiBpbiBzb2x1dGlvbl9kaWN0OgogICAgICAgICAgICAgICAgZXhwcmVzc2lvbjIgPSBzb2x1dGlvbl9kaWN0W2tleTJdCiAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgIGlmIGxlbihleHByZXNzaW9uMikgPiAxOgogICAgICAgICAgICAgICAgICAgIGV4cHJlc3Npb24yID0gIih7fSkiLmZvcm1hdChleHByZXNzaW9uMikKCiAgICAgICAgICAgICAgICBuZXdfZXhwcmVzc2lvbiA9ICJ7fTx7fSIuZm9ybWF0KGV4cHJlc3Npb24xLCBleHByZXNzaW9uMikKICAgICAgICAgICAgICAgIHJlc3VsdHMgPSB0ZXN0KG5ld19leHByZXNzaW9uLCBuKQoKICAgICAgICAgICAgICAgIGlmIHJlc3VsdHMgbm90IGluIHNvbHV0aW9uX2RpY3Q6CiAgICAgICAgICAgICAgICAgICAgdXBkYXRlX2RpY3RbcmVzdWx0c10gPSBuZXdfZXhwcmVzc2lvbgoKICAgICAgICAgICAgICAgIGVsaWYgbGVuKG5ld19leHByZXNzaW9uKSA8IGxlbihzb2x1dGlvbl9kaWN0W3Jlc3VsdHNdKToKICAgICAgICAgICAgICAgICAgICB1cGRhdGVfZGljdFtyZXN1bHRzXSA9IG5ld19leHByZXNzaW9uCgogICAgICAgIHNvbHV0aW9uX2RpY3QudXBkYXRlKHVwZGF0ZV9kaWN0KQoKICAgIGZvciByZXN1bHQgaW4gc29ydGVkKHNvbHV0aW9uX2RpY3QpOgogICAgICAgIHByaW50KHNvbHV0aW9uX2RpY3RbcmVzdWx0XSkKCnNvbHZlKG49Mik=