11
\$\begingroup\$

In this variant of the Four fours puzzle your should use up to x x's (and no other number) and a defined set of operations to reach every number from 0 to 100. If x = 4 then you can use up to four 4s and this question becomes the classic four fours puzzle (except you can use up to four 4s rather than having to use exactly four of them). We assume 1 < x <= 9.

In this version, only the following operators are allowed:

  • Addition (+), Subtraction (-), Multiplication (*), Division (/). Note this is real division, so that 5/2 = 2.5.
  • Exponentiation (e.g. 4^4) as this would involve no extra symbols if written normally by hand.
  • You can make new integers by concatenating xs. E.g. you can make the integers 4, 44, 444, 4444.

You may also use parentheses to group numbers simply in order to control the order of evaluation of the operators. You can't for example combine parentheses with concatenation as in (4/4)(4/4) = (1)(1) = 11.

No other symbols may be used and standard order of operations applies.

Your program should generate, given an x in the defined range and an n between 0 and 100 inclusive, a correct solution for that input if it exists. Otherwise your code must output something to indicate no such solution exists.

You must be able to run your submission to completion on your machine for any input values of x and n in the allowed range. This is code golf, so shortest solution wins.

This old related question uses more operators (and only 4s) and hence all numbers from 0 to 100 are solvable which won't be true for this challenge.

Input and output

Your code takes two integers x and n as input and should output a solution (or an indication there is no solution) in any human readable format you find convenient. Input 4 6 would mean "Using up to four 4s, make the number 6" for example. So if the input is 4 6 the output could be (4+4)/4+4.

\$\endgroup\$
  • 1
    \$\begingroup\$ Helpful Reference \$\endgroup\$ – Engineer Toast May 15 '18 at 20:51
  • 2
    \$\begingroup\$ Can parens be combined with concatenation? e.g. `(4/4)(4/4) = (1)(1) = 11 ? \$\endgroup\$ – Digital Trauma May 15 '18 at 20:52
  • 1
    \$\begingroup\$ Adding parentheses (and disallowing parentheses + concatenation) does make this significantly harder \$\endgroup\$ – Draconis May 15 '18 at 21:16
  • 2
    \$\begingroup\$ Adding the exponentiation operator and an outer loop over the number of times the digit is used don't IMO add anything non-trivial over codegolf.stackexchange.com/q/82884/194 \$\endgroup\$ – Peter Taylor May 16 '18 at 16:11
  • 2
    \$\begingroup\$ @PeterTaylor The parentheses seem to make quite a lot of difference. I would vote to reopen if I could. \$\endgroup\$ – felipa May 17 '18 at 13:58
4
\$\begingroup\$

Python 3, 265 bytes

def f(x,n):
 for e in g(x,x-(x>7)):
  try:
   if eval(e)==n:return e
  except:1
g=lambda x,d:{str(x)*-~i for i in range(d)}|{s%(a,b)for a in g(x,d-1)for b in g(x,d-a.count(str(x)))for s in'%s**%s (%s/%s) (%s+%s) (%s-%s) %s*%s %s/%s'.split()['**'in a+b:]}if d else{}

Try it online!

Works for all numbers in the reference linked by Engineer Toast.

Runs up to x=8 on tio, x=9 takes a couple of minutes on my machine.


The function g returns a set of all combinations with at most x number of x's. f then loops through them and returns the first which evaluates to the number n.

The number of possible values i found for each x are:

x  possible numbers
------
2  5
3  17
4  35
5  56
6  83
7  101
8  101
9  101

All the numbers above can be generated from (a+b), (a-b), (a+b), a*b, a/b, (a/b), and a^b. a+b and a-b do not give more numbers.

a^b is also only used once, as otherwise huge numbers are created (this is also verified in the reference document above)


An alternate version which short-circuits as soon as it finds a solution (not as golfed):

This is much faster as for x=7..9 all numbers can be created.

Python 3, 338 289 bytes

def f(x,n,d=-1):
 d=[d,x][d<0];X=str(x);r=set()
 for E in{X*-~i for i in range(d)}|{s%(a,b)for a in[0]*d and f(x,n,d-1)for b in f(x,n,d-a.count(X))for s in'%s**%s (%s/%s) (%s+%s) (%s-%s) %s*%s %s/%s'.split()['**'in a+b:]}:
  try:e=eval(E)
  except:e=-1
  if e==n:exit(E)
  r|={E}
 return r

Try it online!

\$\endgroup\$
  • \$\begingroup\$ This is a very nice answer! I thought you were always using exactly (as opposed to up to) x xs (e.g. (4/4**(4-4)) for 4) but it turns out that isn't the case. \$\endgroup\$ – Anush May 16 '18 at 15:10
  • \$\begingroup\$ exit(e) is shorter than return e \$\endgroup\$ – mbomb007 May 16 '18 at 18:50

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.