Perl Weekly Challenge 123: Ugly Numbers and Square Points
These are some answers to the Week 123 of the Perl Weekly Challenge organized by Mohammad S. Anwar.
Spoiler Alert: This weekly challenge deadline is due on August 1, 2021 at 24:00. This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.
Task 1: Ugly Numbers
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 in Raku
The isugly
subroutine finds whether its input value is ugly by dividing it by 2, 3 and 5 as long as it can do it evenly. At the end, the number is ugly if the end result is 1.
The program then simply builds an infinite lazy list of ugly numbers. The nth ` ugly number is just the nth number of that list.
use v6;
sub isugly (UInt $in is copy where * > 0) {
for 2, 3, 5 > $div {
$in div= $div while $in %% $div;
}
return $in == 1;
}
my $uglynrs = grep {isugly $_}, (1...Inf);
my $n = @*ARGS[0] // 7;
say $uglynrs[$n1];
Some sample executions:
$ raku ./uglynrs.raku
8

$ raku ./uglynrs.raku 10
12

$ raku ./uglynrs.raku 100
1536
Ugly Numbers in Perl
The isugly
subroutine is essentially similar to its counterpart in Raku: it finds whether its input value is ugly by dividing it by 2, 3 and 5 as long as it can do it evenly. At the end, the number is ugly if the end result is 1.
The rest or the program is quite different because there is no lazy list in Perl. So we basically use an infinite loop and test the successive integers for ugliness. The program counts the ugly numbers, and it prints out the number and exits the loop when the target range is reached.
use strict;
use warnings;
use feature "say";
sub is_ugly {
my $in = shift;
for my $div (2, 3, 5) {
$in /= $div while $in % $div == 0;
}
return $in == 1;
}
my $n = shift // 7;
my $i = 0;
my $count = 0;
while (1) {
$count ++;
$i++ if is_ugly $count;
say $count and last if $i == $n
}
Some sample executions:
$ perl ./uglynrs.pl
8
$ perl ./uglynrs.pl 10
12
$ perl ./uglynrs.pl 100
1536
Ugly Numbers in Scala
In Scala, we also use a while
loop.
object root extends App {
def isUgly(in: Int): Boolean = {
var cpy = in
val div = List(2, 3, 5);
for (i < div) {
while (cpy % i == 0) {
cpy = cpy / i
}
}
if (cpy == 1) { return true }
return false
}
val n = 7
var j = 0
var k = 0
while (k <= n) {
j = j + 1
if (isUgly(j)) {
k = k + 1
// println(k)
if (k == n) { println(k) }
}
}
}
With the hardcoded input value of 7, the program duly prints 8, the 7th ugly number.
Ugly Numbers in Python
import sys
def isUgly(n):
for div in [2, 3, 5]:
while (n % div == 0):
n = n / div;
if n == 1:
return True
return False;
count = 0
i = 0
target = int(sys.argv[1])
while count <= target:
i += 1;
if isUgly(i):
count += 1;
if count == target:
print(i)
break
Sample output:
$ python3 uglynums.py 7
8
$ python3 uglynums.py 10
12
$ python3 uglynums.py 100
1536
Task 2: Square Points
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.
How do we determine whether four points form a square? There is undoubtedly a number of ways to do that, but it seems to me that the easiest is to check whether the four edges of the quadrilateral are equal. The problem, though, is that we can compute 6 distances between four points, 4 or which are the edges, and two the diagonals. But we don’t know in advance which distance will be the edges and which will be the diagonals. So, essentially, for the six possible distances in a square, we expect four to be equal (the edges) and 2 others with a distance equal to the edge length multiplied by the square root of 2.
This is what we find with the distances computed in the first test case provided with the task:
([x => 10 y => 20] [x => 20 y => 20]) 10
([x => 10 y => 20] [x => 20 y => 10]) 14.142135623730951
([x => 10 y => 20] [x => 10 y => 10]) 10
([x => 20 y => 20] [x => 20 y => 10]) 10
([x => 20 y => 20] [x => 10 y => 10]) 14.142135623730951
([x => 20 y => 10] [x => 10 y => 10]) 10
It seems likely that having two values for the six distances might be sufficient. But I would rather test that one of the distance values appears four times.
Square Points in Raku
People who know me know that I am not really a great fan of objectoriented programming, but, in this case, I found that implementing a very simple Point
class made some sense. The dist
subroutine takes two Point
objects as input parameters. Otherwise, the build4point
subroutine creates four points from a list of numeric parameters.
The program computes the six possible distances between the four points, and confirm that the four points form a square if there are four distances that are equal. Note that, for “oblique” squares, it might be necessary to round the distances before comparing them, but that might lead to false squares. So there is a tradeoff, and I’m not sure how to handle it. The program below doesn’t try to handle such specific cases.
use v6;
class Point {
has $.x; # abscissa
has $.y; # ordinate
method gist { return "[x => $!x y => $!y]"}
}
sub dist (Point $a, Point $b) {
return sqrt( ($b.x  $a.x)² + ($b.y  $a.y)² );
}
sub build4points (@in) {
my @points;
for @in > $x, $y {
push @points, Point.new(x => $x, y => $y)
}
return @points;
}
my @tests = <10 20 20 20 20 10 10 10>,
<12 24 16 10 20 12 18 18>;
for @tests > @test {
my @p = build4points @test;
my %dist;
for (@p).combinations: 2 > $c {
%dist{dist($c[0], $c[1])}++;
}
# say %dist;
print @test, " => ";
if any(values %dist) == 4 {say 1;} else {say 0}
}
This program displays the follwing output:
$ raku .:squarepoints.raku
10 20 20 20 20 10 10 10 => 1
12 24 16 10 20 12 18 18 => 0
Square Points in Perl
We are not using OOprogramming in Perl, but the algorithm is essentially the same.
use strict;
use warnings;
use feature qw/say/;
use Data::Dumper;
sub dist {
my ($p1, $p2) = @_;
sqrt(($p2>{x}  $p1>{x}) ** 2 + ($p2>{y}  $p1>{y}) ** 2);
}
sub build4points {
my @i = @_;
my @p;
for (1..4) {
push @p, { x => shift, y => shift };
}
return @p;
}
my @tests = ( [ qw/10 20 20 20 20 10 10 10/ ],
[ qw/12 24 16 10 20 12 18 18/ ] );
for my $test (@tests) {
my @points = build4points(@$test);
my %dist;
for my $p ( [0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3] ) {
my $distance = dist($points[$p>[0]], $points[$p>[1]]);
$dist{$distance}++
}
# say Dumper \%dist;
print "@$test => ";
if ( grep { $_ == 4 } values %dist) {
say 1;
} else {
say 0;
}
}
This program displays the following output:
$ perl ./squarepoints.pl
10 20 20 20 20 10 10 10 => 1
12 24 16 10 20 12 18 18 => 0
## Wrapping up
The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on August 8, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.
Leave a comment