# generate a valid equation using specified operators

A twist on a recently asked question, you are given a list of operators and a result and you need to find integers which, when operated on by those operators, generate the result.

Example 1

input

+ + * / 13


possible output

4 8 2 2 4


which means that 4 + 8 + 2 * 2 / 4 = 13.

More specifically, you are given a sequence of N operators (between 1 and 5 inclusive) and an integer result, space separated. You must print N+1 integers, space separated, in the range 1 through 9, inclusive, that when alternated with the operators produce the result.

The operators are +,-,*,/. They have the natural precedence order (* and / before + and -, left associative). Divides must be integral divides, a divide with a fractional result is not allowed. Operators must appear in the order given.

Most problems will have more than one solution. Printing any of them, or any subset of them, is fine. If there is no solution, print NO SOLUTION.

Example 2

input

/ + - - 16


output

9 1 9 1 1


Example 3

input

+ 5


output

1 4
2 3
3 2
4 1


(or any nonempty subset of those lines)

Example 4

input

+ + 30


output

NO SOLUTION


Example 5

input

/ + / 3


output

6 3 5 5


note that 3 2 3 2 is not a solution, as 3/2+3/2=3 is true but the individual divides have fractional values.

Standard code golf, shortest answer wins.

• Just to clarify something for me: is 9 2 a valid solution if the input is / 4? – Gareth Jun 22 '12 at 17:00
• @Gareth, no it isn't. That is a divide with a fractional result. – Keith Randall Jun 22 '12 at 19:07
• Any chance the result can be printed without spaces? – Steven Rumbalski Jun 22 '12 at 19:13
• @Steven: nope, format as specified. – Keith Randall Jun 22 '12 at 19:42

## Perl, 129160 151 chars

sub a{my($s,$t,$o)=splice@_,0,3;@_?map{a("$s $_","$t$o$_",@_)}1..9:
$o-eval$t||$o-eval"use integer;$t"||exit say$s}a"","","",split$",<>;say"NO SOLUTION"


Fun with recursion. The program exits upon finding the first valid tuple.

The eval has to be done twice, in and out of integer-only mode, in order to avoid invalid solutions like that given in example 5 in the description.

## Python (197 212 277)

Related question, related answer. Gives the answer and an error if there is one, else prints "NO SOLUTION".

import re,itertools as I
e=eval;a=raw_input().split();c=1;b=len(a)
for i in I.product('123456789',repeat=b):
d=''.join(sum(zip([j+'.'for j in i],a),()))[:3*b-1]
if e(d)==int(a[-1])and all([e(n)%1==0 for n in re.findall('\d./\d.',d)]):print' '.join(i);c=0
print"NO SOLUTION"*c

• This doesn't work for me, e.g. + 5 doesn't work. It doesn't handle / correctly (in either 2.x or 3.x), and I don't want exceptions in my output :) – Keith Randall Jun 22 '12 at 0:38
• Fixed it. Man, that increased the code size. – beary605 Jun 22 '12 at 2:16

### Scala 333

val o=args.init
val e=args.last
val n=(1 to 9)
val i=new bsh.Interpreter
def b(o:Array[String],s:String=""):Boolean={
if(s.isEmpty)n.exists(y=>b(o,s+y))else
if(o.isEmpty){
val r=i.eval(s)
if(r.toString==e){
println(s.replaceAll("[-*+/]"," "))
true}else false}else
n.exists(x=>b(o.tail,s+o(0)+x))
}
b(o)||{println("NO SOLUTION");true}


# Python 2.7, 192 190 184 181 chars

Getting rid of itertools.product saved 3 characters.

s=raw_input().split()
j=' '.join
s[-1]='=='+s[-1]
n=len(s)
x=[j(i)for i in map(str,range(10**(n-1),10**n))if'0'not in i and eval(j(map(j,zip(i,s))))]
print x and x[0]or"NO SOLUTION"