# Perl Weekly Challenge 101

This week was pretty fun – solution one ends up re-using some code from my first post (Challenge 88), and solution two explores Barycentric coordinates! No ugly one-liners this week. 🙂

## Task 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 of the difference between `M` and `N` (`|M-N|`) 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,2,3,4,5,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,2,3,4,5,6,7,8,9,10,11,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
``````

### Solution

See below for explanation and any implementation-specific comments.

``````# Finds all factor pairs of a given numbers
sub factors(Int \$n) returns Positional {
my \$max = \$n.sqrt.floor;
my \$number = 1;
my @factors;
while \$number <= \$max {
my \$potential-factor = \$n / \$number;
if \$potential-factor == \$potential-factor.Int {
@factors.push((\$number.clone, \$potential-factor)); # 
}
\$number++;
}
@factors;
}

# Formats a 2D array into a multi-line string
sub format(@two-d) returns Str {
my \$width = @two-d[*;*].max(*.chars).chars;                                # 
my @formatted = gather {
for @two-d -> @row {
take @row.map(-> \$num { sprintf('%*s', \$width, \$num) }).join(' '); # 
}
}
@formatted.join("\n");
}

sub challenge(@A) returns Str {
enum Direction <NORTH EAST SOUTH WEST>;

my @factors = factors(@A.elems);
my (\$m, \$n) = @factors.min(-> (\$a, \$b) { abs(\$a - \$b) });
my (@matrix, @output);
for ^\$m {
my (@matrix-row, @output-row);
for ^\$n {
@matrix-row.push({ :!visited });
@output-row.push(Nil)
}
@matrix.push(@matrix-row);
@output.push(@output-row);
}

sub visit-cell(\$i, \$j, \$element) { # 
my %cell = @matrix[\$i][\$j];
if !%cell<visited> {
@output[\$i][\$j] = \$element;
}
@matrix[\$i][\$j]<visited> = True;
}

my (\$min-row, \$min-col) = 0, 0;
my (\$max-row, \$max-col) = @matrix.elems - 1, @matrix.tail.elems - 1;
my (\$current-row, \$current-col, \$current-direction) = \$min-row, \$min-col, EAST;

for @A -> \$element {
visit-cell(\$current-row, \$current-col, \$element);
given \$current-direction {
when EAST {
if \$current-col == \$max-col || @matrix[\$current-row][\$current-col+1]<visited> {
\$current-direction = SOUTH;
\$current-row += 1;
} else {
\$current-col += 1;
}
}
when SOUTH {
if (\$current-row == \$max-row && \$current-col == \$max-col) || @matrix[\$current-row+1][\$current-col]<visited> {
\$current-direction = WEST;
\$current-col -= 1;
} else {
\$current-row += 1;
}
}
when WEST {
if \$current-col == \$min-col || @matrix[\$current-row][\$current-col-1]<visited> {
\$current-direction = NORTH;
\$current-row -= 1;
} else {
\$current-col -= 1;
}
}
when NORTH {
# No need to check for special case here, because we always start in the top left
if @matrix[\$current-row-1][\$current-col]<visited> {
\$current-direction = EAST;
\$current-col += 1;
} else {
\$current-row -= 1;
}
}
}
}

format(@output.reverse);
}

sub MAIN(*@A) {
say challenge(@A);
}
``````

This program runs as such:

``````\$ raku ch-1.raku 1 2 3 4
4 3
2 1

\$ raku ch-1.raku 1 2 3 4 5 6
6 5 4
1 2 3
``````

### Explanation

The problem says to wrap the spiral counterclockwise (i.e., start at the bottom left, and fill-in counterclockwise), this is pretty hard to do, given a dynamic-sized array. What I did instead was start at the top left, fill in clockwise, then reverse (mirror) the outer array, so the spiral started at the bottom left.

Here is the basic logic:

