It’s time to do the math

Question

Introduction

This is one of my favorite math puzzles.

Given a digit (say 3) and the number of times to use that digit (say 5), generate 10 expressions which result to 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10 using just +, −, ×, ÷, ^ and √ (root) (brackets are allowed to group operations).

For example:

(3^3 + 3)/(3 + 3) = (33 - 3)/(3 + 3) = 3 + 3/3 + 3/3 = 5

Note that all of the above use five 3’s and the mathematical operations and result to 5. You can also use a 3 before √ to denote a cube root. Same goes for using 4 before √ to denote a fourth root.

Also note that two 3’s can be used to form 33, or three 3’s can be used to form 333 and so on.

Challenge

• You will be given two numbers (both ranging from 1 to 5) as a function argument, STDIN or command line argument.
• The first number denotes which digit to use and the second number denotes the number of times that digit is to be used in the expression.
• Your program should output an array of size 10 (or 10 space-separated numbers) where each element denotes whether a mathematical expression (using just the allowed operators) resulting into the (index + 1) number is possible or not using a truthy/falsy value.

For example, if the input is

1 3

Then the output should be

[1, 1, 1, 0, 0, 0, 0, 0, 0, 1]

because only 1, 2, 3 and 10 can be expressed using three 1’s.

Score

• This is a code-golf so the minimum code length in bytes wins.

Bonus

Print-em-all [−50]

Subtract 50 from your score if the output array elements are equal to the total number of plausible combinations to get the (index + 1) value instead of truthy or falsy values.

For example, if there are only 3 possible combinations of five 3’s which result to 5, then the output array’s 4^th entry should be 3.

Extreme Maths [−100]

Subtract 100 from your score if the output array elements contain at least one of the actual expressions which result to the (index + 1) value.

For example, if using five 3’s, the output array’s 4^th entry can be either (3^3 + 3)/(3 + 3), (33 - 3)/(3 + 3) or 3 + 3/3 + 3/3

Overkilled [−200]

Subtract 200 from your score if the output array elements contain all possible combinations (separated by |). This bonus is added on top of the Extreme Maths bonus, so you get −300 in total.

For example, if using five 3’s, the output array’s 4^th element should be (3^3 + 3)/(3 + 3)|(33 - 3)/(3 + 3)|3 + 3/3 + 3/3

Note: Any two expressions to achieve the same result should be logically different with a different approach in both of them.

For instance, to get 5 using five 3’s, 3 + 3/3 + 3/3 is same as 3/3 + 3 + 3/3 or 3/3 + 3/3 + 3 because the same approach is taken for each of them. (3^3 + 3)/(3 + 3) and (33 - 3)/(3 + 3) differ, as the 30 in the numerator is achieved via different approaches.

UPDATE : After going through all answers, it was found that all answers had imperfections due to edge cases of unary - and √. Thus, missing those edge cases was considered okay as far as completeness of answers is involved.

This is a tough question, but a rather interesting one.

Happy golfing!

Answer 1

Python (imperfect) 493 474 - 300 = 174

There are a fair number of issues with this solution, firstly that it ignores any exponent that is too large (any in which the exponent is greater than 100). I actually don't think this removes any possibilities for inputs less than or equal to 5, but I'm not 100% sure.

Another thing is that it does not consider any unary square roots, as it would get complicated (any solution with any term equal to 0 or 1 would produce an infinite number of solutions). It also does not consider any unary negation (the '-' symbol) for the same reason, as well as the fact that I'm not actually sure if the question asked for it.

I also considered what criteria should decide if two expressions were equivalent, but I couldn't find a way to rigorously define it in a way I found to be intuitive, so (for now at least) I didn't implement anything like that. This does mean that it outputs quite a few results, and it also uses parenthesis in a fairly naive way.

On a side note I think that this might include the longest single line of code I've written, especially before it was fully golfed.

R=range
F=lambda s:lambda a,b:eval(s)
L=lambda D,N:[(int(str(D)*N),str(D)*N)]+[(o(u,v),"(%s%s%s)"%(s,c,t))for p in R(1,N)for u,s in L(D,p)for v,t in L(D,N-p)for c,o in[('+',F('a+b')),('-',F('a-b')),('*',F('a*b')),('/',F("1.*a/b if b else''")),('^',F("''if(a<0 and int(b)!=b)|(a and b<0)|(b>99)else a**b")),('v',F("b**(1./a)if a and(a>=0 or b)and(b>=0 or int(1./a)==1./a)&(1./a<99)else''"))]if o(u,v)!='']
A=L(*input())
for i in R(11):
 for v,s in A:
    if v==i:print i,s[1:-1]

Example: ('v' represents '√')

2,3

0 2*(2-2)
0 2v(2-2)
0 (2-2)*2
0 (2-2)/2
0 (2-2)^2
1 2^(2-2)
1 2-(2/2)
1 2v(2/2)
1 (2/2)^2
2 2v(2+2)
2 2+(2-2)
2 2-(2-2)
2 2v(2*2)
2 2*(2/2)
2 2/(2/2)
2 2^(2/2)
2 2v(2^2)
2 (2+2)-2
2 (2+2)/2
2 (2-2)+2
2 (2*2)-2
2 (2*2)/2
2 (2/2)*2
2 (2/2)v2
2 (2^2)-2
2 (2^2)/2
3 2+(2/2)
3 (2/2)+2
6 2+(2+2)
6 2+(2*2)
6 2+(2^2)
6 (2+2)+2
6 (2*2)+2
6 (2^2)+2
8 2*(2+2)
8 2*(2*2)
8 2*(2^2)
8 (2+2)*2
8 (2*2)*2
8 (2^2)*2

Answer 2

Python 3 – 349 346

