[Question]
  [
The [Four fours puzzle](http://en.wikipedia.org/wiki/Four_fours) 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](http://en.wikipedia.org/wiki/Gamma_function) (`Γ`)
* Exponentiation (`^`), Square root (`√`)
* Concatenation (eg. `44` is two `4`s)
* Decimal point (eg. `4.4` is two `4`s), 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 `4`s - no more, no less. Also, `.4 = 4/10` is a valid term, and counts as using only one `4`.
  
[Answer]
## 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](http://en.wikipedia.org/wiki/Code_page_437) and [cp850](http://en.wikipedia.org/wiki/Code_page_850), 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](http://codepad.org/6V0V8cz2). 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]
## 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]
## 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](http://pastebin.com/PgGuQTN3)
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), ~~70~~ 69 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
•1OF•₂в"(4/9)"ª0.4ª©4ã"+-*/"3ãâε`.ιJ}.Δ.EQ}®¦¨ŽYyç"Γÿ4 Γ4 4! .4~"#:0K
```
[Try it online](https://tio.run/##AWkAlv9vc2FiaWX//@KAojFPRuKAouKCgtCyIig0LzkpIsKqMC40wqrCqTTDoyIrLSovIjPDo8OizrVgLs65Sn0uzpQuRVF9wq7CpsKoxb1ZecOnIs6Tw780IM6TNCA0ISAuNH4iIzowS///Njc) or [verify all test cases](https://tio.run/##AXkAhv9vc2FiaWX/0YLGkk4/IiDihpIgIj9OVf/igKIxT0bigKLigoLQsiIoNC85KSLCqjAuNMKqwqk0w6MiKy0qLyIzw6PDos61YC7OuUp9Ls6ULkVYUX3CrsKmwqjFvVl5w6cizpPDvzQgzpM0IDQhIC40fiIjOjBL/yz/).
**Explanation:**
Uses a similar approach as some of the other answers. Creates all possible combinations of four of the values \$[1,4,6,24,\frac{4}{9},0.4]\$ and three of the operators `+-*/` (both of course with duplicates).
```
•1OF•                       # Push compressed integer 71160
     ₂в                     # Convert it to base-26 as list: [4,1,6,24]
       "(4/9)"ª             # Append "(4/9)": [4,1,6,24,"(4/9)"]
       0.4ª                 # As well as 0.4: [4,1,6,24,"(4/9)",0.4]
           ©                # Store this list in variable `®` (without popping)
4ã                          # Create all possible quartets by using the cartesian product times 4
"+-*/"                      # Push the string "+-*/"
      3ã                    # Create all possible triplets by using the cartesian product times 3
â                           # Create all possible pairs of both lists by using the cartesian product
 ε    }                     # Map each pair of lists by:
  `                         #  Push the list and string separated to the stack
   .ι                       #  Interleave them
     J                      #  And join them together
.Δ                          # Find the first which is truthy for:
  .E                        #  Evaluate the expression-string as Python code
                            #  (NOTE: Unfortunately doesn't work with .4 instead of 0.4)
    Q                       #  And check if it equals the (implicit) input-integer
}®                          # After we've found our result: push the list from variable `®`
  ¦¨                        # Remove the first and last items: [1,6,24,"(4/9)"]
    ŽYy                     # Push compressed integer 8730
       ç                    # Convert it to a character with this unicode: "√"
                            # (`√` isn't part of 05AB1E's codepage, hence why this is necessary)
        "Γÿ4 Γ4 4! .4~"     # Push this string, where the `ÿ` is automatically filled with the "√"
                       #    # Split it on spaces: ["Γ√4","Γ4","4!",".4~"]
                        :   # Replace the [1,6,24,"(4/9)"] with ["Γ√4","Γ4","4!",".4~"]
                         0K # And remove all 0s to convert the "0.4"s to ".4"s
                            # (after which the result is output implicitly)
```
[See this 05AB1E tip (section *How to compress large integers?* and *How to compress integer lists?*)](https://codegolf.stackexchange.com/a/166851/52210) to understand why `•1OF•` is `71160`; `•1OF•₂в` is `[4,1,6,24]`; and `ŽYy` is `8730`.
]