### Golf: Tree searching

by Masem (Monsignor)
 on Apr 19, 2001 at 21:48 UTC ( #73900=perlmeditation: print w/ replies, xml ) Need Help??

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 pre-made 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 - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain

Replies are listed 'Best First'.
(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")
Very nice. I tried several times without success to come up with a good non-recursive 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...

Thanks, but credit goes to Masem for the algorithm as mine was just mechanical compression of Masem's original code. (:

- tye (but my friends call me "Tye")
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
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
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);
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=shift||return;\$a{\$n->{d}}=\$n;r(\$n
+->{l});r(\$n->{r});};};

Speak up if I missed something.

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...
Re: Golf: Tree searching
by premchai21 (Curate) on Apr 19, 2001 at 22:58 UTC
Hmmm...
```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?

Create A New User
Node Status?
node history
Node Type: perlmeditation [id://73900]
Approved by root
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (19)
As of 2016-07-27 13:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
What is your favorite alternate name for a (specific) keyboard key?

Results (242 votes). Check out past polls.