# Perl Weekly Challenge 123.

My solutions (task 1 and task 2) to the The Weekly Challenge - 123.

``````Submitted by: Mohammad S Anwar
You are given an integer \$n >= 1.

Write a script to find the \$nth element of Ugly Numbers.

Ugly numbers are those number whose prime factors are 2, 3
or 5. For example, the first 10 Ugly Numbers are 1, 2, 3, 4,
5, 6, 8, 9, 10, 12.

Example
Input: \$n = 7
Output: 8

Input: \$n = 10
Output: 12
``````

Ugly numbers are of the form `U_n=2**a 3**b 5**c` with `a`, `b`, and `c` nonnegative integers. Thus I can obtain an ugly number from previous ugly numbers either by multiplying by 2, by 3 or by 5. I build an array of known ugly numbers and for each factor (2, 3, or 5) I keep an index to the next old ugly number to try, choosing the smallest one that after multiplication by the appropriate prime lies above all previous ugly numbers. To find the n-th ugly number I have to generate all the previous ones, which can then be recycled for the next calculation

``````# Perl weekly challenge 123
#

use warnings;
use strict;
use v5.12;
my @uglies=(1); #known uglies
my @u_id=(0,0,0); # indices into uglies array corresponding to
my @factors=(2,3,5); # prime factors of uglies

foreach(@ARGV){
say "Input: \$_ Output: ", ugly(\$_);
}

sub ugly {
my \$n=shift @_; # desired ugly number. Assume a positive integer
while(\$n>@uglies){ # generate uglies until the n-th becomes known
my (\$next_id)=sort {next_from_id(\$a)<=>next_from_id(\$b)} 0..2;
my \$next_val=next_from_id(\$next_id);
\$u_id[\$next_id]++;
push @uglies, \$next_val if \$next_val>\$uglies[-1];
}
return \$uglies[\$n-1];
}

sub next_from_id {
my \$id=shift @_;
return \$uglies[\$u_id[\$id]]*\$factors[\$id];
}
``````

Example: Generate the first 20 ugly numbers

``````./ch-1.pl `perl -E 'say join " ", 1..20'`
``````

Results:

``````Input: 1 Output: 1
Input: 2 Output: 2
Input: 3 Output: 3
Input: 4 Output: 4
Input: 5 Output: 5
Input: 6 Output: 6
Input: 7 Output: 8
Input: 8 Output: 9
Input: 9 Output: 10
Input: 10 Output: 12
Input: 11 Output: 15
Input: 12 Output: 16
Input: 13 Output: 18
Input: 14 Output: 20
Input: 15 Output: 24
Input: 16 Output: 25
Input: 17 Output: 27
Input: 18 Output: 30
Input: 19 Output: 32
Input: 20 Output: 36
``````

``````Submitted by: Mohammad S Anwar
You are given coordinates of four points i.e. (x1, y1), (x2,
y2), (x3, y3) and (x4, y4).

Write a script to find out if the given four points form a
square.

Example
Input: x1 = 10, y1 = 20
x2 = 20, y2 = 20
x3 = 20, y3 = 10
x4 = 10, y4 = 10
Output: 1 as the given coordinates form a square.

Input: x1 = 12, y1 = 24
x2 = 16, y2 = 10
x3 = 20, y3 = 12
x4 = 18, y4 = 16
Output: 0 as the given coordinates doesn't form a square.
``````

There are several properties of squares that may be used. I guess, the easiest to use and to generalize are that the four sides are equal and the diagonal is sqrt(2) times larger. I use the Perl Data Language `PDL` to manipulate the data.

``````# Perl weekly challenge 123
#
use strict;
use warnings;
use v5.12;
use PDL;
foreach(@ARGV){
# assume data as strings "[[x0,y0],[x1,y1],[x2,y2],[x3,y3]]"
my \$m=pdl(\$_); # convert to 2d array
# Separate into four vectors, translate the origin to the first
# and sort by size
my \$v0=\$m->slice(":,(0)");
my (undef, \$s1, \$s2, \$d)=sort {size2(\$a) <=> size2(\$b)} map {\$_-\$v0} \$m->dog;
# \$s1 and \$s2 ought to be the sides and \$d the diagonal
# check they add up and their sizes. I use 'approx' to accommodate rounding errors.
my \$ok=approx(size2(\$s1+\$s2-\$d),0) && approx(size2(\$s1),size2(\$s2))
&& approx(size2(\$d),2*size2(\$s1));
say "Input: \$m Output: \$ok"
}
sub size2 { #  squared size of vector
my \$v=shift @_;
return (\$v*\$v)->sumover;
}
``````

