Add polettix's solutions to PWC093

4 files changed, 91 insertions, 0 deletions

diff --git a/challenge-093/polettix/blog.txt b/challenge-093/polettix/blog.txt
new file mode 100644
index 0000000000..25abccffb5
--- /dev/null
+++ b/challenge-093/polettix/blog.txt
@@ -0,0 +1 @@
+https://github.polettix.it/ETOOBUSY/2020/12/28/pwc093-max-points/
diff --git a/challenge-093/polettix/blog1.txt b/challenge-093/polettix/blog1.txt
new file mode 100644
index 0000000000..f290b02305
--- /dev/null
+++ b/challenge-093/polettix/blog1.txt
@@ -0,0 +1 @@
+https://github.polettix.it/ETOOBUSY/2020/12/29/pwc093-sum-path/
diff --git a/challenge-093/polettix/perl/ch-1.pl b/challenge-093/polettix/perl/ch-1.pl
new file mode 100644
index 0000000000..4379e7ca49
--- /dev/null
+++ b/challenge-093/polettix/perl/ch-1.pl
@@ -0,0 +1,46 @@
+#!/usr/bin/env perl
+use 5.024;
+use warnings;
+use experimental qw< postderef signatures >;
+no warnings qw< experimental::postderef experimental::signatures >;
+use List::Util 'max';
+
+sub max_points ($inputs) {
+   my $max = 0;
+   my %skip;
+   for my $i (0 .. $#$inputs - 1) {
+      next if $skip{$i};    # it's coincident with some points before
+      my ($x, $y) = $inputs->[$i]->@*;
+      my %count_for;
+      my $coincident = 1;    # the point itself
+      for my $j ($i + 1 .. $#$inputs) {
+         my $q = $inputs->[$j];
+         my ($dx, $dy) = ($q->[0] - $x, $q->[1] - $y);
+         if ($dx == 0) {
+            if ($dy == 0) { $skip{$j}++; $coincident++ }
+            else          { $count_for{'0,1'}++ }
+         }
+         else {
+            ($dx, $dy) = (-$dx, -$dy) if $dx < 0;
+            my $gcd =
+                $dy > 0 ? gcd($dx, $dy)
+              : $dy < 0 ? gcd($dx, -$dy)
+              :           $dx;
+            $count_for{($dx / $gcd) . ',' . ($dy / $gcd)}++;
+         } ## end else [ if ($dx == 0) ]
+      } ## end for my $j ($i + 1 .. $#$inputs)
+      my $rmax = $coincident + max(0, values %count_for);
+      $max = $rmax if $rmax > $max;
+   } ## end for my $i (0 .. $#$inputs...)
+   return $max;
+} ## end sub max_points ($inputs)
+
+sub gcd { my ($A, $B) = @_; ($A, $B) = ($B % $A, $A) while $A; return $B }
+
+say max_points([[1, 1], [2, 2], [3, 3]]);
+say max_points(
+   [
+      [1, 1], [2, 2], [3, 1], [1, 3], [5, 3], [4, 4],
+      [3, 3], [4, 0], [0, 4], [0, 4]
+   ]
+);
diff --git a/challenge-093/polettix/perl/ch-2.pl b/challenge-093/polettix/perl/ch-2.pl
new file mode 100644
index 0000000000..c4abbcf659
--- /dev/null
+++ b/challenge-093/polettix/perl/ch-2.pl
@@ -0,0 +1,43 @@
+#!/usr/bin/env perl
+use 5.024;
+use warnings;
+use experimental qw< postderef signatures >;
+no warnings qw< experimental::postderef experimental::signatures >;
+
+sub sum_path ($input) {
+   my @rows = map { [ split m{}mxs ] } split m{\n}mxs, $input;
+   my $root = 0;
+   $root++ while $rows[0][$root] eq ' ';
+   return _sum_path_r(\@rows, 0, $root, 0);
+}
+
+sub _sum_path_r($rows, $rid, $cid, $parent) {
+   my $so_far = $parent + $rows->[$rid][$cid];
+   my $sub_sum = 0;
+   if ($rid < $#$rows) { # there can be something more
+      $rid++;
+      $sub_sum += _sum_path_r($rows, $rid + 1, $cid - 2, $so_far)
+         if $cid > 0 && $rows->[$rid][$cid - 1] ne ' ';
+      $sub_sum += _sum_path_r($rows, $rid + 1, $cid + 2, $so_far)
+         if $cid < $#{$rows->[$rid]} && $rows->[$rid][$cid + 1] ne ' ';
+   }
+   return $sub_sum || $so_far;
+}
+
+my $tree = <<'END';
+     1
+    /
+   2
+  / \
+ 3   4
+END
+
+$tree = <<'END';
+     1
+    / \
+   2   3
+  /   / \
+ 4   5   6
+END
+
+say sum_path($tree);