Month: February 2021

Wherein we undo what we have done previously and see if we’re still working inside the lines.

THE WEEKLY CHALLENGE – PERL & RAKU #101

---

episode one:
“Spiraling Out of Control”

---

Task 1

Pack a Spiral

Submitted by: Stuart Little

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

Method

There’s basically two parts to this puzzle — figuring out the ideal dimensions of the matrix, then fitting our array.

it’s intuitively obvious that the rectangle whose height and width will most nearly coincide is the one where they’re the same value: a square. Perhaps we could go stronger: rather than saying it’s obvious we should just call it a tautology. In any case it then stands to reason that the ideal form for our ‘tightly’ qualifier would be that of a square. The dimension of a side of one of these ideal spirals then is naturally the square root of the length. If that value works out evenly to an integer, then ding, ding, we have a winner.

If it does not, however, we will need to find the next best fit.

For every factor that evenly divides the target value there will be a complement factor, being the number it multiplies by to obtain the desired value. For each of these pairs one value will be less than the square root, the other more. Unless they are the square root, of course, in which case both values are the same. As such we really only need to search one side, the smaller, iterating up to and including the square root. Any factor located past that point will just be the complement to another we’ve already found on the way up.

As to the second half of the puzzle, drafting out the spiral, essentially this is a reverse of the actions we wrote about in The Product of the Absence – Spiralize the Day Away, where we took a spiral matrix and unrolled it into an array. Although the act of translating between the idea of a spiraled matrix and a linear sequence exists in both tasks, and the code for one obviously will inform to the other, the implementation will not be exactly the same.

The actual spiraling does follow the same general pattern, though: Draw a line in a given direction until it’s time to stop, turn left, draw again. Stop when we run out of array.

PERL 5 SOLUTION

The output for the numbers 1-15 suggests some weird deep structure. If we subtract the height from the width, we get the sequence

2, 0, 4, 1, 6, 2, 0, 3, 10, 1, 12, 5, 2, 0, 16, 3, 18, 1, 4, 9, 22, 2, 0, 11, 6, 3, 28…

which when we run it through the Online Encyclopedia of Integer Sequences, yields

A056737

Minimum nonnegative integer m such that n = k*(k+m) for some positive integer k.

Huh. Well would you look at that.

1 2 3

4  3  
1  2  

1 2 3 4 5

6  5  4  
1  2  3  

1 2 3 4 5 6 7

8  7  6  5  
1  2  3  4  

7  6  5  
8  9  4  
1  2  3  

10  9   8   7   6   
1   2   3   4   5   

1 2 3 4 5 6 7 8 9 10 11

9   8   7   6   
10  11  12  5   
1   2   3   4   

1 2 3 4 5 6 7 8 9 10 11 12 13

14  13  12  11  10  9   8   
1   2   3   4   5   6   7   

11  10  9   8   7   
12  13  14  15  6   
1   2   3   4   5   

Here’s the code:

use warnings;
use strict;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';
use POSIX;
use List::Util qw(max);


my @arr;
for my $n (3..100) {
    @arr = (1..$n);
    my ($m, $n) =  find_dim( scalar @arr );
    my $spiral = spiral_fill( $m, $n, @arr );
    print_matrix( $spiral );
    say '';

}

sub find_dim ($size) {
## SV Int size -> (SV Int m, SV Int n)
## find the largest factor less than or equal to the square root
    my $try = (int sqrt $size) + 1;
    while (--$try > 1) {
        last unless $size % $try;
    }
    return ($try, int $size/$try);
}

sub spiral_fill ( $rows, $cols, @arr ) {
## given dimensions and an array spiral fills a matrix with those dimensions
    my $rank = 0;
    my $mat;

    while ( -spiralize ) {
        ## lower - left to right
        return $mat if $rank > ceil( $rows / 2 - 1);
        for my $col ( $rank..$cols - $rank - 1) {
            $mat->[$rows-$rank-1][$col] = shift @arr;
        }

        ## right - bottom to top
        return $mat if $rank > ceil( $cols / 2 - 1);
        for my $row ( reverse $rank+1..$rows-$rank-2 ) {
            $mat->[$row][$cols-$rank-1] =  shift @arr;
        }

        ## upper - right to left
        return $mat if $rank > floor( $rows / 2 - 1);
        for my $col ( reverse $rank..$cols - $rank - 1) {
            $mat->[$rank][$col] =  shift @arr;
        }

        ## left - top to bottom
        return $mat if $rank > floor( $cols / 2 - 1);
        for my $row ( $rank+1..$rows-$rank-2 ) {
            $mat->[$row][$rank] =  shift @arr;
        }
        
        ## close ranks
        $rank++;
    }
}