Example:

``````./ch-2.pl "[[10,20],[20,20],[20,10],[10,10]]" \
"[[12,24],[16,10],[20,12],[18,16]]"
``````

Results:

``````Input:
[
[10 20]
[20 20]
[20 10]
[10 10]
]
Output: 1
Input:
[
[12 24]
[16 10]
[20 12]
[18 16]
]
Output: 0
``````

Example with a square that is not aligned with the Cartesian axes

``````./ch-2.pl "[[0,0],[30,40],[-40,30],[-10,70]]"
``````

Results:

``````Input:
[
[  0   0]
[ 30  40]
[-40  30]
[-10  70]
]
Output: 1
``````

The same example but shifted away from the origin

``````./ch-2.pl "[[20,30],[50,70],[-20,60],[10,100]]"
``````

Results:

``````Input:
[
[ 20  30]
[ 50  70]
[-20  60]
[ 10 100]
]
Output: 1
``````

What is very nice about `PDL` is that now I can apply my program without modification to squares in three dimensional space. First I try some squares parallel to the cartesian planes

``````./ch-2.pl "[[10,20,10],[20,20,10],[20,10,10],[10,10,10]]" \
"[[10,10,20],[20,10,20],[20,10,10],[10,10,10]]" \
"[[10,10,20],[10,20,20],[10,20,10],[10,10,10]]"
``````

Results:

``````Input:
[
[10 20 10]
[20 20 10]
[20 10 10]
[10 10 10]
]
Output: 1
Input:
[
[10 10 20]
[20 10 20]
[20 10 10]
[10 10 10]
]
Output: 1
Input:
[
[10 10 20]
[10 20 20]
[10 20 10]
[10 10 10]
]
Output: 1
``````

Now I generate a square with some other orientation by rotating and shifting in space a simple known square. For example, I rotate a simple unit square around the x axis and then around the z axis by π/4 and translate by (1,2,3).

``````perl -MPDL -E '\$t=atan2(1,1); \$c=cos(\$t), \$s=sin(\$t);'\
-E '\$Rz=pdl([[\$c,\$s,0],[-\$s,\$c,0],[0,0,1]]);'\
-E '\$Rx=pdl([[1,0,0],[0,\$c,\$s],[0,-\$s,\$c]]);'\
-E 'say +(\$Rz x \$Rx x  pdl([[1,0,0],[1,1,0],[0,1,0]])->transpose)->transpose +pdl[1,2,3]'
``````

Results:

``````[
[ 1.7071068  1.2928932          3]
[ 2.2071068  1.7928932  2.2928932]
[       1.5        2.5  2.2928932]
]
``````

I use this as input to the program.

``````./ch-2.pl "[[1,2,3],[1.7071068,1.2928932,3],[2.2071068,1.7928932,2.2928932],[1.5,2.5,2.2928932]]"
``````

Results:

``````Input:
[
[         1          2          3]
[ 1.7071068  1.2928932          3]
[ 2.2071068  1.7928932  2.2928932]
[       1.5        2.5  2.2928932]
]
Output: 1
``````

I repeat the example above but modifying one of the inputs, so that it differs slightly from a square.

``````./ch-2.pl "[[1,2,3.001],[1.7071068,1.2928932,3],[2.2071068,1.7928932,2.2928932],[1.5,2.5,2.2928932]]"
``````

Results:

``````Input:
[
[         1          2      3.001]
[ 1.7071068  1.2928932          3]
[ 2.2071068  1.7928932  2.2928932]
[       1.5        2.5  2.2928932]
]
Output: 0
``````

By default, the `approx` routine I used checks for equality within a 1e-6 error, but if desired, a more strict comparison can be made adding a third argument.

By the way, squares may be found not only in two or three dimensions, but also in higher dimensions. Some simple examples in four dimensions follow

``````./ch-2.pl "[[10,20,1,2],[20,20,1,2],[20,10,1,2],[10,10,1,2]]" \
"[[10,1,2,20],[20,1,2,20],[20,1,2,10],[10,1,2,10]]" \
"[[1,2,10,20],[1,2,20,20],[1,2,20,10],[1,2,10,10]]"
``````

Results:

``````Input:
[
[10 20  1  2]
[20 20  1  2]
[20 10  1  2]
[10 10  1  2]
]
Output: 1
Input:
[
[10  1  2 20]
[20  1  2 20]
[20  1  2 10]
[10  1  2 10]
]
Output: 1
Input:
[
[ 1  2 10 20]
[ 1  2 20 20]
[ 1  2 20 10]
[ 1  2 10 10]
]
Output: 1
``````
Written on July 27, 2021