Joachim Breitner's Homepage
FourFours in 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
1: (sqrt(4)**sqrt(4))**(sqrt(4)-sqrt(4))
That’s almost as ofuscated as your code :-)
http://paste-it.net/684
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
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.
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?)
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
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
http://groups.csail.mit.edu/pag/reading-group/wadler-monads.pdf
is a really nice read.
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)};