PWC 251

PWC 251

This time I tried both challenges using antique software on DOSBOX: Perl 4.019 for DOS, and for comparison Python 1.4 beta for DOS. My solutions also run on the current versions of Perl 5 (5.38) and Python 2 (2.7.18). Hooray for backward compatibility!

Challenge 1 (Concatenation Value)

Links to solution: Perl Python

We are given a list of positive integers, say ints. We are asked to follow the following procedure:

  • Concatenate ints[0] and ints[-1] (last element). Store the result in retval say.
  • Concatenate ints[1] and ints[-2] (second-last element), and add the result to retval.
  • Concatenate ints[2] and ints[-3] .... etc. until we have reached the middle of the list.
  • Return retval.

Here is the Perl 4.019 subroutine (it also works fine on the latest Perl 5.38).

sub concatenation_value {
  local(@ints)=@_;
  local($x,$retval)=(0,0);
  foreach $x (0 .. @ints/2-1) {
   $retval += $ints[$x] . $ints[$#ints-$x];
  }
  (@ints % 2) && ($retval += $ints[$#ints/2]);
  return $retval;
}

We loop through the list concatenating items as described above. If there is an odd number of items, there is an extra step to add the single item in the middle of the list.

Here is the equivalent Python 1.4b code. (It also runs fine on Python 2.7.18, though not on Python 3 of course.) We need to explicitly convert the numbers to strings before concatenating, and then we need to explicitly convert the concatenated numbers from string to integer using the string.atoi method when updating retval. (In later python versions, we can just use int(strval), but that was not possible in 1.4b and gives a syntax error.)

def concatenation_value( ints ):
  retval=0
  for i in range(int(len(ints)/2)):
    concat = str(ints[i])+str(ints[len(ints)-i-1])
    retval = retval+string.atoi(concat)
  if ((len(ints) % 2) ==1):
    retval = retval + ints[ len(ints)/2 ]
  return retval

Challenge 2 (Lucky Numbers)

Links to solution: Perl Python

We are given a matrix (array of equal-length arrays) consisting of distinct numbers (no number repeated). We are asked to find a matrix element such that it is simultaneously the highest in its column and the lowest in its row. If there is no such element, we return -1.

The python code is easier as an array of arrays is directly available even in this early version. Here is my python function:

def lucky_numbers( inmatrix ):
  retval=-1;
  ncol=len(inmatrix[0])
  nrow=len(inmatrix)
  for y in range(nrow):
    for x in range(ncol):
      if (inmatrix[y])[x]==max(column(inmatrix,x)) == min(inmatrix[y]):
        retval = (inmatrix[y])[x]
        break
  return retval

We loop through the matrix cells looking for a matrix entry that meets the condition. If we find one, we break out of the loop and return the item. Otherwise, we return -1.
 
I use a home-made function to extract columns from the matrix.
 
def column( inmatrix, colno ):
  retval=[]
  for y in range(len(inmatrix)):
    retval.append( (inmatrix[y])[colno] )
  return retval
 
Given a matrix and a column number, we loop through rows extracting each row element at that column. 

The python code also runs with no modification needed on Python 2.7.18.

Perl 4.019 needs more work, as we need to DIY matrices and min and max functions. I follow the traditional Perl 4 approach of using a hash to represent a multi-dimensional array where hash{"row,col"} represents the entry at row number row and column number col. Here is my DIY matrix creation routine, as well as DIY routines to extract columns and rows. The variables nrow and ncol are the number of rows and columns respectively, and @data contains the matrix data as a flat list.

sub matrix {
 local ($nrow, $ncol, @data)=@_;
 (scalar(@data)==$nrow*$ncol) || die "Matrix data input error: $!\n";

 local (%matrix,$y,$x);
 foreach $y (0 .. $nrow-1){
  foreach $x (0 .. $ncol-1){
    $matrix{ "$y,$x" } = shift(@data);
  }
 }
 %matrix;
}

sub column {
 local ($colno, %matrix)=@_;
 local (@column) = @matrix { grep( $_ =~ /,$colno/, keys %matrix) };
 @column;
}

sub row {
 local ($rowno, %matrix)=@_;
 local (@row) = @matrix { grep( $_ =~ /^$rowno,/, keys %matrix) };
 @row;
}


Here is the lucky numbers subroutine. Like the python code, it loops through cells until it finds an element that satisfies the criterion. To find min and max, we sort the relevant row or column in ascending or descending order as needed, and take the first element from the sorted row or column.

sub lucky_numbers {
 local ($nrow, $ncol)=($_[0], $_[1]);
 local (%matrix)=&matrix(@_);
 local ($y, $x,$retval);
 $retval=-1;
 OUTER: foreach $y (0 .. $nrow-1) {
  INNER: foreach $x (0 .. $ncol-1) {
   local ($rowmin)=((sort {$a<=>$b;} &row($y, %matrix))[0]);
   local ($colmax)=((sort {$b<=>$a;} &column($x, %matrix))[0]);
   if (($matrix{"$y,$x"}==$rowmin) && ($matrix{"$y,$x"}==$colmax)) {
    $retval = $matrix{"$y,$x"};
    last OUTER;
   } #if
  } #INNER
 } #OUTER
 $retval;
}

Notice the semi-colon in the sort algorithm {$a<=>$b;}. This could be left out in modern Perl, but you get a syntax error if you do that in Perl 4.019.
 
The script also works fine on the latest Perl 5.38, though of course there are better ways to do this in modern Perl, such as using PDL.

Comments

Popular posts from this blog

PWC 258

PWC 249

PWC 253