r=range
l=lambda s:eval("lambda a"+s)
def T(u,f,X,Y):
    try:return u(f(X,Y))
    except:0
c=l(',x:{x}.union(*[{u(int("1"*a)*x)}|{T(u,f,X,Y)for j in r(1,a)for X in c(j,x)for Y in c(a-j,x)for f in[l(",b:a%sb"%o)for o in{"**"}|set("+-*/")]+[l(",b:a**b**-1")]}for u in[l(":-a")]+[l(":a**.5**%i"%k)for k in r(9)]])')
R=l(",i:[{n+1}<c(i,a)for n in r(10)]")

Here is a rather ungolfed version:

def R(x,i):
    # Unary Operations
    U = [lambda a:-a] + [eval("lambda a:a**(1/2.**%i)" % j) for j in range(9)]
    # Binary Operations
    F = [eval("lambda a,b:a%sb"%o) for o in ["+","-","*","/","**"]] + [lambda a,b:a**(1./b)]

    def combos(i):
        L = {x}
        for u in U:
            # 3, 33, 333, etc.
            L |= {u(int(str(x)*i))}
            
            for j in range(1,i):
                for X in combos(j):
                    for Y in combos(i-j):
                        for f in F:
                            # To avoid trouble with division by zero, overflows and similar:
                            try:
                                L |= {u(f(X,Y))}
                            except:
                                pass
        return L

    return [n in combos(i) for n in range(1,11)]

For testing I recommend to change (9) to something smaller, since this is the number of multiple square roots taken into account, which has a huge impact on the performance.

Finally, this made me wonder, whether the unary minus is actually needed in some case …

Answer 3

Mathematica - 246 characters (no bonuses claimed)

f[x_,y_]:=x-y
g[x_,y_]:=x/y
h[x_,y_]:=x^(1/y)
j[x_,y_]:=FromDigits@Join[IntegerDigits@x,{y}]
z[{r_,n_,L_}]:=z[{L[[1]][r,n],n,Rest@L}]
z[{r_,n_,{}}]:=r
a[n_,t_]:=Union@Select[z[{n,n,#}]&/@Tuples[{Plus,f,Times,g,Power,h,j},t-1],IntegerQ@#&&0<#<11&]

Explanation

Function j concatenates two numbers digit-wise.

Function z takes a result r, number n, and list of functions L, each which operates on two arguments. It then applies the list of functions sequentially to argumnts [r,n] using recursion, until the list is empty, whereupon it returns the result.

Function a takes a number n and a number of copies t. It creates all tuples of length (t-1) from the list of functions {Plus, f, Times, g, Power, h, j} and sends each tuple through function z, then returns a list of all numbers 1 through 10 that were created.

Example execution a[2,3] returning {1, 2, 3, 6, 8}.

Limitations

Because the list of functions is applied sequentially, consuming one copy of the number each time, it can miss some combinations. For example, when operating on four twos, it would miss 22/22 = 1 due to its inability to evaluate the list of functions out of order. Of course, 2/2*2/2 = 1 covers this case.

Answer 4

Python 3 (imperfect), 449 - 300 = 149

Suffers from all the same shortcomings as KSab's solution: no unary operators, fully parenthesized, contains equivalent expressions like (1+1)+1 and 1+(1+1). I eliminated exact duplicates by passing the results to set(). The output could be a bit uglier to save a few bytes, but I like it this way. I also didn't do nth roots because it doesn't seem like they buy you much in this problem.

R=range
E=lambda z:eval(z.replace("^","**"))
def m(d,n):_=R(1,11);s={i:[]for i in _};r=R(1,n);n<2 and s[d].append(str(d));d=str(d);t=[[(d*i,i)for i in r]]+[[]]*n;h=[];[(h.append("("+A+o+B+")"),t[l].append((h[0],a+b))if a+b<n else E(*h)in _ and s[E(*h)].append(h[0]),h.pop())for l in r for j in R(l)for A,a in t[j]for k in R(l)for B,b in t[k]if a+b<=n for o in"+-*/^"if(o=="^"and-~-(0<E(B)<9)or 0==E(B)and"/"==o)-1];[print(i,set(s[i])or'')for i in _]

This will take several minutes to run if the second argument is 5. Test by calling m(digit, number):

>>> m(1,3)
1 {'((1*1)^1)', '(1^(1+1))', '((1-1)+1)', '((1/1)/1)', '((1*1)*1)', '((1^1)/1)', '(1*(1*1))', '(1^(1*1))', '(1+(1-1))', '(1^(1^1))', '((1^1)*1)', '(1^(1/1))', '((1/1)*1)', '(1-(1-1))', '(1/(1^1))', '(1/(1*1))', '(1/(1/1))', '(1*(1^1))', '((1+1)-1)', '((1*1)/1)', '((1^1)^1)', '(1*(1/1))', '((1/1)^1)'}
2 {'(1*(1+1))', '((1^1)+1)', '((1+1)/1)', '((1*1)+1)', '((1+1)^1)', '(1+(1*1))', '((1/1)+1)', '(1+(1^1))', '(1+(1/1))', '((1+1)*1)'}
3 {'((1+1)+1)', '(1+(1+1))'}
4 
5 
6 
7 
8 
9 
10 {'(11-1)'}
>>> m(3,3)
1 {'((3/3)^3)'}
2 {'(3-(3/3))', '((3+3)/3)'}
3 {'(3-(3-3))', '((3-3)+3)', '((3/3)*3)', '(3*(3/3))', '(3/(3/3))', '((3+3)-3)', '(3^(3/3))', '(3+(3-3))', '((3*3)/3)'}
4 {'((3/3)+3)', '(3+(3/3))'}
5 
6 {'((3*3)-3)'}
7 
8 
9 {'(3+(3+3))', '((3+3)+3)', '((3^3)/3)'}
10