Perl Weekly Challenge 123.
My solutions (task 1 and task 2) to the The Weekly Challenge - 123.
Task 1: Ugly Numbers
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
# Task 1: Ugly numbers
#
# See https://wlmb.github.io/2021/07/27/PWC123/#task-1-ugly-numbers
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
Task 2: Square Points
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
# Task 2: Square points
#
# See https://wlmb.github.io/2021/07/27/PWC123/#task-2-square-points
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