# Perl Weekly Challenge 188.

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

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

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