PWC 256

I do both challenges in perl 4.019 on DOSBOX. For comparison, I also do them in python 1.4 beta on DOSBOX. My perl and python solutions to both challenges also run fine on the current versions of Perl 5 (5.8) and Python 2 (2.7.18).

Challenge 1 (Maximum Pairs)

Links: PERL4.019 PYTHON1.4b

We are given a list of strings. We are asked to count how many pairs of the form (string, reverse(string)) we can form from the elements of the list.

In perl 4, I use a single pass through the list that does the following:

1. For each element, check if I have seen the reverse of that element before. (I use a hash called %seen to track this).
2. If I have seen the reverse before:
1. Count one more pair of conformant elements (I increment a counter called $count.)
2. Reset the hash entry for the reverse of the element to be 0 or false (to prevent for example ('ab','ba','ba') from being counted as two pairs instead of one).
3. If I have not seen the reverse before, I just update %seen to record that I have seen the current element, and move on.

Here is the subroutine:

sub maximum_pairs {
 local(%seen,$count,$i);
 $count=0;
 for $i (@_){
  if ( $seen{ reverse($i) } ) {
   $count++;
   $seen{ reverse($i) } = undef;
  }
  else {
   $seen{$i}=1;
  }
 }
 $count;
}

I translate this code directly into python 1.4 beta:

def maximum_pairs( words ):
 seen={}
 count=0
 for i in words:
  rev_i=list(str(i))
  rev_i.reverse()
  rev_i=string.joinfields( rev_i, "" )
  if seen.has_key(rev_i) and seen[rev_i]==1:
   count=count+1
   seen[rev_i]=0
  else:
   seen[i]=1
 return count

In python, strings are immutable. To get the reverse of a string is a three-line chore: first split the string element using list(.), then reverse the list thus obtained using the reverse method, and finally join the reversed list elements back into a string using the string.joinfields() function.

Minor point: Hashes are called "associative arrays" in perl 4, and "dictionaries" in python of any flavor. Let's just call them hashes.

Challenge 2 (Merge Strings)

Links: PERL4.019 PYTHON1.4b

We are given two strings say str1 and str2. We are asked to return a string that zips them, i.e., returns str1[0].str2[0].str1[1].str2[1]...  When we reach the end of the shorter string, we just append the remaining portion of the longer string.

That task description pretty much describes the algorithm. In perl 4, I split the strings so that I loop through lists (calling list[i]) instead of strings (calling substr(string,i,1)). This is because Programming perl 1e recommends avoiding the substr(.) operator inside a loop.

Here is my perl 4 subroutine:

sub merge_strings {
 local( @str1 ) = split(//,$_[0]);
 local( @str2 ) = split(//,$_[1]);
 local($max_len)= (($#str1 > $#str2) ? $#str1 : $#str2);
 local( @retval )=();
 local( $i );
 foreach $i (0 .. ($max_len)){
  defined($str1[$i]) && push( @retval, $str1[$i] ) ;
  defined($str2[$i]) && push( @retval, $str2[$i] ) ;
 }
 join( "", @retval);
}

For this challenge compared to challenge 1, the python 1.4 beta implementation is tidier than perl 4, because it can be done without splitting the input strings. We don't care that they are immutable because there is no need to mutate them. Here  is my python 1.4 function, direct translation from perl:

def merge_strings( str1, str2 ):
 max_len=max( len(str1), len(str2) )
 retval=[]
 for i in range(max_len):
  if (len(str1) > i):
   retval.append( str1[i] )
  if (len(str2) > i):
   retval.append( str2[i] )
 return string.joinfields(retval,"")