good chemistry is complicated,and a little bit messy -LW PerlMonks

### Re^4: Golf: Tree searching

 on Apr 20, 2001 at 06:12 UTC ( #74051=note: print w/replies, xml ) Need Help??

in reply to Re (tilly) 3: Golf: Tree searching

Both tilly and indigo have exactly the same result, which is a fix of twerq's including 1) my, and 2) the test for \$t which prevents infinite looping.

Here is a solution which is short, but not 'strict' compliant: sub f{for((\$s,\$t)=@_;\$_=\$\$t{(0,l,r)[\$\$t{d}cmp\$s]};\$t=\$_){}\$t}
Alas, although 4 characters lighter, it doesn't return 0 on misses properly. This does, but is admittedly 3 characters heavy: sub f{for((\$s,\$t)=@_;\$_=\$t&&(0,l,r)[\$\$t{d}cmp\$s];){\$t=\$\$t{\$_}||0}\$t}
Or, a tie, provided the tree has 0-value stubs as it does in other examples: sub f{for((\$s,\$t)=@_;\$_=\$t&&(0,l,r)[\$\$t{d}cmp\$s];){\$t=\$\$t{\$_}}\$t}
Fun test code below for a tree:
```    \$|++;
\$table = {
d => 'h',
l => {
d => 'd',
l => { d => 'b', l => { d => 'a' }, r => { d => 'c' } },
r => { d => 'f', l => { d => 'e' }, r => { d => 'g' } },
},
r => {
d => 'l',
l => { d => 'j', l => { d => 'i' }, r => { d => 'k' } },
r => { d => 'm', l => { d => 'l' }, r => { d => 'n' } },
}
};

foreach \$y (qw[ a b c d e f g h i j k l m n o p q ])
{
\$x = f(\$y,\$table);
print "Answer for \$y = ";
print \$x," ", \$\$x{d},"\n";
}
value entry in the hash.

Replies are listed 'Best First'.
Re (tilly) 4: Golf: Tree searching
by tilly (Archbishop) on Apr 20, 2001 at 07:19 UTC
Well it has to handle both failure and success. However by borrowing shamelessly from tye, I beat my previous, and if we want to be shamelessly non-strict about it, I can improve again.
```sub f {
\$t=pop;\$t=\$\$t{\$c>0?l:r}while\$c=\$\$t{d}cmp\$_[0]and\$t;\$t
}
By my count this is 53 characters.
Inspirationally shameless, and a great demonstration of the power of 'and' versus '&&', something that I hadn't fully understood. Until now. I have to say, at first it looks like a drop-in alternative to the presumably scary C-style double-ampersands (as in, an artifact of the use English movement), but when you get right down to it, it binds much more loosely, enhancing its utility vastly.

In the spirit of shameless borrowing, switching to 'pop' and using 'and' nets the following: sub f{for(\$t=pop;\$_=(0,l,r)[\$\$t{d}cmp\$_[0]]and\$t=\$\$t{\$_};){}\$t}
But this is really just converging on the same thing: sub f{for(\$t=pop;\$_=\$\$t{d}cmp\$_[0]and\$t=\$\$t{\$_>0?l:r};){}\$t}
Which is the same length, and functionally the same due to heavy cross-pollination.

Of course, if the spec had indicated that the two branches were labelled '-1' and '1' instead of 'r' and 'l', that would certainly simplify things a whole lot. Or at least it would save 6 precious characters: sub f{for(\$t=pop;\$_=\$\$t{d}cmp\$_[0]and\$t=\$\$t{\$_};){}\$t}
A tip. Whenever possible go for the one-line looping constructs. The following two are equivalent logically:
```for(A;B;C){}
A;C while B;
however the second has 3 characters you may be able to drop. So use it. Even if it means using commas etc in C to get it to work, use it. (I am able to drop the 2 spaces.) A technicality, to be sure, but a significant one.

Also while the binding of and can make it better than &&, if you see it used that way, look for a way to move things around to get the && in somewhere and save a character. Watch:

```sub f {
\$t=pop;\$t=\$\$t{\$c>0?l:r}while\$c=\$t&&\$\$t{d}cmp\$_[0];\$t
}
Not something you would write from scratch, but there you have it...

Create A New User
Node Status?
node history
Node Type: note [id://74051]
help
Chatterbox?
 [choroba]: ♪ ♫ ♬ Moon on the water... the fire in the sky... ♪ ♫ ♬

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (18)
As of 2017-07-25 09:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I came, I saw, I ...

Results (368 votes). Check out past polls.