Advent Calendar - December 1, 2023

Friday, Dec 1, 2023| Tags: Perl, Raku

|   Day 1   |   Day 2   |

The gift is presented by `Laurent Rosenfeld`. Today he is talking about his solution to The Weekly Challenge - 205. This is re-produced for `Advent Calendar 2023` from the original post.

``````You are given an array of integers.

Write a script to find out the Third Highest if found otherwise return the maximum.

Example 1

Input: @array = (5,3,4)
Output: 3

First highest is 5. Second highest is 4. Third highest is 3.

Example 2

Input: @array = (5,6)
Output: 6

First highest is 6. Second highest is 5. Third highest is missing, so maximum is returned.

Example 3

Input: @array = (5,4,4,3)
Output: 3

First highest is 5. Second highest is 4. Third highest is 3.
``````

Third Highest in Raku

The `third-largest` subroutine first sorts the input in descending order and then returns the third or the first item, depending on whether there are three items or more in the input, or less than that.

``````sub third-largest (@in) {
my @s = @in.sort.reverse;
return @s.elems >= 3 ?? @s[2] !! @s[0];
}
for <5 3 4>, <5 6>, <5 4 4 3>, <5 6 7 8 2 1> -> @test {
say (~@test).fmt("%-12s => "), third-largest @test;
}
``````

With large lists, using the sort routine may not be the most efficient solution in terms of performance (speed). However, in my humble opinion, this solution is better in terms of coding efficiency, because finding manually the third-largest item would require some form of circular buffer of the three largest elements, making the code significantly longer. Actually, the third-largest subroutine could boil down to a single line of code:

``````return @in.elems >= 3 ?? @in.sort[*-3] !! @in.sort[*-1];
``````

but I did not do it, because it would lead to repeat the sorting statement, which is not the best programming practice.

This program displays the following output:

``````\$ raku ./third-largest.raku
5 3 4        => 3
5 6          => 6
5 4 4 3      => 4
5 6 7 8 2 1  => 6
``````

Third Highest in Perl

This is port to Perl of the above Raku program:

``````use strict;
use warnings;
use feature "say";

sub third_largest  {
my @s = sort {\$b <=> \$a} @_;
return scalar @s >= 3 ? \$s[2] : \$s[0];
}
for my \$t ([<5 3 4>], [<5 6>], [<5 4 4 3>],
[<5 6 7 8 2 1>]) {
printf "%-12s => %d \n", "@\$t", third_largest @\$t;
}
``````

The comments about efficiency made in the `Raku` section above also apply to this `Perl` implementation.

This program displays the following output:

``````\$ perl ./third-largest.pl
5 3 4        => 3
5 6          => 6
5 4 4 3      => 4
5 6 7 8 2 1  => 6
``````

``````You are given an array of integers.

Write a script to find the highest value obtained by XORing any two distinct members of the array.

Example 1

Input: @array = (1,2,3,4,5,6,7)
Output: 7

The maximum result of 1 xor 6 = 7.

Example 2

Input: @array = (2,4,1,3)
Output: 7

The maximum result of 4 xor 3 = 7.

Example 3

Input: @array = (10,5,7,12,8)
Output: 7

The maximum result of 10 xor 5 = 15.
``````

First, there is a mistake in `Example 3`: the output should be 15, as shown in the output explanation. That’s just a typo.

We have another somewhat more serious problem. There is a `xor` operator both in `Raku` and in `Perl`. Both are actually logical operators. In `Perl`, for example, `“binary ‘xor’ returns the exclusive-OR of the two surrounding expressions.”` Looking at the examples provided, we can see that this is not the desired behavior. Obviously, what is wanted is the `bit-wise xor`, which is written `+^` in `Raku` and `^` in `Perl`.

Maximum Bit-Wise XOR in Raku

The `largest-xor` subroutine uses the built-in combinations routine to test all input-array two-items combinations and returns the highest value obtained (together with the first combination that led to that value).

``````sub largest-xor (@in) {
my \$max = 0;
my \$max-i;
for @in.combinations(2) -> \$i {
my \$xor = \$i[0] +^ \$i[1];   # bitwise xor
\$max = \$xor and \$max-i = \$i if \$xor > \$max
}
return "\$max-i -- \$max";
}

for (1,2,3,4,5,6,7), (2,4,1,3), (10,5,7,12,8) -> @test {
say (~@test).fmt("%-15s => "), largest-xor @test;
}
``````

This program dispàlays the following output:

``````\$ raku ./max-xor.raku
1 2 3 4 5 6 7   => 1 6 -- 7
2 4 1 3         => 4 3 -- 7
10 5 7 12 8     => 10 5 -- 15
``````

Maximum Bitwise XOR in Perl

This `Perl` implementation uses the same approach as the `Raku` program above, except that we find all 2-item combinations with two nested for loops, as there is no built-in combinations routine in core `Perl`.

``````use strict;
use warnings;
use feature "say";

sub largest_xor {
my \$max = 0;
my @max_ij;
for my \$i (0..\$#_) {
for my \$j (\$i+1.. \$#_) {
my \$xor = \$_[\$i] ^ \$_[\$j];    # bitwise xor
if (\$xor > \$max) {
\$max = \$xor;
@max_ij = (\$_[\$i], \$_[\$j]) ;
}
}
}
return "@max_ij -- \$max";
}

for my \$t ([1,2,3,4,5,6,7], [2,4,1,3], [10,5,7,12,8]) {
printf "%-15s => %-10s \n", "@\$t", largest_xor @\$t;
}
``````

This program displays the following output:

``````\$ perl  ./max-xor.pl
1 2 3 4 5 6 7   => 1 6 -- 7
2 4 1 3         => 4 3 -- 7
10 5 7 12 8     => 10 5 -- 15
``````

If you have any suggestion then please do share with us perlweeklychallenge@yahoo.com.

SO WHAT DO YOU THINK ?

If you have any suggestions or ideas then please do share with us.