From 65c1ba6edf6828bcc81222fa888b3fc63667e10a Mon Sep 17 00:00:00 2001
From: Flavio Poletti <flavio@polettix.it>
Date: Sun, 26 Dec 2021 08:50:59 +0100
Subject: Add polettix's solution to challenge-144

---
 challenge-144/polettix/blog.txt       |  1 +
 challenge-144/polettix/blog1.txt      |  1 +
 challenge-144/polettix/perl/ch-1.pl   | 36 ++++++++++++++++++++++++++++
 challenge-144/polettix/perl/ch-2.pl   | 33 +++++++++++++++++++++++++
 challenge-144/polettix/raku/ch-1.raku | 45 +++++++++++++++++++++++++++++++++++
 challenge-144/polettix/raku/ch-2.raku | 25 +++++++++++++++++++
 6 files changed, 141 insertions(+)
 create mode 100644 challenge-144/polettix/blog.txt
 create mode 100644 challenge-144/polettix/blog1.txt
 create mode 100644 challenge-144/polettix/perl/ch-1.pl
 create mode 100644 challenge-144/polettix/perl/ch-2.pl
 create mode 100644 challenge-144/polettix/raku/ch-1.raku
 create mode 100644 challenge-144/polettix/raku/ch-2.raku

diff --git a/challenge-144/polettix/blog.txt b/challenge-144/polettix/blog.txt
new file mode 100644
index 0000000000..ae4a919047
--- /dev/null
+++ b/challenge-144/polettix/blog.txt
@@ -0,0 +1 @@
+https://github.polettix.it/ETOOBUSY/2021/12/22/pwc144-semiprime/
diff --git a/challenge-144/polettix/blog1.txt b/challenge-144/polettix/blog1.txt
new file mode 100644
index 0000000000..b4e8d651a4
--- /dev/null
+++ b/challenge-144/polettix/blog1.txt
@@ -0,0 +1 @@
+https://github.polettix.it/ETOOBUSY/2021/12/23/pwc144-ulam-sequence/
diff --git a/challenge-144/polettix/perl/ch-1.pl b/challenge-144/polettix/perl/ch-1.pl
new file mode 100644
index 0000000000..0faa3d1f51
--- /dev/null
+++ b/challenge-144/polettix/perl/ch-1.pl
@@ -0,0 +1,36 @@
+#!/usr/bin/env perl
+use v5.24;
+use warnings;
+use experimental 'signatures';
+no warnings 'experimental::signatures';
+
+my $limit = shift // 100;
+say join ', ', semiprimes_upto_constructive_tight($limit);
+
+sub semiprimes_upto_constructive_tight ($limit) {
+   my @ps = primes_upto(1 + $limit / 2);
+   my @retval;
+   for my $li (0 .. $#ps) {
+      my $n_start = @retval;
+      for my $hi ($li .. $#ps) {
+         my $prod = $ps[$li] * $ps[$hi];
+         last if $prod > $limit;
+         push @retval, $prod;
+      }
+      last if @retval == $n_start;
+   }
+   return sort { $a <=> $b } @retval;
+}
+
+sub primes_upto ($n) {
+   return if $n < 2;
+   my @ps = 2;
+   my $candidate = 3;
+   CANDIDATE:
+   while ($candidate <= $n) {
+      for my $p (@ps) { next CANDIDATE unless $candidate % $p }
+      push @ps, $candidate;
+   }
+   continue { $candidate += 2 }
+   return @ps;
+}
diff --git a/challenge-144/polettix/perl/ch-2.pl b/challenge-144/polettix/perl/ch-2.pl
new file mode 100644
index 0000000000..c12c1086d5
--- /dev/null
+++ b/challenge-144/polettix/perl/ch-2.pl
@@ -0,0 +1,33 @@
+#!/usr/bin/env perl
+use v5.24;
+use warnings;
+use experimental 'signatures';
+no warnings 'experimental::signatures';
+
+sub ulam_iterator ($v, $w) {
+   my @items = ($v, $w);
+   my $n = 0;
+   return sub {
+      ITEM:
+      while ($n > $#items) {
+         my %count;
+         for my $i (0 .. $#items - 1) {
+            for my $j (reverse($i + 1 .. $#items)) {
+               my $sum = $items[$i] + $items[$j];
+               last if $sum <= $items[-1];
+               $count{$sum}++;
+            }
+         }
+         for my $new (sort { $a <=> $b } keys %count) {
+            next unless $count{$new} == 1;
+            push @items, $new;
+            next ITEM;
+         }
+      }
+      return $items[$n++];
+   };
+}
+
+my @seeds = @ARGV == 2 ? @ARGV : (1, 2);
+my $it = ulam_iterator(@seeds);
+say join ', ', map { $it->() } 1 .. 10;
diff --git a/challenge-144/polettix/raku/ch-1.raku b/challenge-144/polettix/raku/ch-1.raku
new file mode 100644
index 0000000000..9992c182bd
--- /dev/null
+++ b/challenge-144/polettix/raku/ch-1.raku
@@ -0,0 +1,45 @@
+#!/usr/bin/env raku
+use v6;
+sub MAIN (Int:D $limit where * > 0 = 100) {
+   semiprimes-upto-constructive-tight($limit).join(', ').put;
+   semiprimes-upto-constructive-flow($limit).join(', ').put;
+   semiprimes-upto-deconstruct($limit).join(', ').put;
+}
+
+sub semiprimes-upto-constructive-tight ($limit) {
+   my @ps = (2 .. 1 + ($limit / 2).Int).grep: *.is-prime;
+   my @retval;
+   for ^@ps -> $li {
+      my $n-start = @retval.elems;
+      for $li ..^ @ps -> $hi {
+         my $prod = @ps[$li] * @ps[$hi];
+         last if $prod > $limit;
+         @retval.push: $prod;
+      }
+      last if @retval.elems == $n-start;
+   }
+   return @retval.sort;
+}
+
+sub semiprimes-upto-constructive-flow ($limit) {
+   my @ps = (2 .. 1 + ($limit / 2).Int).grep: *.is-prime;
+   (@ps X @ps) # consider all pairs of those primes
+      .grep({$_[0] <= $_[1]}) # DRY
+      .map({[*] @$_})         # multiply them
+      .grep({$_ <= $limit})   # stay within the limit
+      .sort;                  # format and cook
+}
+
+sub semiprimes-upto-deconstruct ($limit) {
+   my @ps;
+   gather for 2 .. $limit -> $candidate {
+      if $candidate.is-prime { @ps.push: $candidate }
+      else {
+         for @ps -> $prime {
+            next unless $candidate %% $prime;
+            my $other = ($candidate / $prime).Int;
+            take $candidate if ($other >= $prime) && $other.is-prime;
+         }
+      }
+   };
+}
diff --git a/challenge-144/polettix/raku/ch-2.raku b/challenge-144/polettix/raku/ch-2.raku
new file mode 100644
index 0000000000..134e88bf55
--- /dev/null
+++ b/challenge-144/polettix/raku/ch-2.raku
@@ -0,0 +1,25 @@
+#!/usr/bin/env raku
+use v6;
+
+class Ulam {
+   has @!items is built;
+   has $!n = 0;
+
+   method new ($v, $w) { self.bless(items => [$v, $w]) }
+
+   method next () {
+      ITEM:
+      while $!n > @!items.end {
+         @!items.push: (@!items X @!items).grep({ $_[0] < $_[1] })
+            .map({$_.sum}).grep({$_ > @!items[*-1]})
+            .Bag.pairs.grep({.value == 1}).map({.key}).min;
+      }
+      return @!items[$!n++];
+   }
+}
+
+sub MAIN (*@args) {
+   my ($v, $w) = @args.elems == 2 ?? @args !! (1, 2);
+   my $ulam = Ulam.new($v, $w);
+   (1..10).map({$ulam.next}).join(', ').put;
+}
-- 
cgit