Don’t Be an Ugly Square, Man

Wherein we separate the hep cats from the straight-laced, and please be cool — don’t call us ugly, man, we’re smooth.

THE WEEKLY CHALLENGE – PERL & RAKU #123

---

episode one:
“Play Me a Smooth Five”

---

Task 1

Ugly Numbers

Submitted by: Mohammad S Anwar

You are given an integer $n >= 1.

Write a script to find the n-th 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

An opening Note

I feel we should open this discussion with a few words of warning, and appropriate admonishment.

I feel that the very notion of numbers constructed solely from the factors 2, 3, and 5 as being somehow “ugly” would be quite distressing and even offensive to those illustrious proponents of 5-limit just intonation musical tuning systems, and expressing these sentiments in certain rarefied environments would be liable to provoke a hostile, even violent, response. These psycho-temporal explorers, remember, have chosen to live with their minds in the nexus between acoustic vibrations and the cosmos itself, and have left an even temperment — apologies for that pun but you must admit it works — far behind.

What is known as a “5-limit” system only allows interval ratios for the various notes in the scale to be composed of numbers with the factors 2, 3 and 5. Terry Riley’s tuning in The Harp of New Albion uses the intervals 2:1, 15:8, 16:9, 5:3, 8:5, 3:2, 64:45, 4:3, 5:4, 6:5, 9:8, 16:15, and 1:1, starting at a tonic of C#, and he uses the divergence among various overtone harmonics in the resulting intervals between notes within the scale to great compositional effect. It’s got bell-like consonance, stormy dissonance, jazz, ragtime, puns; it’s a whole improvised world.

I’ve been listening to The Harp of New Albion quite a lot since the Black Ships came, and consider it an amazing achievement, among the most beautiful things I’ve ever heard. And all built from the numbers 2, 3 and 5.

So there.

To those that say ugly I laugh openly and derisively at the raw insolent foolishness of the claim.

And besides, the numbers don’t care one bit about our collective, infinitesimally unimportant opinions of them. They have so, so many better things to do.

In honor of constructing note intervals from factors, then, I will choose a constructive method to build our sequence. And should we find the need, we’ll call them by another name: “5-Smooth Numbers“.

Method

If we start composing numbers using just the products of 2, 3 and 5, we can populate a line, order the values and find the number at the index requested. This sounds like a sound strategy (I’m going to leave that somewhat awkward phrasing because it reenforces the musical thematic resonance, as does the word “resonance” as well).

The question arises, though, of how many values do we need to construct? Well obviously the answer is “enough”, but the relative placement of the values constructed from a given number of factors from the pool will be figuratively all over the map. If we are to avoid filtering and factoring scads of values, instead compiling the products of (2,2), (2,3), (2,5), (3,3), etc — as is our plan — we need to know when to stop.

Ok, perhaps we could stop and check every once in a while, but the sub-problem, restated, is that calculating the next sequential value is non-obvious. 5 x 5 x 5 = 125, with 3 factors, but earlier than that in the sequence we find 2 x 2 x 2 x 2 x 2 x 2 = 64 with 6 factors. Obviously the quantity of factors will not be the complete story.

Actually I believe that that power of 2 we used as an example is the key. Our sequence is constructed from numbers found as the product of multisets of numbers drawn from our limited pool of three values. These multisets will have increasing numbers of elements as our final sequence grows generally larger, but there can be no assumption that a number from a set of k elements will necessarily fall after all numbers from the sets with k-1 elements, and in fact we know this is not true. But what we do know is that in a given number line constructed from all sets of members sized 1 to k, that the smallest next number added to the number line will be the smallest value from the set composed of k+1 elements. The smallest number that can be created from the set of all multisets containing k+1 factors is that multiset using only the value 2 repeated k+1 times: 2^k+1, so we can therefore conclude that the number line for all sets less than k members, for those values less than 2^k+1, is complete and ordered, and can be safely used.

We have now established 2^k+1 – 1 as an upper bound beyond which we cannot be certain that our number line is complete, but below which, and including, we can.

PERL 5 SOLUTION

Because we need to create a very large number of combinations, we will pull out the big guns and use the combinations_with_repetition() function from Algorithm::Combinatorics. This will give us our required combinations quickly without breaking the bank in memory. Likewise the List::Util function product() will multiply all the factors for us to get our result.

At each set of multisets containing a given quantity of factors, the new additions to the number line are pushed onto the list and sorted once complete, and the number of safe values is computed.

If more values are required to produce the desired index in the sequence the loop is repeated, adding additional factors until enough elements have been constructed beneath the upper bound.

The size of the sequence we can construct using this method is only limited by integer size in the system: for me the value S(12691) = 9,216,000,000,000,000,000, the largest number precisely calculable without using the bigint pragma.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';

use Algorithm::Combinatorics qw( combinations_with_repetition );
use List::Util               qw( product );

my $request = shift @ARGV // 12691;

$request--;

my @factors = (2, 3, 5);
my @inter = ( 1 );
my @seq;
my $fcount = 0;

while (++$fcount) {

    for my $iter (combinations_with_repetition( \@factors, $fcount)) {
        my $p = product $iter->@*;
       push @inter, $p;  
    }
    @seq = grep { $_ < 2**$fcount+1 } sort {$a<=>$b} @inter;
    last if scalar @seq > $request;
}

say "requested index, 1-based count: ", $request+1;
say "sequence value:  $seq[$request]";

say "sequence computed to ", scalar @seq, " known values";
say "sequence:";
say $_ for @seq;

I chose a rather verbose output report:

requested index, 1-based count: 12691
sequence value:  9216000000000000000
sequence computed to 12691 known values
sequence:
1
2
3
4
5
6
8
9
10
12
15
16
18
20
24
25
27
30
    ...

