## Perl weekly challenge 101

Here are solutions to this weeks challenges from the Perl Weekly Challenge.

You can find my full code on Github

### 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 |M-N| of the difference has to be as small as possible.

```(1..4)  ->  4 3
1 2
(1..6)  ->  6 5 4   5 4
1 2 3   6 3
1 2

(1..12) ->  9  8  7  6    8  7  6
10 11 12  5    9 12  5
1  2  3  4   10 11  4
1  2  3
```

#### The solution

No attempting at real golfing this week - but still want to keep it "minimalist"...

Our `pack_spiral` routine starts by finding the largest factor of the size of the list below sqrt of the size of the list. The two dimensions we will need are this (`\$rows`) and `\$cols`. Just for compactness when printing we chose it so that `\$rows < \$cols`.

To compute the number of rows (\$rows) this is the largest number < sqrt of the number of elements (N) which is a factor of N. We can use grep to get all factors - if we reverse this the highest factor is the first element of the list...

``````sub pack_spiral {
my( \$rows )               = reverse grep { ! (@_ % \$_) } 1 .. sqrt @_;
my( \$cols, \$r, \$c, @out ) = ( @_/\$rows, \$rows-1, -1 );

``````  while( @_ ) {                                      # do until empty
\$out[ \$r ][ ++\$c ] = shift foreach 1 .. \$cols--; # >>
\$out[ --\$r ][ \$c ] = shift foreach 1 .. --\$rows; # ^^
last                       unless  @_;           # exit if empty
\$out[ \$r ][ --\$c ] = shift foreach 1 .. \$cols--; # <<
\$out[ ++\$r ][ \$c ] = shift foreach 1 .. --\$rows; # vv
}
return \@out;
}``````

We work around the spiral starting bottom left - and then work our way right `++\$c`, up `--\$r`, left `--\$c` & down `++\$r`. Each time when we draw one less column (when going left or right) and one less row (when going up or down) - hence the `\$cols--` & `--\$rows`.

Notes: `shift` by itself shifts off the magic "@_" array - so in our cases takes the next item of the list...

You can see the progress below:

```       [__]  [__]  [__]  [__]

[__]  [__]  [__]  [__]

(st)  [__]  [__]  [__]  [__]

\$rows = 3; \$cols = 4; \$r = 2; \$c = -1; @_=12;
\$out[ \$r ][ ++\$c ] = shift foreach 1 .. \$cols--;
< 4 >
[__]  [__]  [__]  [__]

[__]  [__]  [__]  [__]

st ->[_1]->[_2]->[_3]->(_4)

\$rows = 3; \$cols = 3; \$r = 2; \$c = 3; @_=8;
\$out[ --\$r ][ \$c ] = shift foreach 1 .. --\$rows;
< 2 >
[__]  [__]  [__]  (_6)
^^
[__]  [  ]  [  ]  [_5]
^^
st   [_1]->[_2]->[_3]->[_4]

\$rows = 2; \$cols = 3; \$r = 0; \$c = 3;  @_=6;
\$out[ \$r ][ ++\$c ] = shift foreach 1 .. \$cols--;
< 3 >
(_9)<-[_8]<-[_7]<-[_6]
^^
[__]  [  ]  [  ]  [_5]
^^
st   [_1]->[_2]->[_3]->[_4]

\$rows = 2; \$cols = 2; \$r = 0; \$c = 0;  @_=3;
\$out[ ++\$r ][ \$c ] = shift foreach 1 .. --\$rows;
< 1 >

[_9]<-[_8]<-[_7]<-[_6]
vv                ^^
(10)  [  ]  [  ]  [_5]
^^
st   [_1]->[_2]->[_3]->[_4]

\$rows = 1; \$cols = 2; \$r = 1; \$c = 0;  @_=1;
\$out[ \$r ][ ++\$c ] = shift foreach 1 .. \$cols--;
< 2 >
[_9]<-[_8]<-[_7]<-[_6]
vv                ^^
->->(12)  [_5]
^^
st   [_1]->[_2]->[_3]->[_4]

\$rows = 1; \$cols = 1; \$r = 1; \$c = 2;  @_=0;
\$out[ --\$r ][ \$c ] = shift foreach 1 .. --\$rows; # does nothing..
< 0 >

[_9]<-[_8]<-[_7]<-[_6]
vv                ^^
->->(12)  [_5]
^^
st   [_1]->[_2]->[_3]->[_4]```

### Task 2: Origin-containing Triangle

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.

```Input: A=(0,1) B=(1,0)  C=(2,2)   Output: 0
Input: A=(1,1) B=(-1,1) C=(0,-3)  Output: 1
Input: A=(0,1) B=(2,0)  C=(-6,0)  Output: 1
```

#### The solution

One of the uses I put my degree to at work was to use "Winding numbers" to replicate image maps in web pages {we needed to implement drag features and click feature on an image}... So winding numbers are what I will use here...

Winding number - imagine you are a dalek standing at the origin - and you trace around the triangle with your gunstick... If your head turns a full 360 either way then you are in the triangle - if it does not you are outside the triangle! This extends to any shape - you are inside the shape if you take an odd number of turns - outside if you take an even number. The following code is a quick way to compute the winding number.

To include each line - we start with the last point and join it to the first... and then first to second until we finally get back to the line between the last two points.

``````sub winding_number {
my ( \$a, \$b, \$wn ) = @_[ -2, -1 ], 0;

``````  while( my(\$x,\$y) = splice @_, 0, 2 ) {
\$wn += \$a<=0 ? \$y>0  && \$a*\$y-\$x*\$b >  0 ?  1 : 0
: \$y<=0 && \$a*\$y-\$x*\$b <= 0 ? -1 : 0;
(\$a,\$b)=(\$x,\$y);
}
return \$wn%2;
}``````

## Leave a comment

### About James Curtis-Smith Perl developer for nearly 30 years now, mainly in maintenance scripts and web pages, using mod_perl. I also code a lot in PHP (20+yrs), and also extensive experience in HTML (27+yrs), Javascript(25+yrs), CSS (24+yrs) and SASS.