Perl Weekly Challenge 188.

My solutions (task 1 and task 2 ) to the The Weekly Challenge - 188.

Task 1: Divisible Pairs

Submitted by: Mohammad S Anwar
You are given list of integers @list of size $n and divisor $k.

Write a script to find out count of pairs in the given list that
satisfies the following rules.

The pair (i, j) is eligible if and only if
a. 0 <= i < j < len(list)
b. list[i] + list[j] is divisible by k
Example 1
Input: @list = (4, 5, 1, 6), $k = 2
Output: 2
Example 2
Input: @list = (1, 2, 3, 4), $k = 2
Output: 2
Example 3
Input: @list = (1, 3, 4, 5), $k = 3
Output: 2
Example 4
Input: @list = (5, 1, 2, 3), $k = 4
Output: 2
Example 5
Input: @list = (7, 2, 4, 5), $k = 4
Output: 1

I use combinations from Algorithm::Combinatorics to find all distinct ordered pairs of elements, filter them for divisibility and count them, yielding a compact 1-liner. I assume the input is in @ARGV and contains the divisor followed by the list, which I order before further processing.

perl -MAlgorithm::Combinatorics=combinations -E '
$k=shift; @l=sort @ARGV; say scalar grep {($_->[0]+$_->[1])%$k==0} combinations(\@l,2);
' 2 4 5 1 6
perl -MAlgorithm::Combinatorics=combinations -E '
$k=shift; @l=sort @ARGV; say scalar grep {($_->[0]+$_->[1])%$k==0} combinations(\@l,2);
' 2 1 2 3 4
perl -MAlgorithm::Combinatorics=combinations -E '
$k=shift; @l=sort @ARGV; say scalar grep {($_->[0]+$_->[1])%$k==0} combinations(\@l,2);
' 3 1 3 4 5
perl -MAlgorithm::Combinatorics=combinations -E '
$k=shift; @l=sort @ARGV; say scalar grep {($_->[0]+$_->[1])%$k==0} combinations(\@l,2);
' 4 5 1 2 3
perl -MAlgorithm::Combinatorics=combinations -E '
$k=shift; @l=sort @ARGV; say scalar grep {($_->[0]+$_->[1])%$k==0} combinations(\@l,2);
' 4 7 2 4 5

Results:

2
2
2
2
1

The full code is similar, but uses the iterator version of combinations for the case of a large list.

 1  # Perl weekly challenge 188
 2  # Task 1:  Divisible Pairs
 3  #
 4  # See https://wlmb.github.io/2022/10/25/PWC188/#task-1-divisible-pairs
 5  use v5.36;
 6  use Algorithm::Combinatorics qw(combinations);
 7  die <<EOF unless @ARGV>=3;
 8  Usage: $0 D N1 N2 [N3...]\nto count distinct ordered pairs of integers Ni
 9  that add to a multiple of D
10  EOF
11  my $divisor=shift;
12  my @list=sort @ARGV;
13  my $iter=combinations(\@list, 2);
14  my $count=0;
15  while(my $z=$iter->next){
16      my ($x, $y)=@$z;
17      ++$count if ($x+$y)%$divisor==0;
18  }
19  say "The number of pairs from the list ",
20      join(", ", @ARGV), " with sum divisible by $divisor is $count";

Example:

./ch-1.pl 2    4 5 1 6
./ch-1.pl 2    1 2 3 4
./ch-1.pl 3    1 3 4 5
./ch-1.pl 4    5 1 2 3
./ch-1.pl 4    7 2 4 5

Results:

The number of pairs from the list 4, 5, 1, 6 with sum divisible by 2 is 2
The number of pairs from the list 1, 2, 3, 4 with sum divisible by 2 is 2
The number of pairs from the list 1, 3, 4, 5 with sum divisible by 3 is 2
The number of pairs from the list 5, 1, 2, 3 with sum divisible by 4 is 2
The number of pairs from the list 7, 2, 4, 5 with sum divisible by 4 is 1

Task 2: Total Zero

