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 :-)
: min 2dup - abs - + 2 / ;
ReplyDeleteIf 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.
ReplyDeleteHowever, it's possible to implement MIN in less words :-)
: min 2dup > 1+ pick 2nip ;
ReplyDeletellogiq: great solution, mine is similar:
ReplyDelete: 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.
ReplyDeleteEr...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...
ReplyDeleteAnonymous: You're right. Thank you for finding my error.
ReplyDeleteThis discussion was a great help working through the tutorial in the Gforth manual.
ReplyDeleteHowever, I think there is an error in John's solution: the conditional is in the wrong direction.
John wrote:
: min 2dup < 1+ roll nip ;
... but I believe the correct solution is:
: min 2dup > 1+ roll nip ;
Thanks! I was trying to do it without pick - just with comparisons and bitwise logic, which I don't think is possible.
ReplyDeleteImpressive solutions!
With bitwise logic only:
ReplyDelete: min ( a b - x ) 2dup < tuck 0= and -rot and or ;
As an explanation: ands true with the smaller one, ands false with the larger one (making it 0), then ors those two together, to get the smaller one.
DeleteOne word shorter than my previous anonymous answers:
ReplyDelete: min 2dup > and tuck 0= and or ;
With commented stack as we go, where x/y means x if > was true, y if not:
: min ( a b -- x )
2dup > ( a b t/f )
and ( a b/0 )
tuck 0= ( b/0 a f/t )
and ( b/0 0/a )
or ; ( b/a )