RogerBW's Blog

I’ve been doing the Perl Weekly Challenges. The latest involved zeroing parts of a matrix and reordering a list.

You are given a matrix of size M x N having only 0s and 1s.

Write a script to set the entire row and column to 0 if an element is 0.

Back to test-driven development.

use Test::More tests => 2;

is_deeply(zm([[1,0,1],[1,1,1],[1,1,1]]),
          [[0,0,0],[1,0,1],[1,0,1]],
          'example 1',
            );
is_deeply(zm([[1,0,1],[1,1,1],[1,0,1]]),
          [[0,0,0],[1,0,1],[0,0,0]],
          'example 2',
            );

Then the actual function.

sub zm {
  my $in=shift;

Get the M and N sizes (assume N is consistent).

  my $a=scalar @{$in}-1;
  my $b=scalar @{$in->[0]}-1;
  my %seta;
  my %setb;

For each zero we find, flag the rows and columns in the list.

  foreach my $ai (0..$a) {
    foreach my $bi (0..$b) {
      if ($in->[$ai][$bi]==0) {
        $seta{$ai}=1;
        $setb{$bi}=1;
      }
    }
  }

Then, using those flags, zero the relevant cells. We may set a cell more than once if it's in both a zeroed row and a zeroed column (or indeed if it's the zero cell that triggered the setting in the first place), but I suspect it's quicker to do that than to keep another level of edit lists.

  foreach my $aa (keys %seta) {
    foreach my $bi (0..$b) {
      $in->[$aa][$bi]=0;
    }
  }
  foreach my $bb (keys %setb) {
    foreach my $ai (0..$a) {
      $in->[$ai][$bb]=0;
    }
  }
  return $in;
}

You are given a singly linked list $L as below:

L0 → L1 → … → Ln-1 → Ln

Write a script to reorder list as below:

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 →

Perl really doesn't do linked lists; there's rarely a need for them. But I'll try to solve this in the spirit of the problem.

use Test::More tests => 2;

is_deeply(rl([1,2,3,4]),
          [1,4,2,3],
          'example 1',
            );
is_deeply(rl([1,2,3,4,5]),
          [1,5,2,4,3],
          'example 2',
            );

sub rl {
  my $list=shift;

I'll ignore the contents for now, and simply build a list of indices in the required order.

  my $n=scalar @{$list};
  my $nx=$n-1;
  my @i;
  foreach my $ni (0..int($nx/2)) {
    push @i,$ni,$nx-$ni;
  }
  if ($i[-1] == $i[-2]) {
    pop @i;
  }

Now we have a list of indices, and we can rearrange the list of actual data in a single operation with array slicing:

  @{$list}=@{$list}[@i];
  return $list;
}