# 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 !

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 = \$_;
my \$short = \$_;
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 = \$_;
my \$short = \$_;
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 = @{\$_};
my \$ind = \$_;
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
}```