---

episode two:
“No Room For Squares”

---

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.

Method

There are two ways to look at this problem that I see: the easy interpretation and the hard version. The easy problem, as in first example, is to identify a square in orthogonal alignment with the coordinate system. In the more complex version we should consider any square shape we can define with points, for example { (1,1), (5,2), (4,6), (0,5) } which is canted one unit counterclockwise.

So how can we go about mathematically identifying a square? It seems some properties of squares would be in order. To rattle off a few , a square has:

1. four vertex angles summing to 360°
2. parallel opposing edges
3. four equal angles at the vertices
4. four sides of equal length

These traits correspond to a square being, in increasingly constrained definition:

1. a quadrilateral
2. a parallelogram
3. a rectangle
4. a regular rectangle.

This description, of increasingly narrowing the definition of our polygon, isn’t quite perfect: the last constraint, of equilateral sides, without the previous requirement of equiangular vertices, identifies a rhombus. But you get the idea. It also follows that if the four equiangular vertices sum to 360°, the individual angles can only be right angles, at 90°.

What we don’t need to prove is all of these assertions, but only enough to eliminate any possibility that the shape is not a square. We can do this by showing that for the complete graph described by the four points, that is, theoretically, the four sides of the square and the two diagonals, we have four edges the same length and two edges also the same length. We could be more specific and require the two differing edges to hold the relationship 1:√2 to the more populous, but if the two alternate lengths are diagonals, they will need to be equal to form a square, and a little work shows that if they are not both either diagonals or edges they cannot be equal. Further, if neither is a diagonal the edges cannot be the same length without multiple vertices occupying the same position, and we no longer have a quadrilateral if a connecting edge has zero length.

Almost.

Unfortunately there does exist one polygon that defeats this analysis (see? I’m brutal about breaking my own algorithms too) and that is most easily described as taking an equilateral triangle, with three edges te same length, and extending a new unit-length edge from one vertex perpendicular to the opposing edge, out away from the triangle. These four lines are two sides and two diagonals of a concave polygon made by connecting the point on the far end of the new line to each of the two other vertices:

No one ever said the points needed to describe a convex polygon.

This suggests we need an additional check, but fortunately we can still avoid having to deal directly with the square root of 2, as we can derive the length of the two equal segments AC and CB.

The line CE has length

1 + (√3/2)

being the length of CD plus that of DE, and the length of AE is ½ the unit length, or ½ itself. Using Pythagoras’ theorem, the length of AC is then found to be

√(2+√3) ≅ 1.93

Whatever the actual value, the square root of the quantity 2 plus some positive value will always be greater than √2, so we can avoid making a direct equality with an irrational number. The square root of 2 is about 1.41, and the shape we’ve described only works in that single configuration, fixing the value of the AC and BC edges. So if we pick a nice, simple coefficient sitting between the lengths, say 1.5 times the unit value, we should be just fine.

PERL 5 SOLUTION

I describe the various steps in the procedure as we go in the comments. The first collects the edge lengths, and the second fails if we count more than two values. Because the Euclidean distances are calculated the same way, any floating-point math will share the same approximations should they arise. The third part standardize the ordering by count, and makes sure we have 4 main values; if this is the case the other value can only have 2 instances. Finally we do a quick check to make sure our pathological polygon hasn’t reared its head.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';


sub is_square ($pts) {
    my @pts = $pts->@*;
    my @dist;
    
    ## get distance list for all edges in complete graph of points
    for my $idx (0..2) {
        push @dist, map { euclidean( $pts[$idx], $pts[$_] )} ( $idx+1..3 )
    }
    
    ## makes sure only 2 values for length
    my ($v1, $c1, $v2, $c2) = ( shift @dist, 1, undef, 0);
    for (@dist) {
        if ( $_ == $v1 ) { $c1++; next }
        $v2 //= $_;
        if ( $_ == $v2 ) { $c2++; next }
        return 0;
    }

    ## order lengths to "sides" first, fail if not 4 
    if ( $c1 < $c2 ) { ($v1, $c1, $v2, $c2) = ($v2, $c2, $v1, $c1) } 
    return 0 unless $c1 == 4;
    
    ## fail unless 2 remaining sides are less than 1.5 x short side
    ## this is the concave polygon case
    return 0 unless $v2 < 1.5 * $v1;
    
    return 1;
}


sub euclidean ($pt1, $pt2) {
    return sqrt( ($pt1->[0] - $pt2->[0])**2 + ($pt1->[1] - $pt2->[1])**2 );
}

Raku Solution

The Raku is a straight port this time.

sub is_square ( @pts ) {
    my @distances;
    
    for 0..2 -> $idx {
        @distances.push: |($idx+1..3).map({ euclidean( @pts[$idx], @pts[$_] )})
    }
    ## makes sure we have only 2 values for length
    my ($v1, $c1, $v2, $c2) = @distances.shift, 1, False, 0;
    for @distances {
        if $_ == $v1     { $c1++; next }
        $v2 ||= $_;
        if $_ == $v2     { $c2++; next }
        return 0;
    }
    ## reorder lengths to edges, fail if $v1 is not 4 equal sides
    if $c1 < $c2 { ($v1, $c1, $v2, $c2) = ($v2, $c2, $v1, $c1) } 
    return 0 unless $c1 == 4;
    
    ## fail unless 2 remaining sides are less than 1.5 x short side
    ## this is the concave polygon case
    return 0 unless $v2 < 1.5 * $v1;
    
    return 1;
}

sub euclidean ( @pt1, @pt2 ) {
    sqrt( (@pt1[0]-@pt2[0])**2 + (@pt1[1]-@pt2[1])**2 );
}