April 2020 Archives

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!

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

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.


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.

the Giant Planet of Perl

Finally I saw posts of PWC#056 on blogs.perl.org .

I haven't found what to discuss about #056 Task #1. Just to keep people know this code producer is alive and healthy, I share my recent life:

On Perl resources:

1. Perl Monks

From a blogpost[1], I was hooked to https://www.perlmonks.com/ . Apart from many advanced Perl discussions, there is a book review section (not very active):

Book Reviews of Perl Monks

Yesterday I got…

CY's take Perl Weekly Challenge on #055

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

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

named.jpg

Oh.

/users/c_y_fung/2020/04/index.html

CY's take on PWC#054

This is a part of Perl Weekly Challenge(PWC) #054 and the followings are related to my solution. If you want to challenge yourself on Perl, go to https://perlweeklychallenge.org, code the latest challenges, submit codes on-time (by GitHub or email) if possible, before reading my blog post.


Apr03_2020.png

My laptop spent about 40.5 hours for calculating the list for the extra credit in task #2. While it was calculating, I found that my code hadn't been optimized. Anyway, even if I optimized it by 50%, the wait of 20 hours could still be a record for an impatient and blunt person like me.

2nd Apr, 2020
time | number_reached
1427 1
1745 309560
1809 325441
1831 339572
1852 353486
1951 386882
2205 453250
2253 475841
2308 482951
2358 502248

3rd Apr, 2020
time | number_reached
0419 600125
1405 772771
1534 794982
1538 796651
1543 798343
1555 800112 At this point, I realized that I should do more optimization.
1558 801872
1607 803625
1630 808808
1724 822777
1730 824482
1955 859075

4th Apr, 2020
time | number_reached
0519 980874
0636 994616
0653 1000000

Being afraid of losing the data, I did not use the laptop for other tasks. And, I am living in a hostel-like environment; continuous occupying the electrical plug is not a sensible action. Luckily the staff of my room is sensible enough...

Binary_tree.png

I want to implement a binary tree for the integers, such that, for instance, I want to list the sequence for 13, the program can just trace the "ancestries". However, I am not good at handling references. I kept puzzled with my codes. No codes to be provided in blogpost this week.

(After having the list, I am going to use selection algorithm to get the top 20 "drunkers".)

--
Some feedback on my performance/blogpost PWC#053:

  • I was having indulgence of bad(unedited) script of "the simple verison" in the task #1.
  • $class = $module = $package   in OO sense... (ref: Section 1.3, "Object Oriented Perl" by Damian Conway)
  • Though reading others' code, there is an easy way put the module inside a script:

instead of

#!/usr/bin/perl
use strict;
use xy.pm; #require the user inconveniently
#put the module in the right directory
# inside his/her disk

we can just do

#!/usr/bin/perl
use strict;
{
package xy;

sub new {
my ($class) = @_;
bless{
_value=> $_[1],
_x=>$_[2],
_y=>$_[3],
}, $class;
}

sub #...
}

Anyway, I found I have devoted more and more time on PWC and Perl. Well, on the positive side: I can learn to be a good coder sooner.


My scirpts is on https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-054/cheok-yin-fung/perl

About C.-Y. Fung

user-pic This blog is inactive and replaced by https://e7-87-83.github.io/coding/blog.html ; but I post highly Perl-related posts here.