RogerBW's Blog

I’ve been doing the Perl Weekly Challenges. The latest involved multiplications and spirals. (Note that this is open until 29 November 2020.)

TASK #1 › Array of Product

You are given an array of positive integers @N.

Write a script to return an array @M where $M[i] is the product of all elements of @N except the index $N[i].

In other words, given [a,b,c], return [b*c,a*c,a*b].

There are two obvious ways to do it. The naïve approach would be to build each subset of the list, then take the product: so for each of the n list members do n-2 multiplications, a total of n²-2n. The other would be to multiply everything together (n-1 multiplications), and then divide the product by each element in turn (n divisions). Divisions are more computationally expensive than multiplications, of course, and the product will be slightly larger, but it's still O(n) rather than O(n²).

Anyway, the naïve approach (using the product function from List::Util):

sub aop {
  my $ns=shift;
  my @o;
  foreach my $i (0..$#{$ns}) {
    push @o,product(map {$ns->[$_]} grep {$_ != $i} (0..$#{$ns}));
  }
  return \@o;
}

and the better one that I ended up using:

sub aop {
  my $ns=shift;
  my $p=product(@{$ns});
  return [map {$p/$_} @{$ns}];
}

Profiling showed that on a 20-element list the naïve approach took about ten times as long. One restriction is that the product has to fit in a standard integer (I didn't bother with BigInt or equivalents).

The other languages I'm using have reduce-type functions, a compact way of combining list members with a specific function. The syntax varies a bit from one language to another. Raku:

sub aop(@ns) {
  my $p=@ns.reduce: &infix:<*>;
  return (map {$p div $_}, @ns);
}

Python:

def aop(ns):
    p=reduce(operator.mul,ns)
    return [p // i for i in ns]

Ruby:

def aop(*ns)
  p=ns.reduce(:*)
  return ns.map {|x| p.div(x)}
end

Rust:

fn aop(ns: Vec<i32>) -> Vec<i32> {
    let p=ns.iter().fold(1,|sum, item| sum * item);
    return ns.iter().map(|i| p/i).collect()
}

TASK #2 › Spiral Matrix

You are given m × n matrix of positive integers.

Write a script to print spiral matrix as list.

The approach I took on this was a path traversal. Start off by going along one edge, logging each cell value; whenever there's no cell ahead (i.e. an edge), or the cell ahead has already been visited, turn right.

I'll use the Raku version to demonstrate; they all look roughly the same.

sub sm(@m) {

Establish x/y sizes

  my $mx=@m.elems;
  my $my=@m[0].elems;

Push the first entry into the output list.

  my @o=(@m[0][0]);

Construct the "visited" matrix, initially 0 throughout.

  my @v;
  for 1..$mx {
    push @v,[(0) xx $my];
  }

Establish the direction array and initialise x, y and direction.

  my @dir=(
    [0,1],
    [1,0],
    [0,-1],
    [-1,0],
      );
  my ($x,$y,$d)=(0,0,0);

We don't need an "exit if no un-visited adjacent cells" test, because we know how many cells are to be visited.

  for 2..$mx*$my {

Mark the current cell as visited

    @v[$x][$y]=1;

Generate the neighbouring cell coordinates. If they're out of bounds, or they've been visited, turn right and try again.

    my ($nx,$ny);
    while (1) {
      ($nx,$ny)=($x+@dir[$d][0],$y+@dir[$d][1]);
      if ($nx < 0 || $nx >= $mx || $ny < 0 || $ny >= $my || @v[$nx][$ny]==1) {
        $d++;
        $d%=4;
      } else {
        last;
      }
    }

We have valid coordinates, so stick the new cell's value on the output.

    ($x,$y)=($nx,$ny);
    push @o,@m[$x][$y];
  }
  return @o.List;
}

The other languages worked pretty much the same way. Something went a bit strange with Rust, and I had to sprinkle types and type conversions all over everything; I suspect this is because of the the possibility that a value I'll want to use for a subscript will at some point be negative (even if I explicitly test for that first).

Full code on github.