The Weekly Challenge ‐ Perl and Raku

CY's Take on The Weekly Challenge #113

If you want to challenge yourself on programming, especially on Perl and/or Raku, go to https://perlweeklychallenge.org, code the latest challenges, submit codes on-time (by GitHub or email).

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

It's time for challenges in Week #113 !

---

Task 1: Represent Integer

An important assertion is: for a non-zero digit $D, any positive integers larger than or equal to $D*10 can be represented in the way specific in the task statement. This comes from modulo arithmetic or mathematical induction, whatever.

For a positive integer smaller than $D*10, there are two very similar ways to determine whether it is "representable":

sub step_down {
    # Example   I: if N = 82, D = 9, it hints 82 = 9*7+19
    # Example  II: if N = 64, D = 7, it hints 64 = 7*1+57
    # Example III: if N = 30, D = 8, the set {8, 18, 28} ...
    # Example  IV: if N = 44, D = 6, it hints 44 = 6*3+26
    my $digit = $_[0];
    my $short = $_[1];
    my $temp_short = $short;
    do {
        return 1 if $temp_short =~ /$digit/;
        $temp_short -= $digit;
    } while ($temp_short > 0);   
    return 0;
}

sub last_digit {
    # Example   I: if N = 82, D = 9, it hints 82 = 72+10 = 9*8+10 = 9*7+19
    # Example  II: if N = 64, D = 7, it hints 64 = 14+50 = 7*2+50 = 7*1+57
    # Example III: if N = 30, D = 8, the set {8, 18, 28} ...
    # Example  IV: if N = 44, D = 6, it hints 44 = 24+20 = 6*4+20 = 6*3+26
    my $digit = $_[0];
    my $short = $_[1];
    my $last_digit_of_short = $short % 10;
    my $i = 1;
    while ($digit*$i < $short) {
        if ($digit*$i % 10  == $last_digit_of_short ) {
            return 1;
        }
        $i++;
    }
    return 0;
}

Let us do some optimization according to the fact that the base is 10:

sub representable {
    #...
    return 1 if $N >= 10*$D;   


    return 1 if $N % $D == 0;  # $N = $D + $D + ... + $D, esp $D == 1
    return 0 if $D == 2 || $D == 5;


    if ($D == 4 && $N > 10) {
        return $N % 2 == 0 ? 1 : 0;
    }

    if ($D == 8 && $N >= 40) {
        return $N % 2 == 0 ? 1 : 0;
    }

    if ($D == 6) {
        return 0 if $N % 2 != 0;
    }

    # call &step_down or &last_digit...
}

The math of "representable number" in an arbitary base has certain interesting mathematical properties and I am stil exploring them. What kinds of interesting properties? For example, in base-10, for digits $D coprime to 10 (i.e. 3, 7 and 9), the number of "representable" positive integers smaller than $D*10 is (10-1)*($D+1)/2:

• 3: 3, 6, 9, 12, 13, 15, 16, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29 (18 terms);
• 7: 7, 14, 17, 21, 24, 27, 28, 31, 34, 35, 37, 38, 41, 42, 44, 45, 47, 48, 49, 51, 52, 54, 55, 56, 57, 58, 59, 61, 62, 63, 64, 65, 66, 67, 68, 69 (36 terms);
• 9: 9, 18, 19, 27, 28, 29, 36, 37, 38, 39, 45, 46, 47, 48, 49, 54, 55, 56, 57, 58, 59, 63, 64, 65, 66, 67, 68, 69, 72, 73, 74, 75, 76, 77, 78, 79, 81, 82, 83, 84, 85, 86, 87, 88, 89 (45 terms).

For completeness, note that the handle of the case of $D = 0, is return 1 if $N >= $base*$base; return $N % $base == 0 ? 1 : 0; .

Task 2: Recreate Binary Tree

Firstly, take an assumption that the input are integers. But the task statement does not specific whether zero and/or negative numbers are allowed, hence for the null nodes, we can't set them as 0 or -1. Luckily, we have undef in Perl.

Among the possible data structures for getting the sum of the values in nodes of a binary tree, "an implicitly breadth-first orderred one-dimensional array"(paraphrased from Wikipedia) should be the easiest to implement.

Another advantage of this data structure is that it is easy to input:

# Usage: ch-2.pl [binary tree in array format, 'x' for null nodes]

my @tree = map { $_ eq 'x' ? undef : $_ } @ARGV;

my $sum = 0;

for (@tree) {
    $sum += $_ if defined($_);
}

for (@tree) {
    $_ = $sum - $_ if defined($_);
}

print_tree(@tree);

Using the example in the task statement, we have:

$ perl ch-2.pl 1 2 3 4 x 5 6 x 7
27 26 25 24 x 23 22 x 21 

After the first round of coding, I felt a bit bored. Why not provide a hash of hashes implementation for the binary trees? I hadn't done that before. Look at the history of submission; the closest thing I had done is the nested array implementation(Week #057) for the binary trees. I have typed Java and OO stuff so hard recently that it took some time for me to code out the hash of hashes:

sub tree_build {        # use for print_pretty_tree
    my @t = @{$_[0]};
    my $ind = $_[1]; 
    my %leaf = ( "v" => $t[$ind] );
    $leaf{"l"} = tree_build(\@t, $ind*2+1) 
        if defined($t[$ind*2+1]);
    $leaf{"r"} = tree_build(\@t, $ind*2+2) 
        if defined($t[$ind*2+2]);
    return \%leaf;
}

And just like what I did in Week #057, I ask Data::Dumper for output:

sub print_pretty_tree {
    my @tr = @_;
    my $hash_tree = tree_build( \@tr, 0);

    $Data::Dumper::Terse = 1; 
    $Data::Dumper::Indent = 2;
    $Data::Dumper::Sortkeys = 1;
    print "\n"; 
    print "Output in Hash Format:\n";
    print Dumper $hash_tree; 
}

The updated result is:

$ perl ch-2.pl 1 2 3 4 x 5 6 x 7
Output in Array Format:
27 26 25 24 x 23 22 x 21 

Output in Hash Format:
{
  'l' => {
           'l' => {
                    'r' => {
                             'v' => 21
                           },
                    'v' => 24
                  },
           'v' => 26
         },
  'r' => {
           'l' => {
                    'v' => 23
                  },
           'r' => {
                    'v' => 22
                  },
           'v' => 25
         },
  'v' => 27
}

---

Stay alert and healthy! □

link for full codes: ch-1.pl, ch-2.pl

---

Contact on twitter: @e7_87.

Created Date: 19th May, 2021; last updated: 20th May, 2021 05:09 HKT