1. Find all the factors of the length of the input array.
2. Find the pair of `M` and `N` such that `|M-N|` is minimized
• Because of the way we find the factors, `M` will always be `<= N`, so we will have horizontal output as opposed to the vertical output.
3. Define the 2D array with empty cells (`@output`), as well as a separate companion array (`@matrix`) that keeps track of visited cells.
4. Traverse through the input array, keeping track of visited cells in `@matrix`, and filling in `@output`.
5. Once `@output` has been filled in, reverse it, and format it into the expected output string.

1. I found it interesting that I had to use `\$number.clone` here, but if I just used `\$number`, all the pairs in the output ended up with the same `M` value.
2. `[*;*]` is the way to flatten a 2D array. If it were a 3D array you would use `[*;*;*]` and the pattern continues for more-nested arrays. An interesting quirk of Raku.
3. Normally in `sprintf` we would do something like `%2s` to say we want to pad something to two characters. However, since the width is variable, we are able to use `%*s` and pass the width in as an argument.
4. The `visit-cell` subroutine needs to be defined within `challenge` because it is a closure, meaning it has access to the variables defined within `challenge`, but outside `visit-cell`. In this case, it is accessing `@output` and `@matrix`.

You are given three points in the plane, as a list of six coordinates: `A=(x1,y1)`, `B=(x2,y2)` and `C=(x3,y3)`.

Write a script to find out if the triangle formed by the given three coordinates 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.
``````

### Solution

See below for explanation and any implementation-specific comments.

``````class Point {
has Int \$.x;
has Int \$.y;

multi method new(\$x, \$y) { # 
self.bless(:\$x, :\$y);
}
}

sub challenge(Point \$A, Point \$B, Point \$C, Point \$target = Point.new(0, 0)) returns Int {
my \$area = 0.5 * (-\$B.y * \$C.x + \$A.y * (-\$B.x + \$C.x) + \$A.x * (\$B.y - \$C.y) + \$B.x * \$C.y);
my \$s = 1 / (2 * \$area) * (\$A.y * \$C.x - \$A.x * \$C.y + (\$C.y - \$A.y) * \$target.x + (\$A.x - \$C.x) * \$target.y);
my \$t = 1 / (2 * \$area) * (\$A.x * \$B.y - \$A.y * \$B.x + (\$A.y - \$B.y) * \$target.x + (\$B.x - \$A.x) * \$target.y);
(0 <= \$s <= 1 && 0 <= \$t <= 1 && \$s + \$t <= 1).Int;
}

sub MAIN(Int \$x1, Int \$y1, Int \$x2, Int \$y2, Int \$x3, Int \$y3) {
say challenge(
Point.new(\$x1, \$y1),
Point.new(\$x2, \$y2),
Point.new(\$x3, \$y3)
);
}
``````

This program runs as such:

``````\$ raku ch-2.raku 0 1 1 0 2 2
0

\$ raku ch-2.raku 1 1 -1 1 0 -3
1
``````

### Explanation

This solution is essentially this StackOverflow answer combined with this StackOverflow answer with classes instead of individual points. I won’t pretend I understand Barycentric coordinates, but it was easy enough to translate the solution into Raku. We do the following:

1. Turn our six integers into `Point` objects, so we can reference them via `\$point.x` and `\$point.y`.
2. Find the area of the triangle defined by the three points.
3. Use the area to find the Barycentric values `s` and `t`.
4. If `0 <= s <= 1` and `0 <= t <= 1` and `s + t <= 1`, then the target point (`(0,0)` by default, but can be anything) is in the triangle, otherwise it is not.
5. Cast the above boolean to an integer, because that is what is requested in the challenge.

I think the linked StackOverflow questions do a better job of describing Barycentric coordinates than I can, so I just have one implementation comment.

1. It’s much easier to deal with this problem with the `Point` object. However, defining instances of classes in Raku is quite verbose; by default, it would be like this: `Point.new(x => \$x1, y => \$y1)`. We define our own `new` method that just takes positional arguments and internally calls the named arguments via `bless`. `self.bless(:\$x, :\$y)` is shorthand for `self.bless(x => \$x, y => \$y)`. In fact, this `Point` implementation is actually the example for the `bless` method.

## Final Thoughts

Nothing much to add this week. See y’all next week!

Tags:

Categories:

Updated: