Four fours puzzle

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.

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

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.

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. 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

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

05AB1E, 70 69 bytes

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?) to understand why •1OF• is 71160; •1OF•₂в is [4,1,6,24]; and ŽYy is 8730.