6 files changed, 205 insertions, 0 deletions
diff --git a/challenge-140/polettix/blog.txt b/challenge-140/polettix/blog.txt
new file mode 100644
index 0000000000..9154b31bd8
--- /dev/null
+++ b/challenge-140/polettix/blog.txt
@@ -0,0 +1 @@
+https://github.polettix.it/ETOOBUSY/2021/11/24/pwc140-add-binary/
diff --git a/challenge-140/polettix/blog1.txt b/challenge-140/polettix/blog1.txt
new file mode 100644
index 0000000000..fca7709ef5
--- /dev/null
+++ b/challenge-140/polettix/blog1.txt
@@ -0,0 +1 @@
+https://github.polettix.it/ETOOBUSY/2021/11/25/pwc140-multiplication-table/
diff --git a/challenge-140/polettix/perl/ch-1.pl b/challenge-140/polettix/perl/ch-1.pl
new file mode 100644
index 0000000000..509c326f23
--- /dev/null
+++ b/challenge-140/polettix/perl/ch-1.pl
@@ -0,0 +1,29 @@
+#!/usr/bin/env perl
+use v5.24;
+use warnings;
+use experimental 'signatures';
+no warnings 'experimental::signatures';
+
+package Bin;
+use overload
+   '+' => sub ($A, $B, @whatever) {
+      my @A = split m{}mxs, $$A;
+      my @B = split m{}mxs, $$B;
+      my @result;
+      my $carry = 0;
+      while (@A || @B) {
+         my $sum = $carry + (pop(@A) // 0) + (pop(@B) // 0);
+         unshift @result, $sum & 0x01;
+         $carry = $sum >> 1;
+      }
+      unshift @result, $carry if $carry;
+      @result = (0) unless @result;
+      return Bin->new(join '', @result);
+   },
+   '""' => sub ($x, @whatever) { '' . $$x };
+sub new ($p, $x) { return bless \$x, $p }
+
+package main;
+sub Bin ($x) { return Bin->new($x) }
+
+say Bin($ARGV[0] // 11) + Bin($ARGV[1] // 1);
diff --git a/challenge-140/polettix/perl/ch-2.pl b/challenge-140/polettix/perl/ch-2.pl
new file mode 100644
index 0000000000..ebe3b6320e
--- /dev/null
+++ b/challenge-140/polettix/perl/ch-2.pl
@@ -0,0 +1,93 @@
+#!/usr/bin/env perl
+use v5.24;
+use warnings;
+use experimental 'signatures';
+no warnings 'experimental::signatures';
+
+my ($i, $j, $k) = @ARGV;
+$i //= 2;
+$j //= 3;
+$k //= 4;
+
+say multiplication_table_pq($i, $j, $k);
+say multiplication_table_bf($i, $j, $k) if $k < 2000;
+
+sub multiplication_table_bf ($i, $j, $k) {
+   my @prods;
+   for my $I (1 .. min($i, $k)) {
+      for my $J (1 .. min($j, $k)) {
+         push @prods, $I * $J;
+      }
+   }
+   @prods = sort {$a <=> $b} @prods;
+   return $prods[$k - 1];
+}
+
+sub max ($x, $y) { $x > $y ? $x : $y }
+sub min ($x, $y) { $x < $y ? $x : $y }
+
+sub multiplication_table_pq ($i, $j, $k) {
+   die "out of range (too low!)\n" if $k == 0;
+   die "out of range (too high!)\n" if $k > $i * $j;
+
+   return $k if $k <= 2 || $k == $i * $j;
+   return max($i * ($j - 1), ($i - 1) * $j) if $k == $i * $j - 1;
+
+   my $pq = BPQ->new(
+      before => sub ($x, $y) { $x->[0] < $y->[0] },
+      items  => [[1, 1, 1]],
+   );
+   my %seen = ('1.1' => 1); # just to give the gist of it...
+   while ($k > 1) {
+      my ($p, $I, $J) = $pq->dequeue->@*;
+      for my $deltas ([0, 1], [1, 0]) {
+         my $I_ = $I + $deltas->[0];
+         next if $I_ > $i;
+         my $J_ = $J + $deltas->[1];
+         next if $J_ > $j;
+         next if $seen{"$I_.$J_"}++;
+         $pq->enqueue([$I_ * $J_, $I_, $J_]);
+      }
+      --$k;
+   }
+   my ($result) = $pq->dequeue->@*;
+   return $result;
+}
+
+package BPQ;
+sub dequeue;    # see below
+sub enqueue;    # see below
+sub is_empty    { return !$#{$_[0]{items}} }
+sub top         { return $#{$_[0]{items}} ? $_[0]{items}[1] : () }
+sub new;        # see below
+sub size        { return $#{$_[0]{items}} }
+
+sub dequeue {    # includes "sink"
+   my ($is, $before, $k) = (@{$_[0]}{qw< items before >}, 1);
+   return unless $#$is;
+   my $r = ($#$is > 1) ? (splice @$is, 1, 1, pop @$is) : pop @$is;
+   while ((my $j = $k * 2) <= $#$is) {
+      ++$j if ($j < $#$is) && $before->($is->[$j + 1], $is->[$j]);
+      last if $before->($is->[$k], $is->[$j]);
+      (@{$is}[$j, $k], $k) = (@{$is}[$k, $j], $j);
+   }
+   return $r;
+} ## end sub dequeue
+
+sub enqueue {    # includes "swim"
+   my ($is, $before) = (@{$_[0]}{qw< items before >});
+   push @$is, $_[1];
+   my $k = $#$is;
+   (@{$is}[$k / 2, $k], $k) = (@{$is}[$k, $k / 2], int($k / 2))
+     while ($k > 1) && $before->($is->[$k], $is->[$k / 2]);
+} ## end sub enqueue
+
+sub new {
+   my $package = shift;
+   my $self = bless {((@_ && ref($_[0])) ? %{$_[0]} : @_)}, $package;
+   $self->{before} ||= sub { $_[0] < $_[1] };
+   (my $is, $self->{items}) = ($self->{items} || [], ['-']);
+   $self->enqueue($_) for @$is;
+   return $self;
+} ## end sub new
+1;
diff --git a/challenge-140/polettix/raku/ch-1.raku b/challenge-140/polettix/raku/ch-1.raku
new file mode 100644
index 0000000000..eacae34208
--- /dev/null
+++ b/challenge-140/polettix/raku/ch-1.raku
@@ -0,0 +1,8 @@
+#!/usr/bin/env raku
+use v6;
+subset Bin of Str where * ~~ /^ <[0 1]>+ $/;
+sub add-binary (Bin() $a, Bin() $b) {
+   return ($a.parse-base(2) + $b.parse-base(2)).base(2);
+}
+multi sub infix:<+> (Bin $A, Bin $B) { add-binary($A, $B) }
+sub MAIN (Bin() $A = 101, Bin() $B = 11) { put $A + $B }
diff --git a/challenge-140/polettix/raku/ch-2.raku b/challenge-140/polettix/raku/ch-2.raku
new file mode 100644
index 0000000000..b5583c30a8
--- /dev/null
+++ b/challenge-140/polettix/raku/ch-2.raku
@@ -0,0 +1,73 @@
+#!/usr/bin/env raku
+use v6;
+
+class BasicPriorityQueue {
+   has @!items;
+   has &!before;
+
+   submethod BUILD (:&!before = {$^a < $^b}, :@items) {
+      @!items = '-';
+      self.enqueue($_) for @items;
+   }
+
+   #method dequeue ($obj) <-- see below
+   method elems { @!items.end }
+   # method enqueue ($obj) <-- see below
+   method is-empty { @!items.elems == 1 }
+   method size  { @!items.end }
+   method top { @!items.end ?? @!items[1] !! Any }
+
+   method dequeue () { # includes "sink"
+      return unless @!items.end;
+      my $r = @!items.pop;
+      ($r, @!items[1]) = (@!items[1], $r) if @!items.end >= 1;
+      my $k = 1;
+      while (my $j = $k * 2) <= @!items.end {
+         ++$j if $j < @!items.end && &!before(@!items[$j + 1], @!items[$j]);
+         last if &!before(@!items[$k], @!items[$j]);
+         (@!items[$j, $k], $k) = (|@!items[$k, $j], $j);
+      }
+      return $r;
+   }
+
+   method enqueue ($obj) { # includes "swim"
+      @!items.push: $obj;
+      my $k = @!items.end;
+      (@!items[$k/2, $k], $k) = (|@!items[$k, $k/2], ($k/2).Int)
+         while $k > 1 && &!before(@!items[$k], @!items[$k/2]);
+      return self;
+   }
+}
+
+sub MAIN (Int $i  = 2, Int $j = 3, Int $k = 4) {
+   put multiplication-table($i, $j, $k);
+}
+
+sub multiplication-table (Int $i, Int $j, Int $k is copy) {
+   die "out of range (too low!)\n" if $k == 0;
+   die "out of range (too high!)\n" if $k > $i * $j;
+
+   return $k if $k <= 2 || $k == $i * $j;
+   return max($i * ($j - 1), ($i - 1) * $j) if $k == $i * $j - 1;
+
+   my $pq = BasicPriorityQueue.new(
+      items  => [[1, 1, 1],],
+      before => { $^a[0] < $^b[0] },
+   );
+   my %seen = '1.1' => 1;
+   while ($k > 1) {
+      my $item = $pq.dequeue;
+      my ($p, $I, $J) = $item.Slip;
+      for [0, 1], [1, 0] -> $deltas {
+         my $I_ = $I + $deltas[0];
+         next if $I_ > $i;
+         my $J_ = $J + $deltas[1];
+         next if $J_ > $j;
+         next if %seen{"$I_.$J_"}++;
+         $pq.enqueue([$I_ * $J_, $I_, $J_]);
+      }
+      --$k;
+   }
+   my ($result) = $pq.dequeue;
+   return $result;
+}