Submitted by: Mohammad S Anwar
You are given two positive integers $x and $y.

Write a script to find out the number of operations needed to make
both ZERO. Each operation is made up either of the followings:

$x = $x - $y if $x >= $y

or

$y = $y - $x if $y >= $x (using the original value of $x)
Example 1
Input: $x = 5, $y = 4
Output: 5
Example 2
Input: $x = 4, $y = 6
Output: 3
Example 3
Input: $x = 2, $y = 5
Output: 4
Example 4
Input: $x = 3, $y = 1
Output: 3
Example 5
Input: $x = 7, $y = 4
Output: 5

I believe the statement of the problem is wrong, or else, the examples are wrong. In accordance to the examples, I will count the number of steps needed to make any of the arguments zero. This is actually the number of steps required to find the greatest common divisor of the orginal numbers using Euclid’s algorithm vía subtraction. Euclid’s algorithm using integer division could also be used, using the quotients as partial counts to be added. The result fits a one-liner

perl -E '
($c,$x,$y)=(0,@ARGV); while($x>0&&$y>0){($x,$y)=($y,$x) if $y>$x; ($x,$y)=($x-$y, $y); ++$c} say $c
' 4 5
perl -E '
($c,$x,$y)=(0,@ARGV); while($x>0&&$y>0){($x,$y)=($y,$x) if $y>$x; ($x,$y)=($x-$y, $y); ++$c} say $c
' 4 6
perl -E '
($c,$x,$y)=(0,@ARGV); while($x>0&&$y>0){($x,$y)=($y,$x) if $y>$x; ($x,$y)=($x-$y, $y); ++$c} say $c
' 2 5
perl -E '
($c,$x,$y)=(0,@ARGV); while($x>0&&$y>0){($x,$y)=($y,$x) if $y>$x; ($x,$y)=($x-$y, $y); ++$c} say $c
' 3 1
perl -E '
($c,$x,$y)=(0,@ARGV); while($x>0&&$y>0){($x,$y)=($y,$x) if $y>$x; ($x,$y)=($x-$y, $y); ++$c} say $c
' 7 4

Results:

5
3
4
3
5

For the full code I use the division algorithm, which ought to be faster for large numbers.

 1  # Perl weekly challenge 188
 2  # Task 2:  Total Zero
 3  #
 4  # See https://wlmb.github.io/2022/10/25/PWC188/#task-2-total-zero
 5  use v5.36;
 6  use POSIX qw(floor);
 7  die <<EOF unless @ARGV==2;
 8  Usage: $0 x y
 9  To count operations required to bring x or y to zero by succesive subtraction.
10  EOF
11  my ($counter, $actual)=(0, 0);
12  my ($x, $y)=my($x0, $y0)=@ARGV;
13  die "Only positive integers allowed" unless $x>0 and $y>0 and $x==floor $x and $y==floor $y;
14  use integer;
15  while($y>0){
16      my ($d, $r)=($x/$y, $x%$y);
17      $counter += $d;
18      ++$actual;
19      ($x, $y)=($y, $r);
20  }
21  say "The number of operations required to bring $x0 $y0 to zero is $counter (divisions: $actual)";

Examples:

./ch-2.pl 5 4
./ch-2.pl 4 6
./ch-2.pl 2 5
./ch-2.pl 3 1
./ch-2.pl 7 4
./ch-2.pl 1024 513

Results:

The number of operations required to bring 5 4 to zero is 5 (divisions: 2)
The number of operations required to bring 4 6 to zero is 3 (divisions: 3)
The number of operations required to bring 2 5 to zero is 4 (divisions: 3)
The number of operations required to bring 3 1 to zero is 3 (divisions: 1)
The number of operations required to bring 7 4 to zero is 5 (divisions: 3)
The number of operations required to bring 1024 513 to zero is 259 (divisions: 4)

I threw a counter of divisions and a larger example to compare it to the count of subtractions. It may be off by one, unless I order x and y before starting.

Written on October 25, 2022