How to brute force arithmetic puzzle?

Question

A friend shared this puzzle:

How to make 21 from 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.

I eventually solved it on paper—two days later. No doubt a computer could brute force all solutions in a second.

How though? I tried generating all strings a.b.c.d inserting the numbers for letters and operations for dots, but it missed my solution.

Bonus puzzles:

How to make 11 from 1,5,6,7?
How to make 16 from 1,5,6,7?

And what would be the answer for 21? (I can't seem to find it) — AnT stands with Russia, Mar 30 '15 at 18:55
I'm fairly sure that [this python code](http://ideone.com/aTiMHK) implements AnT's algorithm. And I find no results for `16` or `21`. — Bill Lynch, Mar 30 '15 at 18:55
@BillLynch By always putting `value` into the left, it's missing, e.g., `1-(5+6)`. — Teepeemm, Mar 30 '15 at 19:07
This could be considered as a duplicate of http://stackoverflow.com/questions/21461084/how-to-find-the-exact-set-of-operations-for-a-specific-number (although the details may vary, of course) — Marco13, Mar 31 '15 at 14:32

AnT stands with Russia · Accepted Answer · 2015-03-30T19:00:27.687

An obvious approach would be the folllwing:

You start with a vector S of four numbers: S = ( 1, 5, 6, 7 )
Pick 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 (take care to avoid division by zero and verify exact division, if the problem requires it)
Include c into S, thus obtaining S'
Continue from step 1, now using S' in place of S

Brute-force branching is performed at step 2 (selecting two numbers), and step 3 (selecting operation). The cycle should be repeated until S reduces to only 1 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, at which point you can either terminate, or continue branching to search for other solutions.

Cool. That's exactly the algorithm I ended up writing. You explain it clearly. https://gist.github.com/hickford/56cc7e2b0c55c140a976 — Colonel Panic, Mar 31 '15 at 10:07

score 2 · Answer 2 · answered Mar 31 '15 at 10:18

Here's the "pop two, combine, recurse" algorithm as suggested by AnT, coded in Python. The hardest part was assembling the expressions after the 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 to the 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)

How to brute force arithmetic puzzle?

2 Answers2

Linked