Add polettix's solution to challenge-123

6 files changed, 191 insertions, 0 deletions

diff --git a/challenge-123/polettix/blog.txt b/challenge-123/polettix/blog.txt
new file mode 100644
index 0000000000..e8885eba97
--- /dev/null
+++ b/challenge-123/polettix/blog.txt
@@ -0,0 +1 @@
+https://github.polettix.it/ETOOBUSY/2021/07/28/pwc123-ugly-numbers/
diff --git a/challenge-123/polettix/blog1.txt b/challenge-123/polettix/blog1.txt
new file mode 100644
index 0000000000..3ce0ef5180
--- /dev/null
+++ b/challenge-123/polettix/blog1.txt
@@ -0,0 +1 @@
+https://github.polettix.it/ETOOBUSY/2021/07/29/pwc123-square-points/
diff --git a/challenge-123/polettix/perl/ch-1.pl b/challenge-123/polettix/perl/ch-1.pl
new file mode 100644
index 0000000000..fb5c42aa83
--- /dev/null
+++ b/challenge-123/polettix/perl/ch-1.pl
@@ -0,0 +1,25 @@
+#!/usr/bin/env perl
+use v5.24;
+use warnings;
+use experimental 'signatures';
+no warnings 'experimental::signatures';
+
+sub is_ugly ($k) {
+   for my $d (2, 3, 5) {
+      $k /= $d until $k % $d;
+   }
+   return $k == 1;
+}
+
+sub ugly_number_at_position ($n) {
+   die "invalid input '$n'\n" if $n !~ m{\A [1-9]\d* \z}mxs;
+   state $cache = [1..6];
+   while ($n > $cache->@*) {
+      my $c = 1 + $cache->[-1];
+      $c++ until is_ugly($c);
+      push $cache->@*, $c;
+   }
+   return $cache->[$n - 1];
+}
+
+say ugly_number_at_position(shift || 8);
diff --git a/challenge-123/polettix/perl/ch-2.pl b/challenge-123/polettix/perl/ch-2.pl
new file mode 100644
index 0000000000..9bf00573ba
--- /dev/null
+++ b/challenge-123/polettix/perl/ch-2.pl
@@ -0,0 +1,47 @@
+#!/usr/bin/env perl
+use v5.24;
+use warnings;
+use experimental 'signatures';
+no warnings 'experimental::signatures';
+use constant False => 0;
+use constant True  => 1;
+
+use constant tolerance => 1e-7;
+
+package Vector2D {
+   use overload
+     '-' => sub ($u, $v, $x) { v([ map { $u->[$_] - $v->[$_] } 0, 1 ]) },
+     '*' => sub ($u, $v, $x) { $u->dot($v) };
+
+   sub dot ($S, $t)   { return $S->[0] * $t->[0] + $S->[1] * $t->[1] }
+   sub length_2 ($S)  { return $S->dot($S) }
+   sub v ($v)         { return bless [$v->@*], __PACKAGE__ }
+}
+
+sub is_sequence_a_square (@points) {
+   my $previous = $points[1] - $points[0];
+   for my $i (1 .. $#points - 1) {
+      my $current = $points[$i + 1] - $points[$i];
+      return False if $previous->length_2 != $current->length_2;
+      return False if $previous * $current > tolerance;
+      $previous = $current;
+   }
+   return True;
+}
+
+sub is_square (@points) {
+   state $permutations = [
+      [0, 2, 1, 3],
+      [0, 1, 2, 3],
+      [0, 2, 3, 1],
+   ];
+   for my $permutation ($permutations->@*) {
+      my @arrangement = map { Vector2D::v($_) } @points[@$permutation];
+      return 1 if is_sequence_a_square(@arrangement);
+   }
+   return 0;
+}
+
+say is_square([10, 20], [20, 20], [20, 10], [10, 10]);
+say is_square([12, 24], [16, 10], [20, 12], [18, 16]);
+say is_square([0, 0], [1, 1], [0, 2], [-1, 1]);
diff --git a/challenge-123/polettix/raku/ch-1.raku b/challenge-123/polettix/raku/ch-1.raku
new file mode 100644
index 0000000000..04b87fee6a
--- /dev/null
+++ b/challenge-123/polettix/raku/ch-1.raku
@@ -0,0 +1,38 @@
+#!/usr/bin/env raku
+use v6;
+
+# check that $x is of the form 2^x * 3^y * 5^z
+sub is-ugly (Int() $k is copy) {
+   # remove all 2, 3, and 5 factors in $k
+   for 2, 3, 5 -> $d {
+      $k /= $d while $k %% $d;
+   }
+
+   # if we're left with anything that's not 1, the number is *not* ugly
+   return $k == 1;
+}
+
+sub ugly-number-at-position (Int:D $n where * > 0) {
+   # keep a cache of values for fun and profit
+   state @cache = 1 .. 6;
+
+   # We add elements to the cache as we need them, otherwise leveraging
+   # previous calculations
+   while $n > @cache.elems {
+      # we start testing immediately after the latest element we put
+      my $c = 1 + @cache[*-1];
+
+      # anything that yields a rest when divided by 2 and by 3 and by 5
+      # is not ugly and gets us to look for the next candidate
+      $c++ until is-ugly($c);
+
+      # our candidate $c is divisible by one of 2, 3, or 5, so it's
+      # "ugly" and we add it to the lot, in order
+      @cache.push: $c;
+   }
+
+   # our input $n has an off-by-one difference from how we index arrays
+   return @cache[$n - 1];
+}
+
+sub MAIN (Int $n = 8) { put ugly-number-at-position($n) }
diff --git a/challenge-123/polettix/raku/ch-2.raku b/challenge-123/polettix/raku/ch-2.raku
new file mode 100644
index 0000000000..e35b9cf1d3
--- /dev/null
+++ b/challenge-123/polettix/raku/ch-2.raku
@@ -0,0 +1,79 @@
+#!/usr/bin/env raku
+use v6;
+
+# comparing stuff might be tricky with computer representation of numbers
+my \tolerance = 1e-7;
+
+# a tiny class for handling a limited set of vector operations
+class Vector {
+   has @.cs is built is required;
+
+   # "dot", i.e. scalar, product
+   method dot (Vector $a) { return [+](self.cs »*« $a.cs) }
+
+   # the *square* of the length is all we need in our solution
+   method length_2 ()     { return self.dot(self) }
+}
+
+# difference between vectors, uses stock constructor from Vector
+multi sub infix:<->(Vector $a, Vector $b) {
+   Vector.new(cs => [$a.cs »-« $b.cs]);
+}
+
+# eye candy for invoking the scalar ("dot") product
+multi sub infix:<*>(Vector $a, Vector $b) { $a.dot($b) }
+
+# check if a sequence of points represents a sequence of consecutive
+# vertices of a square.
+#
+# Consecutive pairs define the candidate square's sides. Consecutive
+# candidate square sides MUST be:
+# - same length (or same length squared, which is equivalent)
+# - orthogonal to each other (scalar product is zero)
+sub is-sequence-a-square (@points is copy) {
+
+   # comparing candidate sides means that we consider a "previous" side
+   # and a "current" one. A side is defined as the vector resulting from
+   # the difference of two consecutive points.
+   my $previous = @points[1] - @points[0];
+
+   # we just need to compare 3 sides, if they comply then the 4th will too
+   for 1, 2 -> $i {
+      my $current = @points[$i + 1] - @points[$i];
+
+      # check if sides have the same length (squared)
+      return False if $previous.length_2 != $current.length_2;
+
+      # approximation might give surprises, we'll accept as orthogonal
+      # sides whose scalar product is below our tolerance
+      return False if $previous * $current > tolerance;
+
+      # prepare for next iteration
+      $previous = $current;
+   }
+
+   # three sides are compliant, it's a square!
+   return True;
+}
+
+# check if a bunch of points form a square. They can be in any order.
+sub is-square (*@points) {
+
+   # try out permutations of the inputs that can yield a square. We fix
+   # point #0 and only consider one permutation for each of the other
+   # points as the opposite, ignoring the other because symmetric.
+   state @permutations = (
+      [0, 2, 1, 3],  # 0 and 1 are opposite
+      [0, 1, 2, 3],  # 0 and 2 are opposite
+      [0, 2, 3, 1],  # 0 and 3 are opposite
+   );
+   for @permutations -> $permutation {
+      my @arrangement = @points[@$permutation].map({Vector.new(cs => @$_)});
+      return 1 if is-sequence-a-square(@arrangement);
+   }
+   return 0;
+}
+
+say is-square($(10, 20), $(20, 20), $(20, 10), $(10, 10));
+say is-square($(12, 24), $(16, 10), $(20, 12), $(18, 16));
+say is-square($(0, 0), $(1, 1), $(0, 2), $(-1, 1));