Given: a binary tree composed of nodes. Each node is stored as a hash, and contains (at least) 3 keys: 'd' is a data string, 'l' is the left node, and 'r' is the right node. The tree has been premade such that all nodes that are in the 'l' (left) node are less than or equal to the 'd' element, and similar for nodes that are greater than in the right node. A value 0 is used for the 'l' or 'r' position if there are no further nodes that satisfy it. You are given $t, a reference to the top node, and $s, a string that you want to search for.
Find: the perl golf best solution for a subroutine that returns the node that $s is in, or 0 if no such node exists.
Do not assume that the tree is well balanced. For avoiding problems with lots of excess characters, assume that you can avoid the 'use strict'.
My current best attempt is 95 characters:
sub f{($s,$t)=@_;while($t>{d}ne$s){$t=($s lt $t>{d})?$t>{l}:$t>{r}
+;return if$t==0;}return$t;}
Dr. Michael K. Neylon  mneylonpm@masemware.com

"You've left the lens cap of your mind on again, Pinky"  The Brain
(tye)Re: Golf: Tree searching
by tye (Sage) on Apr 19, 2001 at 22:06 UTC

sub f{($s,$t)=@_;{return$t if!$t$t>{d}eq$s;$t=$t>{$t>{d}gt$s?l:r}
+;redo}}
...I think...

tye
(but my friends call me "Tye")  [reply] [d/l] 

Very nice. I tried several times without success to come
up with a good nonrecursive solution. The above not only
is short, but it really does the binary search, and
applying standard golfing techniques, it comes up a
winner at 55:
sub f{
($s,$t)=@_;$t=$$t{$$t{d}gt$s?l:r}while$t&&$$t{d}ne$s;$t
}
(Or 57 if you add my to kill side effects. Still
better than anything I thought of.)
Note that this is much less readable than what tye
wrote, but every transformation is fairly mechanical
compression of the code...  [reply] [d/l] 

 [reply] 
Re: Golf: Tree searching
by japhy (Canon) on Apr 19, 2001 at 22:17 UTC

Here's code in your vein (72 chars not counting 'sub '):
sub f{($s,$t)=@_;while($t>{d}ne$s){$t=$t>{(r,l)[$s lt$t>{d}]}retu
+rn}$t}
Here's 63 chars:
sub f{($^,*_)=@_;*_=$_{(r,l)[$^lt$_{d}]}return while$_{d}ne$^;*_}
japhy 
Perl and Regex Hacker  [reply] [d/l] [select] 

Here's 58 chars with a completely different approach. .
sub f{($s,$t)=@_;$$t{d}eq$s?$t:f($s,$$t{l})f($s,$$t{r})}
twerq
 [reply] [d/l] 

As koolade pointed out, not all of these
work. Yours in particular goes into deep recursion.
Works in theory is not good enough, in golf you are going
to learn a lot about the assumptions you cannot make.
And yours has at least 2 separate (and serious) mistakes.
BTW the counts as I list them are just for the body of the
sub, so if yours did work it would be 51 characters.
Playing independently I came in with several solutions
that are small, and the following which is similar to
yours really does work at 58:
sub f {
my($s,$t)=@_;$t?$$t{d}eq$s?$t:f($s,$$t{l})f($s,$$t{r}):0
}
And here, thanks to koolade, is the test that I use:
$t = {
d => 'd',
l => {
d => 'b',
l => { d => 'a', l => 0, r => 0, },
r => { d => 'c', l => 0, r => 0, },
},
r => {
d => 'f',
l => { d => 'e', l => 0, r => 0, },
r => { d => 'g', l => 0, r => 0, },
}
};
sub test {
my $val = f(@_);
print $val ? "$val>{d}:$val\n" : "$val\n";
}
test('e',$t);
test('O',$t);
 [reply] [d/l] [select] 



Re: Golf: Tree searching
by koolade (Pilgrim) on Apr 19, 2001 at 23:01 UTC

I haven't been able to get some of the answers to work. Maybe I have a different image of the data structure. Can somebody post what they've been working with?
Here's what I'm using to test:
$t = {
d => 'd',
l => {
d => 'b',
l => { d => 'a', l => 0, r => 0, },
r => { d => 'c', l => 0, r => 0, },
},
r => {
d => 'f',
l => { d => 'e', l => 0, r => 0, },
r => { d => 'g', l => 0, r => 0, },
}
};
And here's a solution in 92 chars, that puts the tree into a single hash, and searches using the hash:
sub f{r(pop);$a{(pop)}0;sub r{my$n=shiftreturn;$a{$n>{d}}=$n;r($n
+>{l});r($n>{r});};};
Speak up if I missed something.  [reply] [d/l] [select] 
Re: Golf: Tree searching
by indigo (Scribe) on Apr 19, 2001 at 23:03 UTC

sub f{my($s,$t)=@_;$t?$$t{d}eq$s?$t:f($s,$$t{l})f($s,$$t{r}):0}
61 chars. Passes w and use strict.
Hint: You don't have to take advantage of the binary search property...
 [reply] [d/l] 
Re: Golf: Tree searching
by premchai21 (Curate) on Apr 19, 2001 at 22:58 UTC

sub z{my($s,$t)=@_;return if!$t;(z($s,$t>{r},$t,z($s,$t>{l}))[$s cmp
+ $t>{d}]}
81 chars. Shorter than Masem, but longer than jcwren. However, something's wrong with it that I can't quite pinpoint. Can anyone figure out why this doesn't work?  [reply] [d/l] 

