Given an unsorted array of items which may or may not be distinct (with no item having a value of '', '0', or 0), and a coderef to a comparison function (see below).

Find a perl golf solution that returns a sorted binary tree containing those items. The tree need not be balanced if this improves the golf. The tree is represented by a hash; the key is the value from the array above, and the value is an anonymous array ref of 2 elements, the first is a reference to a similar hash for the left branch, while the second is a hash ref for the right branch. If neither branch exists, the value should be 0. See the example solution for more details.

The comparison function that is given works like the spaceship operator or cmp, in that it takes two items, and returns -1 if the first item is less than the second, 0 if they are equal, and 1 if the first item is greater than the second.

As an example: 

my @array = ( 1, 2, 3, 4, 5, 6 );
my $func = sub { $_[0] <=> $_[1] };

my %tree = buildtree( $func, @array );  # the golf function

# one possible output :
%tree => { 2 => [
                  { 1 => [ 0, 0 ] } ,
                  { 4 => [
                           { 3 => [ 0, 0 ] },
                           { 5 => [ 0, 
                                    { 6 => [ 0, 0 ] }
                                  ]
                           }
                         ]
                  }
                ]
            }

[download]
For extra fun, try to avoid the recursive solution.

-----------------------------------------------------
Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain
It's not what you know, but knowing how to find it if you don't know that's important

Replies are listed 'Best First'.
Re: (Golf) Building a Better Binary Tree
by dragonchild (Archbishop) on Oct 08, 2001 at 20:09 UTC
    158 characters, avoiding the recursive answer. 
    $f=shift;$h->{pop@_}=[0,0];for(@_){$i=$h;for(;;){$s=(keys%$i)[0];$b=($
+f->($_,$s)||last)>0?1:0;$i->{$s}[$b]?$i=$i->{$s}[$b]:($i->{$s}[$b]={$
+_,[0,0]},last)}}%$h

    [download]
    If handed a sorted array, it builds the worst-possible, cause it chooses the last element as the root. However, if handed an unsorted array, it should be relatively nice.

    Update: After thinking about this for a while, I cut it down a bit, down to 148 characters.

    Update2: 144 after removing unnecessary parens and rearranging the assignment to $h and rearranging the inner for-loop. 

    $f=shift;$h={pop@_,[0,0]};for(@_){for($i=$h;;){$s=(keys%$i)[0];$b=($f-
+>($_,$s)||last)>0?1:0;$i=$i->{$s}[$b]||($i->{$s}[$b]={$_,[0,0]},last)
+}}%$h

    [download]

    Update3: By doing some horrible rearranging in the inner for-loop declaration, I cut to 142. *shudders*

    Update4: After reading jynx's post, I cut the @_ in the assignment to $h. Now 139 characters. 

    $f=shift;$h={pop,[0,0]};for(@_){for($i=$h;$s=(keys%$i)[0];$i=$i->{$s}[
+$b]||($i->{$s}[$b]={$_,[0,0]},last)){$b=(&$f($_,$s)||last)>0?1:0}}%$h

    [download]

    Update5: I promise this is the last! :-) 136 characters, after removing all hashrefs. 

    $f=shift;%h=(pop,[0,0]);for(@_){for(%i=%h;$s=(keys%i)[0];%i=%{$i{$s}[$
+b]||($i{$s}[$b]={$_,[0,0]},last)}){$b=(&$f($_,$s)||last)>0?1:0}}%h

    [download]

    Update6: I lied. *sighs* 130 characters by adding variable aliasing. 

    $f=shift;%h=(pop,[0,0]);for$c(@_){for(%i=%h;$s=(keys%i)[0];){%i=%{$_||
+($_={$c,[0,0]},last)}for$i{$s}[(&$f($c,$s)||last)>0?1:0]}}%h

    [download]

    ------
    We are the carpenters and bricklayers of the Information Age.

    Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

[reply]
[d/l]
[select]
Re: (Golf) Building a Better Binary Tree
by trantor (Chaplain) on Oct 08, 2001 at 19:53 UTC

    Just to get things started...

    However I'm definitely not proud of this code. Whitespace has not been taken out for clarity.

    The function basically outputs the worst possible tree after sorting the array, each left leaf is always 0 and the right is built iteratively, thus not using recursion. Since building strings is much easier than building trees (no pun intended), I did exactly that, evalling the result. It is a hash, not a reference, as the example code seems to suggest. Outputting a ref would allow some more savings :-)

    Warning: for $func to work properly with sort, it should be prototyped:
    my $func = sub($$) { $_[0] <=> $_[1] };

    And now the code: 

    sub buildtree {
        my($f, @a) = @_;
        local $_;

        @a = ((sort $f @a), '');
        $_ = join '=>[0,{', @a;
        chop;
        $_ = '(' . $_ . '0' . ']}' x $#a;
        s/}$/)/;
        eval;
}

    [download]

    It should be 103 chars excluding function declaration and non significative whitespace.

    It can be tested in this context:

    #!/usr/bin/perl -w

