Perl Weekly Challenge 140.

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

Task 1: Add Binary

Submitted by: Mohammad S Anwar
You are given two decimal-coded binary numbers, $a and $b.

Write a script to simulate the addition of the given binary
numbers.

The script should simulate something like $a + $b. (operator
overloading)

Example 1
Input: $a = 11; $b = 1;
Output: 100
Example 2
Input: $a = 101; $b = 1;
Output: 110
Example 3
Input: $a = 100; $b = 11;
Output: 111

I split the bits and pipe them through a full adder that takes two bits and a carry bit, and produces a one bit sum and a new carry bit, yielding the following illegible three-liner. I add a leading 0 to each number for the case the result requires more bits than the operands, i.e., to add to the last carry bit.

perl -Minteger -MList::MoreUtils=pairwise -E '($x,$y)=map [reverse split "","0$_"],
   @ARGV; @x=@$x;@y=@$y; say sprintf "Input: \$a=%d, \$b=%d, Output: %d", @ARGV,
   join "",reverse pairwise {$c=($s=$a+$b+$c)/2;$r=$s%2} @x,@y;' 11 1
perl -Minteger -MList::MoreUtils=pairwise -E '($x,$y)=map [reverse split "","0$_"],
   @ARGV; @x=@$x;@y=@$y; say sprintf "Input: \$a=%d, \$b=%d, Output: %d", @ARGV,
   join "",reverse pairwise {$c=($s=$a+$b+$c)/2;$r=$s%2} @x,@y;' 101 1
perl -Minteger -MList::MoreUtils=pairwise -E '($x,$y)=map [reverse split "","0$_"],
   @ARGV; @x=@$x;@y=@$y; say sprintf "Input: \$a=%d, \$b=%d, Output: %d", @ARGV,
   join "",reverse pairwise {$c=($s=$a+$b+$c)/2;$r=$s%2} @x,@y;' 100 11

Results:

Input: $a=11, $b=1, Output: 100
Input: $a=101, $b=1, Output: 110
Input: $a=100, $b=11, Output: 111

The full version is

# Perl weekly challenge 140
# Task 1: Add Binary
#
# See https://wlmb.github.io/2021/11/23/PWC140/#task-1-add-binary
use v5.12;
use warnings;
use integer;
use List::Util qw(all max);

my $word_size=8; # finite number of bits, to allow for negative 2s-complement numbers.
say("Usage: ch-1.pl a b [wordsize], to add two binary numbers"), exit unless @ARGV>=2;
say("Only '0' and '1' allowed for binary numbers"), exit unless all {$_=~m/^[01]+$/} @ARGV[0,1];
say("Word size should be positive"), exit unless !defined $ARGV[2] || $ARGV[2]>=1;
my ($x, $y)=map {[reverse (0,split "",$_)]} @ARGV; # bit arrays, least significant first
$word_size=$ARGV[2] if $ARGV[2];
my $length=max scalar @$x, scalar @$y;
my $carry=0;
my $r;
my @result=map {($r,$carry)=full_adder($x->[$_],$y->[$_],$carry);$r} 0..$length-1;
splice @result, $word_size; # truncate to maximum number of bits
my $result=join "", reverse @result;
say sprintf "Input: \$a=%d, \$b=%d, Output: %d", @ARGV[0,1], $result;

sub full_adder{ # add two bits and a carry, produce result and carry
    my ($a, $b, $c)=@_;
    return(($a+$b+$c)%2,($a+$b+$c)/2);
}

I included a finite (smallish) word size, in order to check the program with negative numbers using 2s-complements.

Examples:

./ch-1.pl 11 1
./ch-1.pl 101 1
./ch-1.pl 100 11

Results:

Input: $a=11, $b=1, Output: 100
Input: $a=101, $b=1, Output: 110
Input: $a=100, $b=11, Output: 111

Examples with 4 bit negative numbers:

./ch-1.pl 1111 1111 4
./ch-1.pl 0 1111 4
./ch-1.pl 1 1111 4
./ch-1.pl 11 1100 4

