Merge pull request #2475 from polettix/pwc081

Add polettix's solution for PWC081

4 files changed, 119 insertions, 0 deletions

diff --git a/challenge-081/polettix/blog.txt b/challenge-081/polettix/blog.txt
new file mode 100644
index 0000000000..70d6168bed
--- /dev/null
+++ b/challenge-081/polettix/blog.txt
@@ -0,0 +1 @@
+https://github.polettix.it/ETOOBUSY/2020/10/08/pwc081-common-base-string/
diff --git a/challenge-081/polettix/blog1.txt b/challenge-081/polettix/blog1.txt
new file mode 100644
index 0000000000..2577d90c34
--- /dev/null
+++ b/challenge-081/polettix/blog1.txt
@@ -0,0 +1 @@
+https://github.polettix.it/ETOOBUSY/2020/10/09/pwc081-frequency-sort/
diff --git a/challenge-081/polettix/perl/ch-1.pl b/challenge-081/polettix/perl/ch-1.pl
new file mode 100644
index 0000000000..b48ea56f87
--- /dev/null
+++ b/challenge-081/polettix/perl/ch-1.pl
@@ -0,0 +1,69 @@
+#!/usr/bin/env perl
+use 5.024;
+use warnings;
+use experimental qw< postderef signatures >;
+no warnings qw< experimental::postderef experimental::signatures >;
+
+sub proper_factors ($n) { grep { $n % $_ == 0} (2 .. int($n/2))}
+
+sub min_period ($string) {
+   my $n = length $string;
+
+   CANDIDATE:
+   for my $k (1, proper_factors($n)) {
+      my $m = $n / $k; # sub-sequences we have to test
+      for my $i (0 .. $k - 1) { # sub-sequence iterator
+         my $char = substr $string, $i, 1;
+         for my $s (1 .. $m - 1) { # sequence iterator
+            next CANDIDATE if $char ne substr $string, $k * $s + $i, 1;
+         }
+      }
+      # yay!
+      return $k;
+   }
+
+   # nothing found, minimum period is the string's length
+   return $n;
+}
+
+sub min_common_base ($A, $B) {
+   my $pA = min_period($A);
+   my $pB = min_period($B);
+   return if $pB != $pA; # they must be equal
+   my $candidate = substr $A, 0, $pA;
+   return $candidate if $candidate eq substr $B, 0, $pB;
+   return;
+}
+
+sub common_bases ($A, $B) {
+   defined(my $b = min_common_base($A, $B)) or return;
+
+   my $l = length $b;
+   my ($rA, $rB) = map {length($_) / $l} ($A, $B);
+   ($rA, $rB) = ($rB, $rA) if $rA > $rB;
+
+   return map { $rB % $_ ? () : $b x $_ } (1, proper_factors($rA), $rA);
+}
+
+sub common_bases_brute_force ($A, $B) {
+   my ($lA, $lB) = (length($A), length($B));
+   ($A, $B, $lA, $lB) = ($B, $A, $lB, $lA) if $lA > $lB;
+   my @retval;
+   CANDIDATE:
+   for my $l (1 .. int($lA / 2), $lA) {
+      next CANDIDATE if ($lA % $l) || ($lB % $l);
+      my $base = substr $A, 0, $l;
+      for my $s ($A, $B) {
+         next CANDIDATE if $s ne $base x (length($s) / $l);
+      }
+      push @retval, $base;
+   }
+   return @retval;
+}
+
+for my $input (
+   ['abcdabcd', 'abcdabcdabcdabcd'],
+   ['aaa', 'aa'],
+){
+   say '(', join(', ', map {qq{"$_"}} common_bases_brute_force($input->@*)), ')';
+}
diff --git a/challenge-081/polettix/perl/ch-2.pl b/challenge-081/polettix/perl/ch-2.pl
new file mode 100644
index 0000000000..46124837c4
--- /dev/null
+++ b/challenge-081/polettix/perl/ch-2.pl
@@ -0,0 +1,48 @@
+#!/usr/bin/env perl
+use 5.024;
+use warnings;
+use experimental qw< postderef signatures >;
+no warnings qw< experimental::postderef experimental::signatures >;
+use autodie;
+
+sub frequency_sort ($input = 'input') {
+
+   # Allow for getting an open filehandle as input
+   my $fh = ref($input) ? $input : do {open my $fh, '<', $input; $fh};
+
+   # Count occurrences for all words, just for starters
+   my %count_for;
+   while (<$fh>) {
+      s{(?: [."(),] | 's | -- )+}{ }gmxs; # ignore stuff
+      $count_for{$_}++ for grep {length > 0} split m{\s+}mxs;
+   }
+
+   # Invert "count by word" to "words by count"
+   my %words_for;
+   while (my ($word, $count) = each %count_for) {
+      push $words_for{$count}->@*, $word;
+   }
+
+   say join "\n\n", map {
+      # Sort words for $count lexicographically
+      join ' ', $_, sort {$a cmp $b} $words_for{$_}->@*;
+   } sort {$a <=> $b} keys %words_for;
+}
+
+frequency_sort(\*DATA);
+
+__DATA__
+West Side Story
+
+The award-winning adaptation of the classic romantic tragedy "Romeo and
+Juliet". The feuding families become two warring New York City gangs,
+the white Jets led by Riff and the Latino Sharks, led by Bernardo. Their
+hatred escalates to a point where neither can coexist with any form of
+understanding. But when Riff's best friend (and former Jet) Tony and
+Bernardo's younger sister Maria meet at a dance, no one can do anything
+to stop their love. Maria and Tony begin meeting in secret, planning to
+run away. Then the Sharks and Jets plan a rumble under the
+highway--whoever wins gains control of the streets. Maria sends Tony to
+stop it, hoping it can end the violence. It goes terribly wrong, and
+before the lovers know what's happened, tragedy strikes and doesn't stop
+until the climactic and heartbreaking ending.