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.
Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain
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 | |
by tilly (Archbishop) on Apr 20, 2001 at 02:22 UTC | |
by tye (Sage) on Apr 20, 2001 at 09:44 UTC | |
Re: Golf: Tree searching
by japhy (Canon) on Apr 19, 2001 at 22:17 UTC | |
by twerq (Deacon) on Apr 19, 2001 at 22:48 UTC | |
by tilly (Archbishop) on Apr 20, 2001 at 01:55 UTC | |
by tadman (Prior) on Apr 20, 2001 at 06:12 UTC | |
by tilly (Archbishop) on Apr 20, 2001 at 07:19 UTC | |
| |
Re: Golf: Tree searching
by koolade (Pilgrim) on Apr 19, 2001 at 23:01 UTC | |
Re: Golf: Tree searching
by indigo (Scribe) on Apr 19, 2001 at 23:03 UTC | |
Re: Golf: Tree searching
by premchai21 (Curate) on Apr 19, 2001 at 22:58 UTC |
Back to
Meditations