Generate a valid equation using user-specified numbers

Question

This is based on a game one of my math teachers used to play in middle school. He would write 5 random one-digit numbers on the board, and then a random two-digit number. We would try to create an equation that used all 5 of the one-digit numbers to yield the two-digit number. Here are some examples with solutions to explain this better:

Input:           Solution:
7 5 4 8 4 34     5*8-7+4/4 = 34
3 1 5 7 6 54     (7+3)*6-5-1 = 54
3 9 2 1 6 87     9*(2+1)*3+6 = 87
2 1 6 9 7 16     (9-7+6*1)*2 = 16
2 4 5 8 6 96     8*(5+6)+2*4 = 96
3 8 4 5 4 49     8*(4+4)-3*5 = 49

This challenge is to write a program that can generate such equations for a given input. The input can be provided either via the command line or via a prompt. The 5 one-digit numbers will always be entered first (in no particular order), followed by the two-digit number. The program will then print out a solution equation it finds; you do not have to handle situations where there is no solution. The function must be capable of using the following operations in the equation: addition, subtraction, multiplication, and division. If you would like to allow additional basic operations, that's fine as long as they remain in the spirit of the challenge (negation, exponentiation, and modulus would be nice additions). Order of operations follows the standard math rules, so parenthesis will be needed for grouping. The program must take less than a minute to run on a modern computer.

Programs will be scored based on code length (including required whitespace). Note: division must be exact, not rounded or truncated to nearest integer.

Answer 1

Python 2.7 (284), Python 3.x (253)

from __future__ import division #(Remove for Python 3.x)
from itertools import *
a=raw_input().split()
for i in permutations(a[:-1],5):
 for j in product('+-*/',repeat=5):
  for k,l in combinations(range(1,12,2),2):
   d=''.join(sum(zip(i,j),()))[:-1];d='('+d[:l]+')'+d[l:]
   if eval(d)==int(a[-1]):print d;b

It gives an error (calling unknown function b) on solution.

Basically, it's a gigantic brute force. It takes in the input, splits it by its spaces (1 2 -> [1,2]), and then permutes through that list. With every permutation, it will iterate through all possible strings of length 5 using the characters +-*/. With each of those iterations, it will generate the combinations of length 2 of the list [1,3,5,7,9,11], interweave the permutation and the string together (12345 *-/+- -> 1*2-3/4+5-), and put in the parentheses. Finally, it will evaluate it, and if the answer and equation are true, then it prints the equation and stops.

This is horribly inefficient, about O(n!/(n-5)!)=O(n^5), but it runs in a reasonable time for the test inputs.

Answer 2

Scala 368:

The 2nd g=-Line is more easy to test, the first is flexible to take command arguments, and both are of equal length, so I only count from the second one - remove it to do args passing:

val g=(args.map(_.toDouble))
val g=Array(3,9,2, 1, 6, 87)
val k="+*/-DQ"
val i=(0 to 5)
val f:Seq[(Double,Double)=>Double]=Seq(_+_,_*_,_/_,_-_,(a,b)=>b-a,(a,b)=>b/a)
val h=g.init.permutations;
for(j<-h;o<-i;p<-i;q<-i;r<-i;z=try{f(r)(f(q)(f(p)(f(o)(j(0),j(1)),j(2)),j(3)),j(4))}catch{case _ => 0}
if(z==g(5)))printf("(((%d%c%d)%c%d)%c%d)%c%d=%d\n",j(0),k(o),j(1),k(p),j(2),k(q),j(3),k(r),j(4),g(5))

Sample output (you might have a question right now - just a moment):

(((5+7)/1)+6)*3=54
(((5-7)D1)*6)*3=54
(((5D7)+1)*6)*3=54
(((5+7)+6)Q1)Q3=54

What about this 5D7 thing? D1? Is it hex? There is Q1, Q3 - what's that.

Sir_Lagsalot allowed new basic operations in the spirit of the challenge, and yes, these are basic operations, Delta and Quotient.

They are different from a/b and a-b in that aQb means b/a and aDb means b-a. Let's call it the Ukrainian notation.

So

(((5-7)D1)*6)*3=54

means

((1-(5-7))*6)*3=54
 (1-(-2))*6*3
   3*6*3 = 18*3=54

To the more interesting question of the how and why: In the beginning I got mad about the possibilities to place the parentheses, and whether (a+b)-c = a+b-c = (a+b-c) = ((a+b)-c) = (b+a)-c and so on. You can get mad over this question, but if you write down the possible parenthesis combinations, you sometimes throw away the scratch sheet and face the fact: You always perform 4 operations between 5 values, and you always start with one of them. If the pattern is always (((_x_)x_)x_)x_ ?= _ (x being one of the 4 operators) and allow the opposite direction ( x b) and (b x a), you addressed every possibility.

Now for a+b and a*b we don't need no opposite direction, they are commutative. So I invented the D and Q operator, which just switch the direction. I now have 2 operators more, but don't need to switch direction. Well - it is done in the function Sequence:

 (a,b)=>b-a,(a,b)=>b/a

My for-comprehension takes the values from the Array g, and distributes them on a to e, then I pick 4 indexes to pick the function and later the (only by index) associated operator symbol. I have to catch div/0 errors, since subtraction can lead to zeros, while the sample input data doesn't contain a 0.