CY's take on Perl Weekly Challenge #057

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!

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

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+1shift @{\$kids[0]}, @{\$kids[0]});
}
if (\$kids[1]) {
my (\$temp@smallkids) = @{kids[1]};
array_transform_rowform(\$h+1shift @{\$kids[1]}, @{\$kids[1]});
}

}

Actually the transformations between nested array and row form is the most difficult part of the coding for me this week.

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;
}

I would like to implement the nested hash if I had more spare time.

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.