Four fours puzzle

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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