While lurking in the #forth channel on irc.freenode.net I was pointed to an interesting problem from the Gforth tutorial. The problem is to implement MIN in Forth without any conditionally executed code.
DO, LOOP, BEGIN, UNTIL, REPEAT, WHILE, IF, ELSE and THEN are all forbidden. MIN removes the top two values from the data stack then puts the lower of the two back on.
Can you implement MIN under these conditions? If so I challenge you implement it in as few Forth words as possible! Let me know if your implementation is under 10 words :-)
Posts
7 comments:
: min 2dup - abs - + 2 / ;
If a < b, |a-b| = b-a, so min = a = ((a+b)-(b-a))/2 = (a+b)-|a-b|)/2.
If b < a, |a-b| = a-b, so min = b = ((a+b)-(a-b))/2 = (a+b)-|a-b|)/2.
So ((a+b)-|a-b|)/2 is always the right answer. 7 words, 6 if you have a builtin 2/.
tardieu: that's a neat solution. My technique looks ugly by comparison.
However, it's possible to implement MIN in less words :-)
: min 2dup > 1+ pick 2nip ;
llogiq: great solution, mine is similar:
: min 2dup < 1+ roll nip ;
Great - in fact I like your solution more than my own. Btw. I did not "get" forth, until researching it a little bit for solving this small puzzle and finding Rich Jones' impressively documented implementation. Thank you.
Er...what Forth system are you using? Admittedly 2nip is not a standard word, but usually it is a double cell version of nip, not "nip nip", so 2dup > 1+ pick 2nip would not be a solution...
Anonymous: You're right. Thank you for finding my error.
Post a Comment