Merge pull request #5787 from polettix/polettix/pwc156

Add polettix's solution to challenge-156

8 files changed, 110 insertions, 1 deletions

diff --git a/challenge-156/polettix/blog.txt b/challenge-156/polettix/blog.txt
new file mode 100644
index 0000000000..401ac5ad59
--- /dev/null
+++ b/challenge-156/polettix/blog.txt
@@ -0,0 +1 @@
+https://github.polettix.it/ETOOBUSY/2022/03/16/pwc156-pernicious-numbers/
diff --git a/challenge-156/polettix/blog1.txt b/challenge-156/polettix/blog1.txt
new file mode 100644
index 0000000000..f6a93f4a79
--- /dev/null
+++ b/challenge-156/polettix/blog1.txt
@@ -0,0 +1 @@
+https://github.polettix.it/ETOOBUSY/2022/03/17/pwc156-weird-number/
diff --git a/challenge-156/polettix/perl/ch-1.pl b/challenge-156/polettix/perl/ch-1.pl
new file mode 100644
index 0000000000..a73f11d1be
--- /dev/null
+++ b/challenge-156/polettix/perl/ch-1.pl
@@ -0,0 +1,27 @@
+#!/usr/bin/env perl
+use v5.24;
+use warnings;
+use experimental 'signatures';
+no warnings 'experimental::signatures';
+
+use FindBin '$Bin';
+use lib "$Bin/local/lib/perl5";
+use ntheory 'is_prime';
+
+my $N = shift // 10;
+my @pernicious;
+my $k = 0;
+while (@pernicious < $N) {
+   push @pernicious, $k if is_pernicious($k);
+   ++$k;
+}
+say join ', ', @pernicious;
+
+sub is_pernicious ($n) {
+   my $count = 0;
+   while ($n) {
+      ++$count if $n & 1;
+      $n >>= 1;
+   }
+   return is_prime($count);
+}
diff --git a/challenge-156/polettix/perl/ch-2.pl b/challenge-156/polettix/perl/ch-2.pl
new file mode 100644
index 0000000000..e23a6df19c
--- /dev/null
+++ b/challenge-156/polettix/perl/ch-2.pl
@@ -0,0 +1,27 @@
+#!/usr/bin/env perl
+use v5.24;
+use warnings;
+use experimental 'signatures';
+no warnings 'experimental::signatures';
+
+use FindBin '$Bin';
+use lib "$Bin/local/lib/perl5";
+
+use Algorithm::Knapsack;
+use ntheory 'divisors';
+use List::Util 'sum';
+
+say $_, ' ', is_weird($_) for (@ARGV ? @ARGV : (12, 70));
+
+sub is_weird ($n) {
+   my @divs = reverse divisors($n);
+   shift @divs if @divs > 1;
+   return 0 if $n >= sum @divs;
+   my $ks = Algorithm::Knapsack->new(capacity => $n, weights => \@divs);
+   $ks->compute;
+   for my $solution ($ks->solutions) {
+      my $sum = sum @divs[$solution->@*];
+      return 0 if $sum == $n;
+   }
+   return 1;
+}
diff --git a/challenge-156/polettix/perl/cpanfile b/challenge-156/polettix/perl/cpanfile
index aa20fef593..18d0567b18 100644
--- a/challenge-156/polettix/perl/cpanfile
+++ b/challenge-156/polettix/perl/cpanfile
@@ -1,2 +1,2 @@
 requires 'Math::Prime::Util';
-requires 'List::MoreUtils';
+requires 'Algorithm::Knapsack';
diff --git a/challenge-156/polettix/perl/cpanfile.snapshot b/challenge-156/polettix/perl/cpanfile.snapshot
index 4927cf8387..d47aa9845a 100644
--- a/challenge-156/polettix/perl/cpanfile.snapshot
+++ b/challenge-156/polettix/perl/cpanfile.snapshot
@@ -1,5 +1,11 @@
 # carton snapshot format: version 1.0
 DISTRIBUTIONS
+  Algorithm-Knapsack-0.02
+    pathname: A/AN/ANDALE/Algorithm-Knapsack-0.02.tar.gz
+    provides:
+      Algorithm::Knapsack 0.02
+    requirements:
+      ExtUtils::MakeMaker 0
   Exporter-Tiny-1.002002
     pathname: T/TO/TOBYINK/Exporter-Tiny-1.002002.tar.gz
     provides:
diff --git a/challenge-156/polettix/raku/ch-1.raku b/challenge-156/polettix/raku/ch-1.raku
new file mode 100644
index 0000000000..e74c7ad288
--- /dev/null
+++ b/challenge-156/polettix/raku/ch-1.raku
@@ -0,0 +1,14 @@
+#!/usr/bin/env raku
+use v6;
+
+sub MAIN (Int:D $N = 10) {
+   my @pernicious;
+   my $k = 0;
+   while @pernicious < $N {
+      @pernicious.push: $k if is-pernicious($k);
+      ++$k;
+   }
+   @pernicious.join(', ').put;
+}
+
+sub is-pernicious (Int:D $n where * >= 0) { $n.base(2).comb.sum.is-prime }
diff --git a/challenge-156/polettix/raku/ch-2.raku b/challenge-156/polettix/raku/ch-2.raku
new file mode 100644
index 0000000000..b22bb44d86
--- /dev/null
+++ b/challenge-156/polettix/raku/ch-2.raku
@@ -0,0 +1,33 @@
+#!/usr/bin/env raku
+use v6;
+
+sub MAIN (*@args) {
+   my @inputs = @args ?? |@args !! (12, 70);
+   @inputs.map({
+      put $_, ' ', is-weird($_);
+   });
+}
+
+sub proper-divisors (Int:D $n) { (1..($n/2)).grep: $n %% * }
+
+sub is-weird (Int:D $n) {
+   my @divs = proper-divisors($n);
+   return 0 if @divs.sum <= $n;
+   loop {
+      my $sum = @divs.sum;
+      return 0 if $sum == $n;
+      return 1 if $sum < $n;
+      my $ms = @divs.pop;
+      my $target = $n - $ms;
+      for (^(2 ** @divs.elems)).reverse -> $k is copy {
+         my $sum = 0;
+         my $i = 0;
+         while $k > 0 {
+            $sum += @divs[$i] if $k +& 1;
+            return 0 if $target == $sum;
+            ++$i;
+            $k +>= 1;
+         }
+      }
+   }
+}