use strict;
use Data::Dumper;

sub buildtree {
        my($f, @a) = @_;
        local $_;

        @a = ((sort $f @a), '');
        $_ = join '=>[0,{', @a;
        chop;
        $_ = '(' . $_ . '0' . ']}' x $#a;
        s/}$/)/;
        eval;
}

my @array = ( 6, 1, 2, 3, 4, 5 );
my $func = sub($$) { $_[0] <=> $_[1] };

my %tree = buildtree( $func, @array );

print Dumper \%tree;

    [download]

    Update: In the initial post I forgot to add the character count :-)

    Update 2: After tilly's comment I changed the function so that there's no need to prototypes, and I took some time to compress it further down to 88 chars: 

            #        1         2         3         4
        #23456789012345678901234567890123456789012345
        my$f=shift;@_=((sort{&$f($a,$b)}@_),'');$_=
        join'=>[0,{',@_;chop;%{eval"{$_ 0".']}'x$#_};

    [download]

    -- TMTOWTDI

[reply]
[d/l]
[select]
      The spec did not say you could assume a prototyped comparison function, and the example given in the spec was not prototyped. Therefore I do not consider this a solution. (If we could change conditions, I would love to put the subroutine at the end so I could pop rather than shift. No go.)
[reply]
Re (tilly) 1: (Golf) Building a Better Binary Tree
by Anonymous Monk on Oct 08, 2001 at 20:37 UTC
    54 characters, avoiding the recursive solution. 
    sub h {
#23456789_123456789_123456789_123456789_123456789_1234
$x=0;$s=shift;$x={$_,[$x,0]}for sort{&$s($a,$b)}@_;%$x
}

    [download]
    Those complaining about strict.pm are invited to substitute $a and $b for $x and $s respectively. (Just to demonstrate that becoming strict does not necessarily result in clearer code...)

    UPDATE
    Updated per dragonchild's point about the spec misunderstanding. (How did this get updated? Well let me just say that after conferring with the author of the post, a kind janitor did the favour of editing it...)

[reply]
[d/l]
      Unfortunately, it doesn't work. Easily fixed by changing the last statement to %$x. 54 characters.

      I do have an aesthetic issue with it - your code produces the worst possible tree, not a nearly-optimal tree. :-)

      ------
      We are the carpenters and bricklayers of the Information Age.

      Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

[reply]
[d/l]
      D'oh. That was me.
[reply]

      A question,

      You can eliminate calling $s as a function (and the argument passing) and it will still work for the test cases i've been using. Is there a reason not to do that? That is, is there a reason to use the full function call when passing the function ref will work?

      If you pulled that out, you would get:

      #23456789012345678901234567890123456789012345
$x=0;$s=shift;$x={$_,[$x,0]}for sort$s @_;%$x

      [download]
      at 45 characters.

      jynx

      update: alas, this is a false optimization. Thank you tilly for correcting my eyesight :)

[reply]
[d/l]
        I haven't tested under Perl 5.6, but under 5.005 your code does not work.

        Remember that the comparison function specified depends on the arguments passed to it, and not on $a and $b. Therefore the comparison function is not a valid sort sub and you need to do that transform.

        Try this to see what I mean. 

        print Dumper h(sub {$_[0] <=> $_[1]}, 1..6, -3);

        [download]
        With your code that fails. (BTW your other solution also seems to have used this incorrect optimization.)
[reply]
[d/l]
Re: (Golf) Building a Better Binary Tree
by jynx (Priest) on Oct 09, 2001 at 02:07 UTC

    Here's my go,

    It's strict and warnings compliant. Not a well-adjusted tree, but it's more adjusted than the previous entries:

      #234567890123456789012345678901234567890123456789012345678
  $a=shift;@_=sort$a @_;my%a=(pop,[0,0]);$_=$#_;%a=$_>0?($_[
  $_-1],[0,0],$_[$_--],{%a}):($_[$_],{%a}),$_--while$_>-1;%a

    [download]
    116 characters. Hmm, this isn't nearly as short as it was when it didn't do anything correctly ;-)

    jynx

    update: fixed code to work for base case and sort, modified post to reflect change.

[reply]
[d/l]
      Doesn't every key in the binary tree have to be unique? Yours doesn't do that, given data of 
      ( 2, 1, 3, 4, 7, 6, 5, 4, 3, 2, 7, 9, 5 )

      [download]

      ------
      We are the carpenters and bricklayers of the Information Age.

      Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

[reply]
[d/l]

        i may be wrong but,

        The problem description says that the keys may or may not be distinct. It doesn't say we have to flatten the list to unique keys only. If i'm missing something please tell me, but i don't see where it says we must make the keys unique...

        jynx

[reply]

Back to Meditations