Moments on Perl or other Programming Issues

This is a part of Perl Weekly Challenge(PWC) #057 and the followings are related to my solution.

Do tell me if I am wrong or you strongly oppose my statements!

Task 1: Invert Tree

There is a module Tree::Binary on CPAN and its method "mirror" does what exactly describe in the Task 1. Of course, the experience of using a shortcut won't be filled a blog post.

Last week (PWC #056) I did not attempt the binary tree task but I did read the blogs of other PWC members.

Hence, it's time for my "blog report". Blog posts I use as reference are

• https://ry.ca/2020/04/path-sum/
• https://raku-musings.com/diff-sum.html
• https://blogs.perl.org/users/laurent_r/2020/04/perl-weekly-challenge-56-diff-k-and-path-sum.html

Discovered from reading, one of the ways of representing a binary tree which I hadn't thought of but very intuitive, is putting the nodes row by row!

Just like this:

( [5], [4,8], [11, 14, 13, 9],
[7, 2, 141, 142, 6, 5, 5, 1] );

Using this representation, it is very easy to invert the tree. Just swap the elements.

sub swaprowformtree {
    my @btree = @_;
    my $N = $#btree;
    for my $i (1..$N) {
        for my $j (0..2**($i-1)-1) {
            ($btree[$i][$j], $btree[$i][2**($i)-1-$j])
            = ($btree[$i][2**($i)-1-$j], $btree[$i][$j]);
        }
    }

    return @btree;
}

(May I name this "row form" of binary tree representation.)

The two most common ways are using nested array and using nested hash. I have implemented the nested array form.

The details of scripting is, again, transformation and reverse transformation!

To be lazy, I use Data::Dumper to output the binary tree:

use Data::Dumper;

...

$Data::Dumper::Terse = 1; 
$Data::Dumper::Indent = 0;

print Dumper rowform_transform_array swaprowformtree @ro_tree1;

where @ro_tree1 is the product of these codes:

my @ro_tree1;

sub array_transform_rowform {

    my ($h, $val, @kids) = @_;
    if (! defined(@ro_tree1[$h])) {    
        @{$ro_tree1[$h]} = ();
    }
    push @{$ro_tree1[$h]}, $val; 

    if ($kids[0]) {
        my ($temp, @smallkids) = @{kids[0]};
        array_transform_rowform($h+1, shift @{$kids[0]}, @{$kids[0]});
    } 
    if ($kids[1]) {
        my ($temp, @smallkids) = @{kids[1]};
        array_transform_rowform($h+1, shift @{$kids[1]}, @{$kids[1]});
    }

}

sub rowform_transform_array {
    my @rowform = @_;
    my $height = $#rowform;
    my @data = ();
    for (0..2**$height-1) { push @data, [ $rowform[$height][$_] ];  }
    for my $i (reverse 1..$height-1) {
        my @newdata = ();
        for my $j (0..2**$i-1) {
            $newdata[$j] = CombineTwo($data[$j*2], $data[$j*2+1]);
            unshift @{$newdata[$j]}, $rowform[$i][$j];
        }
        for my $j (0..2**($i-1)) {$data[$j] = $newdata[$j];}
    }
    return [$rowform[0][0], $data[0], $data[1]] ;
}

sub CombineTwo {
    my @temp = ($_[0], $_[1]);
    return \@temp;
}

Task 2: Shortest Unique Prefix

With sorting, this task doesn't seem difficult, so I try on it.

This is my first time to use dualvar in Scalar::Util. It is quite a funny construct. I use it to keep the order of the provided list.

Its official description is: " my $var = dualvar( $num, $string ); # Returns a scalar that has the value $num in a numeric context and the value $string in a string context." ^[source] The funny thing about it is we ask for its numeric value by $var+0, and ask for its string value by "$var".

There should be many ways and tricks on manipulations sorting on hashes. As a dessert of the post, visit Tutorial section of Perl Monks I read today and see the trick of "||" with uc($a) cmp uc($b), written by Our Respected davido in 2003. (Being extraordinarily formal seems like the culture of PM; unable to follow yet.) Time for the end of this blog.

Stay healthy and alert! □

My code can be found in  GitHub.