14
\$\begingroup\$

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 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 4th 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 4th 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 4th 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!

\$\endgroup\$
  • 1
    \$\begingroup\$ I'm sorry, this may be dumb, but how do you get 10 with only three 1s? \$\endgroup\$ – FryAmTheEggman Sep 22 '14 at 15:43
  • 3
    \$\begingroup\$ @FryAmTheEggman 11-1 \$\endgroup\$ – Optimizer Sep 22 '14 at 15:46
  • 1
    \$\begingroup\$ Ah, so I was dumb :p \$\endgroup\$ – FryAmTheEggman Sep 22 '14 at 15:47
  • 4
    \$\begingroup\$ That's a very vague rule. I may decide that the square root of 1, the square root of the square root of 1, etc. are all different approaches and I have an infinite number of answers. Is a+b different from b+a? Is (-a) * (-b) different from b * a? \$\endgroup\$ – feersum Sep 24 '14 at 8:18
  • 2
    \$\begingroup\$ I am aware of this, but I cannot represent 4^(4^(4^(4^4))) in any regular number format – storing 4^(4^(4^4)) as an integer already needs more bits than there are atoms in the universe). So unless I use a computer algebra system capable of handling such numbers (if one exists at all), I need to treat these as special cases. This however almost certainly requires more characters than I win by overkilled. Therefore these awards are pointless unless you somewhat exclude multiple square roots. \$\endgroup\$ – Wrzlprmft Sep 24 '14 at 18:42
1
+50
\$\begingroup\$

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 
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I found a couple things you can do to shorten L: 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)or b>100 else a**b")),('v',F("''if a==0 or(b<0 and int(1./a)!=(1./a))or(b or a<0)or(1./a)>100 else b**(1./a)"))]if o(u,v)!=''] \$\endgroup\$ – FryAmTheEggman Sep 25 '14 at 18:05
  • \$\begingroup\$ I'm sorry, that comment looks really bad :( Anyway, to explain: when comparing against 0, I tried to negate the statement, then swap the consequences. I also found a few places to use | and & instead of or and and. Both of these tricks could be used to shorten the last call to F, but that one would require some Demorgan's and I ran out of beak time ;p \$\endgroup\$ – FryAmTheEggman Sep 25 '14 at 18:16
  • \$\begingroup\$ @FryAmTheEggman Oh that's a good catch, I've updated my answer with what you posted and when I have time I'll look at the last one. Those conditionals to check the validity of the input did get a bit more hefty than I expected :/ \$\endgroup\$ – KSab Sep 25 '14 at 18:56
  • \$\begingroup\$ +10 for the brilliancy of nested lambdas and eval--it took me quite a while to figure your second line out! I think I've got you beat on "longest single line," though. ;) I agree on ignoring large exponents; in fact, I think any exponent bigger than 9 isn't going to be useful (except as a no-op when the base is 1). \$\endgroup\$ – DLosc Sep 26 '14 at 2:21
  • \$\begingroup\$ @DLosc Well the one scenario you can have is something like 3 = 33 √ (3 ^ 33). Actually as I write this I realize that two (probably the only two?) combinations that my answer misses are 4 = (4^4) √ (4 ^ (4^4)) and the equivalent expression with 5s. Admittedly roots don't seem to add much to the problem, as the vast majority of them are either used as no-ops on either 0 or 1, no-ops when the root is 1, or just to cancel out a power. \$\endgroup\$ – KSab Sep 26 '14 at 4:14
3
\$\begingroup\$

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 …

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I think you are right about the unary '-' probably not adding anything (at least to the base question without the bonuses). The only non-trivial scenario I can think of would be anything like 1 = 3^3 * 3^(-3), but even considering these, I doubt there are any numbers for which this is a possible solution when there are no others. \$\endgroup\$ – KSab Sep 26 '14 at 4:38
  • 1
    \$\begingroup\$ You can save 3 bytes by using a**.5**%i instead of a**(1/2**%i) to compute the multiple square roots. \$\endgroup\$ – DLosc Sep 26 '14 at 18:01
  • \$\begingroup\$ @DLosc: Indeed, thanks. \$\endgroup\$ – Wrzlprmft Sep 26 '14 at 18:17
  • \$\begingroup\$ You can save six bytes by reducing the four space indent to one space. \$\endgroup\$ – Beta Decay Sep 27 '14 at 6:22
  • \$\begingroup\$ @BetaDecay: I never use four-space indents (shudder), I use tabs. Just look into the source of my post. Stack Exchange just renders them as four spaces. \$\endgroup\$ – Wrzlprmft Sep 27 '14 at 7:56
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.