Results:

Input: $a=1111, $b=1111, Output: 1110
Input: $a=0, $b=1111, Output: 1111
Input: $a=1, $b=1111, Output: 0
Input: $a=11, $b=1100, Output: 1111

These results may be read as -1-1=-2, 0-1=-1, 1-1=0, 3-4=-1.

TASK #2 › Multiplication Table

Submitted by: Mohammad S Anwar
You are given 3 positive integers, $i, $j and $k.

Write a script to print the $kth element in the sorted
multiplication table of $i and $j.

Example 1
Input: $i = 2; $j = 3; $k = 4
Output: 3

Since the multiplication of 2 x 3 is as below:

    1 2 3
    2 4 6

The sorted multiplication table:

    1 2 2 3 4 6

Now the 4th element in the table is "3".
Example 2
Input: $i = 3; $j = 3; $k = 6
Output: 4

Since the multiplication of 3 x 3 is as below:

    1 2 3
    2 4 6
    3 6 9

The sorted multiplication table:

    1 2 2 3 3 4 6 6 9

Now the 6th element in the table is "4".

This job is very simple using the Perl Data Language (PDL), as it has functions and methods like

  • zeroes($j,$i) to make a table with $i rows and $j columns,
  • ndcoords to produce a vector whose components are the coordinates of each entry in the table, i.e., making a 3D array whose $a,$n,$m-th entry is the $a-th coordinate of the $n,$m-th entry, i.e., either $n or $m, pretty useful although confusing at first,
  • prodover to multiply the elements of a vector, and
  • flat to convert a table into a vector, and
  • qsort to perform a quick-sort a vector.

Thus a one-liner solution is

perl -MPDL -MPDL::NiceSlice -E '($i,$j,$k)=@ARGV; say "i=$i, j=$j, k=$k, out=",
     (zeroes($j,$i)->ndcoords+1)->prodover->flat->qsort->(($k-1))' 2 3 4
perl -MPDL -MPDL::NiceSlice -E '($i,$j,$k)=@ARGV; say "i=$i, j=$j, k=$k, out=",
     (zeroes($j,$i)->ndcoords+1)->prodover->flat->qsort->(($k-1))' 3 3 6

Results:

i=2, j=3, k=4, out=3
i=3, j=3, k=6, out=4

The full version follows.

# Perl weekly challenge 140
# Task 2: Multiplication Table
#
# See https://wlmb.github.io/2021/11/23/PWC140/#task-2-multiplication-table
use v5.12;
use warnings;
use integer;
use PDL;
use PDL::NiceSlice;

say("Usage: ./ch-2.pl i j k to get the k-th element of an iXj multiplication table"),
    exit unless @ARGV==3;
my($i, $j, $k)=@ARGV;
say("i and j should be positive"), exit unless $i>=1 && $j>=1;
say("k should be positive and not greater than iXj"), exit unless 1<=$k<=$i*$j;

my $result=(
    my $sorted=(
	my $table=(zeroes($j,$i)->ndcoords+1)->prodover
        )->flat->qsort
    )->(($k-1));
say "Input: i=$i, j=$j, k=$k,\nOutput=$result",
	    "\nsince the ${i}X$j multiplication table is",
    $table, "which sorted becomes\n$sorted,\nwhose $k-th element is $result\n";

Examples:

./ch-2.pl 2 3 4
./ch-2.pl 3 3 6

Results:

Input: i=2, j=3, k=4,
Output=3
since the 2X3 multiplication table is
[
 [1 2 3]
 [2 4 6]
]
which sorted becomes
[1 2 2 3 4 6],
whose 4-th element is 3

Input: i=3, j=3, k=6,
Output=4
since the 3X3 multiplication table is
[
 [1 2 3]
 [2 4 6]
 [3 6 9]
]
which sorted becomes
[1 2 2 3 3 4 6 6 9],
whose 6-th element is 4
Written on November 23, 2021