21
\$\begingroup\$

The Four fours puzzle is a popular recreational mathematical puzzle that involves using exactly four 4s (and no other number) and a defined set of operations to reach every number from 0 to a given maximum.

In this version, the only following operators are allowed:

  • Any grouping symbols may be used
  • Addition (+), Subtraction (-), Multiplication (*), Division (/)
  • Factorial (!), Gamma function (Γ)
  • Exponentiation (^), Square root ()
  • Concatenation (eg. 44 is two 4s)
  • Decimal point (eg. 4.4 is two 4s), Overbar (eg. .4~ = 4/9)

Standard order of operations applies.

Your program should generate, given an input between 0 and 100 inclusive, a correct solution for that input. If the program outputs an invalid solution to any input, that program is invalid.

For example, with an input of 0, your program might generate 44-44.

The use of external modules is not allowed. Only _.4~ is allowed for the overbar operator - that is, only one 4 can be behind the decimal point.

This is code golf, so shortest solution wins.


Edit: To be extra clear, the program must output a set of the above operations applied to exactly four 4s - no more, no less. Also, .4 = 4/10 is a valid term, and counts as using only one 4.

\$\endgroup\$
  • \$\begingroup\$ no rounding operations? :-( \$\endgroup\$ – John Dvorak Jul 13 '13 at 15:54
  • \$\begingroup\$ @JanDvorak err, no, that wouldn't be allowed. \$\endgroup\$ – Volatility Jul 13 '13 at 16:01
  • \$\begingroup\$ gamma and factorial are both allowed? \$\endgroup\$ – John Dvorak Jul 13 '13 at 16:10
  • \$\begingroup\$ @JanDvorak everthing that is listed (but only the things that are listed) can be used. \$\endgroup\$ – Volatility Jul 13 '13 at 16:17
  • \$\begingroup\$ are we allowed to output factorial as a prefix function (!(4) rather than (4)!)? \$\endgroup\$ – John Dvorak Jul 13 '13 at 16:40
6
\$\begingroup\$

GolfScript (129 chars*)

[4.`2'√4'24'4!'6'Γ4'1'Γ√4'120'ΓΓ4']2/:F{.F=[[44.`]]*\{`{+{'+*-'1/{:^;.[~@[\]{'()'1/*}%^*@@^~\]\}/}:|~2/~\+|;}+F/}%+}3*\{\0==}+?1=

Running time is on the order of 4 minutes on my PC. A moderate speed-up can be obtained at the cost of two characters by adding a uniqueness operation .& immediately after the %+.

I use pre-coded expressions for 1, 2, 4, 6, 24, 120, and 44, and build the rest up from those using only +, *, and -. This way I don't need to do any non-integer arithmetic in the program itself. I've tried to get simpler expressions by placing the simpler pre-coded values at the start.

All of those values are required, and it's necessary to support both directions of subtraction (complex_expression - simple_expression and vice versa). It's also necessary to include some operations which require parentheses (specifically, a*(b-c)), so I bracket all subexpressions indiscriminately.

* I'm counting Unicode code points assuming the program to be UTF-8 encoded, and brushing under the carpet the fact that unless you're using a recent version of Ruby to run the interpreter it's really treating it as ASCII characters. If you're very worried about this, use G for Gamma and v for sqrt.

Well, strictly I could remove 44 in exchange for 11 as 44/4 and 71 as √(Γ√4+(ΓΓ4+Γ√4)!), but that's not a good trade-off.

\$\endgroup\$
7
\$\begingroup\$

Python 155 bytes

h={4:'4',24:'4!',6:'â4',.4:'.4',1:'âû4',4/9.:'.4~'}
f={}
def g(r,s='24',y='4!'):f[eval(s)]=y;[g(r-1,s+o+`k`,y+o+h[k])for k in h for o in'/*-+'if r]
g(3)

The first three bytes (\xEF\xBB\xBF) are the UTF-8 byte order mark, although the file should be saved in an ANSI format. The û and â will be interpretted as and Γ respectively in cp437 and cp850, which should work on just about any Windows box.

Runtime is about 0.4s on my computer.

Sample usage (name the file four_fours.py):

$ python
>>> from four_fours import f
>>> f[39]
'4!+4!/.4/4'
>>> f[87]
'4!*4-4/.4~'
>>> for i in range(101): print i, f[i]
0 4!+4!-4!-4!
1 4!+4!/4!-4!
2 4!-4!+Γ4-4
3 4!-4!+4-Γ√4
4 4!+4!/Γ4-4!
.
.
.
96 4!+4!+4!+4!
97 4!*4!/Γ4+Γ√4
98 4!*4+Γ4-4
99 4!*4+4-Γ√4
100 4!*4!/Γ4+4

Results for 0..100. Due to the way the hash is iterated, it prefers to use 4! as often as possible.

Edit: saved a number of bytes by adding Γ√4 = 1, which eliminates the need for any groupings, and by removing √4 = 2, which was no longer necessary.

\$\endgroup\$
4
\$\begingroup\$

J, 175 161 chars

   f=.')',~'(',;@((<;._2'+ - * % .4 .4~ g(r(4)) r(4) 4 g(4) 4! ( ) '){~(143402 A.i.9)
      /:~(12,11,0,6$0 4 4)+(9$4 7 7)#:((,@(+/,-/,*/,%/)~)^:2,0.4 4r9 1 2 4 6 24)&i.)

   f 1
(.4+.4)+(.4%r(4))

   f 42
(r(4)+4)+(g(4)*g(4))

   f 100
(r(4)+r(4))+(4*4!)

Checked format is (v op v) op (v op v) where v={0.4 4/9 1 2 4 6 24} and op={+ - * /}

full 0..100 results

\$\endgroup\$
  • \$\begingroup\$ I don't think .4 is a valid number for this game. \$\endgroup\$ – John Dvorak Jul 14 '13 at 1:30
  • \$\begingroup\$ @JanDvorak it is - maybe I should have made it clearer \$\endgroup\$ – Volatility Jul 14 '13 at 1:38

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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