# 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)); # [1]
}
$number++;
}
@factors;
}
# Formats a 2D array into a multi-line string
sub format(@two-d) returns Str {
my $width = @two-d[*;*].max(*.chars).chars; # [2]
my @formatted = gather {
for @two-d -> @row {
take @row.map(-> $num { sprintf('%*s', $width, $num) }).join(' '); # [3]
}
}
@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) { # [4]
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:

- Find all the factors of the length of the input array.
- 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.

- Because of the way we find the factors,
- Define the 2D array with empty cells (
`@output`

), as well as a separate companion array (`@matrix`

) that keeps track of visited cells. - Traverse through the input array, keeping track of visited cells in
`@matrix`

, and filling in`@output`

. - Once
`@output`

has been filled in, reverse it, and format it into the expected output string.

#### Specific comments

- 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. `[*;*]`

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.- 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. - 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`

.

## Task 2: Origin-containing Triangle

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) { # [1]
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:

- Turn our six integers into
`Point`

objects, so we can reference them via`$point.x`

and`$point.y`

. - Find the area of the triangle defined by the three points.
- Use the area to find the Barycentric values
`s`

and`t`

. - 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. - Cast the above boolean to an integer, because that is what is requested in the challenge.

#### Specific Comments

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

- 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!