Swirly Mein Kopf

Monday, December 4. 2006

FourFours in Haskell

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!

Trackbacks


FourFours in Common Lisp
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
Weblog: Phil! Gregory
Tracked: Dec 11, 00:24

Comments

Display comments as (Linear | Threaded)

*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 on 2006-12-04 23:49 (Reply)
*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 :-)
#1.1 Joachim Breitner (Homepage) on 2006-12-05 00:17 (Reply)
*Now it's even shorter and gives nicer looking results:

http://paste-it.net/684
#1.1.1 Überperle on 2006-12-05 16:42 (Reply)
*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
#2 Cale Gibbard on 2006-12-05 01:54 (Reply)
*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.
#2.1 Joachim Breitner (Homepage) on 2006-12-05 10:03 (Reply)
*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?)
#3 Phil! Gregory (Homepage) on 2006-12-06 20:43 (Reply)
*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 <- zeroaries, v2 <- zeroaries, v3 <- zeroaries, v4 <- zeroaries, b1 <- binaries, b2 <- binaries, b3 <- binaries]

(Where < is supposed to display as an left angle bracket.)

Cheers!

Jan
#4 Jan on 2008-04-29 22:46 (Reply)
*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.
#4.1 Joachim Breitner (Homepage) on 2008-04-29 23:02 (Reply)
*apropos comprehension, this

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

is a really nice read.
#5 sheyll on 2008-12-01 02:29 (Reply)

Add Comment



To prevent automated Bots from commentspamming, please enter the string you see in the image below in the appropriate input box. Your comment will only be submitted if the strings match. Please ensure that your browser supports and accepts cookies, or your comment cannot be verified correctly.
CAPTCHA

What is the first name of the owner of this blog? / Wie heißt der Betreiber dieses Blogs mit Vornamen?
 
 
Nach oben