sub print_matrix ( $matrix ) {

    if (scalar $matrix->@* == 1) {
        say "$_->@*" for $matrix->@*;
    }
    else {
        my @maxes = map { max $_->@* }  $matrix->@*;
        my $max = max @maxes;

        my $order = 0;
        $order++ while int($max/10**$order) > 0;
        $order+=2;              ## padding
        
        my $fmt = ("%-" . $order . "d") x scalar $matrix->[0]->@*;
        for (keys $matrix->@*) {
            printf "$fmt\n", $matrix->[$_]->@*;
        }
    
    }
    
}

---

episode two:
“In Or Out, Make Up Your Mind!”

---

task 2

Origin-containing Triangle

Submitted by: Stuart Little

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.

Method

This particular task — whether a given point lies within a bounded area, be it a triangle or a generalized polygon — comes into play in real, practical applications, specifically modeling the real world in virtual simulation: “Is this thing touching that?”

Because video games require quite a lot of this sort of thing, mountains of work has been done and a great many schemes have evolved to determine this state quickly and efficiently. To list a few of the most common methods:

1. using barycentric coodinates
2. using parametric equations
3. using the vector product
4. checking an equal sum of triangle areas
5. checking a 360° sum of angles
6. counting single edge intersection with a ray-cast line
7. non-zero winding numbers counting axis crossings

We’re going to use the vector product. Although it involves some advanced mathematics, in another sense it’s fairly easy to understand. What we do here is, for each point, to take what is known as the vector product between the two vectors going from the origin to the point, and from the point to the next point. Consider a vector to be a line with a direction attached, a point to go from and a point to go to. Without delving too far into the details, due to a property known as the right hand rule, it’s easy to visualize that the z-component of this calculation will, if the direction of the turning described by the vectors is counterclockwise, be upward, or positive. Conversely if the turning is clockwise, this value will be negative.

Ok that veered a little from simple layman’s terms, but bear with me.

What this does is it gives us a quick and easy insight as to whether the origin lies to the left or the right of each edge of the triangle. Now some more visualization tells us that if the origin lies consistently to the left of each edge, the edges must by necessity wrap around the origin. Cool, huh? Now doe you get it? That’s what we’re going to do today.

The same logic applies for the right side as well of course, and to complete the picture if the origin lies on one of the edges this value will be 0.

Thus if all values for this calculation are either positive or negative, or any value is 0, the triangle encloses the origin.

PERL 5 SOLUTION

Suffice to say the rather cryptic equation in the dot_product() routine calculates what we’re looking for, and the result tells us what we need to know in the manner explained above.

use warnings;
use strict;
use feature ":5.26";


package main;
use feature qw(signatures);
no warnings 'experimental::signatures';


@ARGV = (0,-4, 0,4, - 4,0);

say origin_inside_triangle( @ARGV ) if @ARGV;

sub origin_inside_triangle ( @triangle ) {
    return place_origin( @triangle );
}

sub dot_product ( $x1,$y1, $x2,$y2 ) {
    my $v = (($y2-$y1)*(-$x1) + (-$x2+$x1)*(-$y1));
    return $v > 0 ? 1 : $v < 0 ? -1 : 0;
}

sub place_origin ( $x1, $y1, $x2, $y2, $x3, $y3 ) {
# return true if all positive, all negative or any 0
    my $s1 = dot_product( $x1,$y1, $x2,$y2 );
    my $s2 = dot_product( $x2,$y2, $x3,$y3 );
    my $s3 = dot_product( $x3,$y3, $x1,$y1 );
    
    return 1 if $s1*$s2*$s3 == 0;
    
    my $sum = $s1 + $s2 + $s3;
    return ($sum == -3 || $sum == 3) ? 1 : 0;
}