Joachim Breitner's Homepage

Categories

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!

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.

@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)};