- Added solutions by Colin Crain.

2 files changed, 285 insertions, 0 deletions

diff --git a/challenge-101/colin-crain/perl/ch-1.pl b/challenge-101/colin-crain/perl/ch-1.pl
new file mode 100644
index 0000000000..23ba68fddb
--- /dev/null
+++ b/challenge-101/colin-crain/perl/ch-1.pl
@@ -0,0 +1,186 @@
+#! /opt/local/bin/perl

+#

+#       sprialling-out-of-control.pl

+# 

+#             PWC 101

+#             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.

+

+#         method:

+#             Given an array, there will always be one packing available, 1 x n,

+#             the linear form of the array itself. Beyond that, a tighter

+#             packing would have to contain the correct number of elements

+#             before any spiralling can commence.

+# 

+#             THus the first course of action is to compute the ideal

+#             2-dimensional form from those avaailable.

+# 

+#             The absolute ideal two dimensional orthogonal packing would be a

+#             square, so that (m-n) would be 0. Unfortunately this is only

+#             available to arrays with lengths in the square numbers,

+#             1,4,9,16,25,36 etc. 

+

+#             In a general sense the dimensions of our rectangle, our

+#             2-dimensional matrix, will be composed of two integers such that m

+#             x n = L, the length of the original array to be spiralized. As our

+#             ideal is a square form, the ideal dimension is the square root of

+#             L, and any divergence from that ideal will expand the gap between

+#             m and n. Thus by finding the smallest factor of L less than the

+#             square root we will locate m, and from that we can determine n.

+# 

+#             Once we have our dimensions determined, we can commence rotation

+#             and scalar reduction. 

+#             

+#             

+#         conclusions and deep structure:

+#             For testing we will make arrays from 1 to 100 items items long and

+#             test them all. The actual values of the elements is

+#             inconsequential so we will use sequentail values starting at 1;

+#             this will make it easy to observe the spiralling. 

+

+#             The observed pattern of minimized rectangular ratio, hence

+#             minimizing abs(m-n) is:

+# 

+#             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...

+

+#             from The On-Line Encyclopedia of Integer Sequences

+#             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 

+#             A056737		

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

+#             positive integer k.

+

+

+#

+#       © 2021 colin crain

+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

+

+

+

+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->[$_]->@*;

+        }

+    

+    }

+    

+}

+

+

+

+

diff --git a/challenge-101/colin-crain/perl/ch-2.pl b/challenge-101/colin-crain/perl/ch-2.pl
new file mode 100644
index 0000000000..9d594bd3f4
--- /dev/null
+++ b/challenge-101/colin-crain/perl/ch-2.pl
@@ -0,0 +1,99 @@
+#! /opt/local/bin/perl

+#

+#       three-walls-around-me.pl

+#

+#         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:

+# 

+#             avoids having to orient the triangle by short-circuiting 

+#             should any dot product equal 0. Inside if all procucts are 

+#             positive, all negative, or any value is 0.

+# 

+#             1. barycentric 

+#             2. parametric

+#             3. product

+#             4. equal sum of triangle area

+#             5. single edge intersection with line from infinity

+#             

+#

+#       © 2021 colin crain

+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

+

+

+

+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;

+}

+

+## TESTING

+use Test::More;

+

+is origin_inside_triangle(0,1, 1,0, 2,2)  ,   0, 'ex-1';

+is origin_inside_triangle(1,1, -1,1, 0,-3),   1, 'ex-2';

+is origin_inside_triangle(0,1, 2,0, -6,0) ,   1, 'ex-3';

+

+

+is origin_inside_triangle(-4,-4, -2,4, 3,-4), 1, '3 quadrants';

+is origin_inside_triangle(-4,-4, -2,4, 3,-4), 1, 'origin is vertex';

+

+is origin_inside_triangle(-4,0, 4,0, 4,4 ),   1, 'origin on line - ccw orientation';

+is origin_inside_triangle(-4,0, 4,0, -4,-4 ), 1, 'origin on line - cw orientation';

+is origin_inside_triangle(-4,-4, -2,4, 3,-4), 1, 'origin is vertex';

+is origin_inside_triangle(-4,1, 4,1, 4,4),    0,  'outside';

+

+done_testing();