RogerBW's Blog

Perl Weekly Challenge 88: Spiral Product 28 November 2020

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.


  1. Posted by RogerBW at 03:34pm on 30 November 2020

    Some answers to part 2 destroyed the matrix as they progressed through it, which might be faster with large matrices. Generally both parts were solved as above, though one player did use Perl::PDL to rotate the matrix and repeatedly take the top row while shaving off the previous one, and most people looked for a stop condition in the number of rows processed rather than the number of elements output…

Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 crime crystal cthulhu eternal cycling dead of winter doctor who documentary drama driving drone ecchi economics en garde espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 essen 2022 essen 2023 essen 2024 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo 2021 hugo 2022 hugo 2023 hugo 2024 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards mpd museum music mystery naval noir non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs ruby rust scala science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1