How to execute an arithmetic puzzle with brute force?

Question

A friend shared this puzzle:

How to make 21 of the numbers 1, 5, 6, 7?

You can use the operations of addition, subtraction, multiplication and division, as well as brackets. You must use each number once.

In the end, I decided it on paper - two days later. Without a doubt, a computer could go over all the solutions in a second.

How so? I tried to generate all abcd lines by inserting numbers for letters and operations for points, but this missed my solution.

---

Bonus puzzles:

• How to make 11 of 1,5,6,7?
• How to make 16 of 1,5,6,7?

Answer 1

An obvious approach would be the following:

• You start with the vector S four numbers: S = ( 1, 5, 6, 7 )
• Choose any two numbers a and b from S , remove them from S
• Apply an arbitrary arithmetic operation to a and b , thus obtaining a new number c (try to avoid division by zero and check the exact division if it requires it)
• Include c in S , getting S'
• Continue from step 1, now using S' instead of S

The deployment of forced force is performed in step 2 (selection of two numbers) and step 3 (selection of operation). The cycle should be repeated until S decreases to only one element, which is the result for this particular brute force branch.

Brackets are not used explicitly, but they are present implicitly.

If one branch ends with 21 in S , you have a solution, after which you can either end or continue branching to look for other solutions.

Answer 2

Here's the "pop two, comb, recurse" algorithm proposed by AnT, encoded in Python. The hardest part is assembling expressions after recursion. I used find-and-replace.

 #!python import operator import itertools from fractions import Fraction operations = dict() operations['+'] = operator.add operations['-'] = operator.sub operations['/'] = operator.truediv operations['*'] = operator.mul def solve(target, numbers): """List ways to make target from numbers.""" numbers = [Fraction(x) for x in numbers] return solve_inner(target, numbers) def solve_inner(target, numbers): if len(numbers) == 1: if numbers[0] == target: yield str(target) return # combine a pair of numbers with an operation, then recurse for a,b in itertools.permutations(numbers, 2): for symbol, operation in operations.items(): try: product = operation(a,b) except ZeroDivisionError: continue subnumbers = list(numbers) subnumbers.remove(a) subnumbers.remove(b) subnumbers.append(product) for solution in solve_inner(target, subnumbers): # expand product (but only once) yield solution.replace(str(product), "({0}{1}{2})".format(a, symbol, b), 1) if __name__ == "__main__": numbers = [1, 5, 6, 7] target = 21 solutions = solve(target, numbers) for solution in solutions: print("{0}={1}".format(target, solution)) 

Solutions for three puzzles:

 >>> solve(21,[1,5,6,7]) 6/(1-(5/7)) >>> solve(11,[1,5,6,7]) (6*(7-5))-1 ((7-5)*6)-1 >>> solve(16,[1,5,6,7]) [] 

(The third puzzle is impossible)