Perl Weekly Challenge: Week 101
Challenge 1:
Pack a Spiral
You are given an array @A of items (integers say, but they can be anything).
Your task is to pack that array into an MxN matrix spirally counterclockwise, as tightly as possible.
'Tightly' means the absolute value |M-N| of the difference has to be as small as possible.
Example 1
Input: @A = (1,2,3,4)
Output:
4 3
1 2
Since the given array is already a 1x4 matrix on its own, but that's not as tight as possible. Instead, you'd spiral it counterclockwise into
4 3
1 2
Example 2
Input: @A = (1..6)
Output:
6 5 4
1 2 3
or
5 4
6 3
1 2
Either will do as an answer, because they're equally tight.
Example 3
Input: @A = (1..12)
Output:
9 8 7 6
10 11 12 5
1 2 3 4
or
8 7 6
9 12 5
10 11 4
1 2 3
The first thing we need to find out is the dimensions of the packed spiral.
This requires finding the factors of the size of @A with the minimum difference.
sub factors {
my ($size) = @_;
my @tightest = ($size, 1);
my $minimum = abs($tightest[0] - $tightest[1]);
for my $m (grep { $size % $_ == 0; } 2 .. $size / 2) {
my $n = $size / $m;
my $difference = abs($m - $n);
if ($difference < $minimum) {
$minimum = $difference;
@tightest = ($m, $n);
}
}
return @tightest;
}
For both of this weeks challenges I had to look up the appropriate algorithms in whole or part on the Internet. For drawing the spiral, this page turned out to be quite helpful though it had the spiral start from the top left and go clockwise whereas we want the spiral to start at the bottom left and go counter-clockwise. It took me a while to figure out how to make the necessary adaptations.
sub spiral {
my ($a, $m, $n) = @_;
$a is a reference to @A, our sequence of items. $m and $n are the minimum factors we determined from the
factors() subroutine.
my $top = 0;
my $bottom = $m - 1;
my $left = 0;
my $right = $n - 1;
my $index = 0;
my @matrix;
In order to form the spiral, we will need to know the positions of its four sides. We will copy the elements of @A
into a new array called @matrix. $index keeps track of which element of @A we are on.
while (1) {
if ($left > $right) {
last;
}
for (my $i = $left; $i <= $right; $i++) {
$matrix[$bottom][$i] = $a->[$index++];
}
$bottom--;
The first leg of the spiral is the bottom side.
if ($top > $bottom) {
last;
}
for (my $i = $bottom; $i >= $top; $i--) {
$matrix[$i][$right] = $a->[$index++];
}
$right--;
Then the right hand side.
if ($left > $right) {
last;
}
for (my $i = $right; $i >= $left; $i--) {
$matrix[$top][$i] = $a->[$index++];
}
$top++;
And the top side.
if ($top > $bottom) {
last;
}
for (my $i = $top; $i <= $bottom; $i++) {
$matrix[$i][$left] = $a->[$index++];
}
$left++;
}
Finally, the left hand side. Each time a side is completed, its position is shrunk (by incrementing or decrementing it as the case may be.) so when the next turn of the spiral is made it will fit inside the previous one. Eventually the top will go past the bottom or the left past the right; that's when we know the spiral is complete so we can break out of the loop.
for my $i (0 .. scalar @matrix - 1) {
for my $j (0 .. scalar @{$matrix[$i]} - 1) {
printf '%2d ', $matrix[$i][$j] // 0;
}
print "\n";
}
Now we have a packed spiral in @matrix we can print it out.
}
Here are the same two functions from above in Raku.
sub factors(Int $size) {
my @tightest = ($size, 1);
my $minimum = abs(@tightest[0] - @tightest[1]);
for (2 .. $size div 2).grep({ $size %% $_ }) -> $m {
my $n = $size div $m;
my $difference = abs($m - $n);
if ($difference < $minimum) {
$minimum = $difference;
@tightest = ($m, $n);
}
}
return @tightest;
}
In this version of factors(), I used div and %% for integer division and modulo.
sub spiral(Int $m, Int $n, *@a) {
my $top = 0;
my $bottom = $m - 1;
my $left = 0;
my $right = $n - 1;
my $index = 0;
my @matrix;
loop {
Raku uses loop for the while(1) idiom and for "C" style for loops.
if ($left > $right) {
last;
}
for $left .. $right -> $i {
@matrix[$bottom][$i] = @a[$index++];
}
$bottom--;
So I could have used loop here to imitate what I did in Perl but I chose to use
ranges instead.
if ($top > $bottom) {
last;
}
for ($top .. $bottom).reverse -> $i {
One of my pet peeves in Perl which was not fixed in Raku for some reason is that you can't have ranges that go backwards without explicitly reversing them.
@matrix[$i][$right] = @a[$index++];
}
$right--;
if ($left > $right) {
last;
}
for ($left .. $right).reverse -> $i {
@matrix[$top][$i] = @a[$index++];
}
$top++;
if ($top > $bottom) {
last;
}
for $top .. $bottom -> $i {
@matrix[$i][$left] = @a[$index++];
}
$left++;
}
for 0 .. @matrix.elems - 1 -> $i {
for 0 .. @matrix[$i].elems - 1 -> $j {
printf '%2d ', @matrix[$i][$j];
}
print "\n";
}
}
Challenge 2:
Triangle Sum
You are given three points in the plane, as a list of six co-ordinates: A=(x1,y1), B=(x2,y2) and C=(x3,y3).
Write a script to find out if the triangle formed by the given three co-ordinates contain origin (0,0).
Print 1 if found otherwise 0.
Example 1
Input: A=(0,1), B=(1,0) and C=(2,2)
Output: 0 because that triangle does not contain (0,0).
Example 2
Input: A=(1,1), B=(-1,1) and C=(0,-3)
Output: 1 because that triangle contains (0,0) in its interior.
Example 3
Input: A=(0,1), B=(2,0) and C=(-6,0)
Output: 1 because (0,0) is on the edge connecting B and C.
I found out how to solve this from this site. It requires two functions.
sub area {
my ($p1, $p2, $p3) = @_;
return abs(
(
$p1->[0] * ($p2->[1] - $p3->[1]) +
$p2->[0] * ($p3->[1] - $p1->[1]) +
$p3->[0] * ($p1->[1] - $p2->[1])
) / 2.0
);
}
This function calculates the area between three points.
sub isInside {
my ($a, $b, $c, $p) = @_;
my $area0 = area($a, $b, $c);
my $area1 = area($p, $b, $c);
my $area2 = area($a, $p, $c);
my $area3 = area($a, $b, $p);
return ($area0 == $area1 + $area2 + $area3);
}
This one determines if point $p is within the triangle formed by $a, $b, and $c.
We do this by comparing the area of the triangle with the area of the sub-triangles formed
by $p and sets of two of the three points of the triangle. If the area of the triangle is equal
to the sum of the areas of the sub-triangles. If the two are equal, $p is inside.
For the purpose of this problem, $p is always (0, 0).
if (scalar @ARGV != 3) {
usage;
}
I chose to provide the input as a set of three points where a point is a pair of integers (possibly negative) separated by a comma.
my $pointrx = qr/\A (-*\d+) \, (-*\d+) \z /msx;
$ARGV[0] =~ /$pointrx/;
my @a = ($1, $2);
$ARGV[1] =~ /$pointrx/;
my @b = ($1, $2);
$ARGV[2] =~ /$pointrx/;
my @c = ($1, $2);
This requires parsing and as I'm going to be using the same regular expression each time, I saved it in the
scalar $pointrx.
my @p = (0, 0);
say isInside(\@a, \@b, \@c, \@p) ? 1 : 0;
In Perl I represented points as an array of two elements but for the Raku version, I thought I would use OOP
and make a proper Point class.
class Point {
has Int $.x;
has Int $.y;
I could have stopped here and had objects that could be constructed like this: Point.new(x => n1, y => n2)
but instead I got fancier.
multi method new (Str $str) {
$str ~~ / ^ ( \-* \d+ ) \, ( \-* \d+ ) $ /;
self.bless( x => $0.Int, y => $1.Int );
}
The new constructor takes a string and parses it into x and y. This way I can take a command line argument
and directly convert it into a Point.
multi method new (Int $x, Int $y) {
self.bless( x => $x, y => $y);
}
There is also a constructor that takes two integers which we will need for $p = (0,0).
}
Having made a Point class, why not a Triangle too?
class Triangle {
has Point $!p1;
has Point $!p2;
has Point $!p3;
has Numeric $.area;
A Triangle holds the three Points which make up its' vertices and has an additional
member that holds its area. After all this is always going to be the same so there is no
need to recalculate it each time we need it.
Class members that have the ! "twigil" are private and can only be accessed from within class methods
as opposed to ones that have ..
method new (Point $a, Point $b, Point $c) {
self.bless(p1 => $a, p2 => $b, p3 => $c);
}
Unfortunately, this means private members cannot be initialized from outside either so we can't use the autogenerated constructor and have to provide our own.
submethod BUILD (Point :$!p1, Point :$!p2, Point :$!p3) {
$!area = abs(
(
$!p1.x * ($!p2.y - $!p3.y) +
$!p2.x * ($!p3.y - $!p1.y) +
$!p3.x * ($!p1.y - $!p2.y)
) / 2.0
);
}
The BUILD() method is called after construction. We calculate the area there.
}
sub isInside (Point $a, Point $b, Point $c, Point $p) {
my $area0 = Triangle.new($a, $b, $c).area;
my $area1 = Triangle.new($p, $b, $c).area;
my $area2 = Triangle.new($a, $p, $c).area;
my $area3 = Triangle.new($a, $b, $p).area;
return ($area0 == $area1 + $area2 + $area3);
}
Notice how much clearer isInside() is now?