laurent_r

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 is-ugly 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 is-ugly (UInt $in is copy where * > 0) {
    for 2, 3, 5 -> $div {
        $in div= $div while $in %% $div;
    }
    return $in == 1;
}
my $ugly-nrs = grep {is-ugly $_}, (1...Inf);
my $n = @*ARGS[0] // 7;
say $ugly-nrs[$n-1];

Some sample executions:

$ raku ./ugly-nrs.raku
8
-
$ raku ./ugly-nrs.raku 10
12
-
$ raku ./ugly-nrs.raku 100
1536

Ugly Numbers in Perl

The is-ugly 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 ./ugly-nrs.pl
8

$ perl ./ugly-nrs.pl 10
12

$ perl ./ugly-nrs.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 hard-coded 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 ugly-nums.py 7
8

$ python3 ugly-nums.py 10
12

$ python3 ugly-nums.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 object-oriented 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 trade-off, 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 .:square-points.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 OO-programming 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 ./square-points.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.