Joachim Breitner

FourFours in Haskell

Published 2006-12-04 in sections English, Haskell.

An interesting programming puzzle appeard in the Blogosphere: To describe every integer from 1 to 100 as a calculation involving only and exactly four fours, and standard operations. There are solutions in C# (code) and in python (code), so I tried to do mine in Haskell.

This seems to be meant for Haskell. The Type system makes the program really great to read. Functional programming allows me to conveniently create all possible associations of four operands with three binary operations. (I found five. Why are the other two sources using four?) And, in this program particular, the use of the list monad to quickly generate a list of all possible combination is really a programming-time-saver.

The program is not too slow either (IBM Thinkpad T41p with Intel M 1700MHz):

$ time ./fourfours >/dev/null
real 0m0.917s
user 0m0.852s
sys 0m0.040s

And it could probably be sped up by using some kind of hashing or similar stuffs. Note that the program has only 73 mostly quite short lines, while the python code has 119 and the C# code has 138 of relatively long lines (comments and empty lines not counted). I think this is impressive (unless you have worked with haskell a bit, then you are used to these kind of results). Comments welcome!

Comments

Did the same stuff in Perl and it looks a little shorter but it is dog slow. :-/

@u=(C..H,'sqrt');@b=qw(+ * - / **);sub i{my$s=shift;if($s=~/U/){$x=$s,
$x=~s/U/$_/,i($x) for@u}elsif($s=~/B/){$x=$s,$x=~s/B/$_/,i($x) for@b}
else{($e=eval$s)&&($expr{$e}=$s)}}i("(((U(4)BU(4))BU(4)))BU(4)");i(
"(U(4)BU(4))B(U(4)BU(4))");($_="$_: $expr{$_}\n"),s/F.*?\)/4!/g,
s/C.*?\)/sqrt(.4bar)/g,s/D.*?\)/sqrt(.4)/g,s/G.*?\)/.4'/g,
s/E.*?\)/.4/g,s/H.*?\)/4/g,print for 1..100;sub H{shift};sub E{(shift)
/10};sub G{(shift)/9};sub D{sqrt((shift)/10)};sub C{sqrt((shift)/9)}
sub F{$_[0]==0||$_[0]*F($_[0]-1)};
#1 Überperle am 2006-12-04
Impressive I especially like the result that it finds for the 1:

1: (sqrt(4)**sqrt(4))**(sqrt(4)-sqrt(4))

That’s almost as ofuscated as your code :-)
#2 Joachim Breitner (Homepage) am 2006-12-04
Now it's even shorter and gives nicer looking results:

http://paste-it.net/684
#3 Überperle am 2006-12-05
I decided to take a shot at the problem in Haskell as well.

I don't know how to properly include code in comments on your blog, so here's a link which should work as long as my computer is on (which is usually always the case).
http://cale.yi.org/autoshare/FourFour.hs
#4 Cale Gibbard am 2006-12-05
Very nice. I had :x: as infix constructors once, but had some problems them. I also like the use of monads to handle evaluation errors, something I considered, but did not do (I yet have to learn more about Monads).

I especially like how you do not specify a monad for eval, and it just falls into place when it is used in the list comprehension.
#5 Joachim Breitner (Homepage) am 2006-12-05
If I understand your code correctly, you're using exponentiation as one of your operators. (I don't really know Haskell, though.) In both Python and C#, the '^' operator is bitwise xor, not exponentiation.

Neither is needed, though. I was able to get all 100 numbers using just addition, subtraction, multiplication, and division. (This was in Common Lisp, which does ratios for integer division; perhaps C#'s and Python's division operators don't work in the same way. OTOH, I still got all the numbers when using truncate instead of /, so who knows?)
#6 Phil! Gregory (Homepage) am 2006-12-06
<strong>Trackback:</strong> <a href="http://aperiodic.net/phil/archives/Geekery/four-fours.html">FourFours in Common Lisp</a><br />I came across the FourFours problem recently. Stated succinctly, it asks:
what are the ways to calculate each of the integers from 1 to 100 with
formulas which use the digit four exactly four times? (No digits other
than four can be used at all.)

Peopl
#7 Phil! Gregory (Homepage) am 2006-12-10
Comment about the list monad thing: I agree that it is a nice example of using the list monad, but I find in this case it is not really necessary to go the monad way when list comprehension offers the same:

all_combos = concat [ groupings v1 v2 v3 v4 b1 b2 b3 | v1 &lt;- zeroaries, v2 &lt;- zeroaries, v3 &lt;- zeroaries, v4 &lt;- zeroaries, b1 &lt;- binaries, b2 &lt;- binaries, b3 &lt;- binaries]

(Where &lt; is supposed to display as an left angle bracket.)

Cheers!

Jan
#8 Jan am 2008-04-29
Personally, I often find list monad expressions easier to read than list comprehensions, but thats personal taste of course. In the end, it’s syntactic sugar for the same thing, AFIAK.
#9 Joachim Breitner (Homepage) am 2008-04-29
apropos comprehension, this

http://groups.csail.mit.edu/pag/reading-group/wadler-monads.pdf

is a really nice read.
#10 sheyll am 2008-12-01

Have something to say? You can post a comment by sending an e-Mail to me at <mail@joachim-breitner.de>, and I will include it here.