Add polettix's solution to challenge-152

6 files changed, 180 insertions, 0 deletions

diff --git a/challenge-152/polettix/blog.txt b/challenge-152/polettix/blog.txt
new file mode 100644
index 0000000000..9cbc627b1a
--- /dev/null
+++ b/challenge-152/polettix/blog.txt
@@ -0,0 +1 @@
+https://github.polettix.it/ETOOBUSY/2022/02/16/pwc152-triangle-sum-path/
diff --git a/challenge-152/polettix/blog1.txt b/challenge-152/polettix/blog1.txt
new file mode 100644
index 0000000000..c395c056d0
--- /dev/null
+++ b/challenge-152/polettix/blog1.txt
@@ -0,0 +1 @@
+https://github.polettix.it/ETOOBUSY/2022/02/17/pwc152-rectangle-area/
diff --git a/challenge-152/polettix/perl/ch-1.pl b/challenge-152/polettix/perl/ch-1.pl
new file mode 100644
index 0000000000..346426486f
--- /dev/null
+++ b/challenge-152/polettix/perl/ch-1.pl
@@ -0,0 +1,11 @@
+#!/usr/bin/env perl
+use v5.24;
+use warnings;
+use experimental 'signatures';
+no warnings 'experimental::signatures';
+use List::Util qw< sum min >;
+
+my @triangle = map { [split m{,}mxs] } @ARGV;
+say triangle_sum_path(@triangle);
+
+sub triangle_sum_path (@triangle) { sum map { min $_->@* } @triangle }
diff --git a/challenge-152/polettix/perl/ch-2.pl b/challenge-152/polettix/perl/ch-2.pl
new file mode 100644
index 0000000000..40e1e750c7
--- /dev/null
+++ b/challenge-152/polettix/perl/ch-2.pl
@@ -0,0 +1,34 @@
+#!/usr/bin/env perl
+use v5.24;
+use warnings;
+use experimental 'signatures';
+no warnings 'experimental::signatures';
+use List::Util qw< min max >;
+
+say rectangle_area([[-1, 0], [2, 2]], [[0, -1], [4, 4]]);
+say rectangle_area([[-3, -1], [1, 3]], [[-1, -3], [2, 2]]);
+
+sub rectangle_area ($r1, $r2) {
+   return area($r1) + area($r2) - area(intersection($r1, $r2));
+}
+
+sub area ($r) {
+   return 0 unless $r;
+   return ($r->[1][0] - $r->[0][0]) * ($r->[1][1] - $r->[0][1]);
+}
+
+sub intersection ($r1, $r2) {
+   my $bottom_left = [
+      max($r1->[0][0], $r2->[0][0]),
+      max($r1->[0][1], $r2->[0][1]),
+   ];
+   my $top_right = [
+      min($r1->[1][0], $r2->[1][0]),
+      min($r1->[1][1], $r2->[1][1]),
+   ];
+   my $min_difference = min(
+      $top_right->[0] - $bottom_left->[0],
+      $top_right->[1] - $bottom_left->[1],
+   );
+   return $min_difference > 0 ? [$bottom_left, $top_right] : undef;
+}
diff --git a/challenge-152/polettix/raku/ch-1.raku b/challenge-152/polettix/raku/ch-1.raku
new file mode 100644
index 0000000000..048963b0d1
--- /dev/null
+++ b/challenge-152/polettix/raku/ch-1.raku
@@ -0,0 +1,114 @@
+#!/usr/bin/env raku
+use v6;
+sub MAIN (*@args) {
+   my @triangle = @args».split(/ \, /)».Array;
+   put triangle-sum-path(@triangle);
+   put triangle-restricted-sum-path(@triangle);
+}
+
+sub triangle-sum-path (@triangle) { @triangle».min.sum }
+
+sub triangle-restricted-sum-path (@triangle) {
+   class Astar { ... }
+   my $max-last = @triangle[*-1].max;
+   my $astar = Astar.new(
+      distance => sub ($u, $v) {
+         return $v<goal> ?? 0 !! @triangle[$v<tier>][$v<index>];
+      },
+      successors => sub ($v) {
+         my $tier = $v<tier> + 1;
+         return hash(goal => 1) unless $tier <= @triangle.end;
+         my @retval = gather {
+            for 0 .. 1 -> $delta {
+               my $index = $v<index> + $delta;
+               take hash(tier => $tier, index => $index)
+                  if $index <= @triangle[$tier].end;
+            }
+         };
+         return @retval;
+      },
+      heuristic => sub ($u, $v) {
+         return $u<goal> ?? 0 !! $u<tier> < @triangle.end ?? $max-last !! 0;
+      },
+      identifier => sub ($v) {
+         return $v<goal> ?? 'goal' !! $v<tier index>.join(',');
+      },
+   );
+   my $triangle-sum-path = $astar.best-path(
+      hash(tier => 0, index => 0),
+      hash(goal => 1),
+   );
+   my $sum = 0;
+   for $triangle-sum-path.List -> $v {
+      last if $v<goal>;
+      $sum += @triangle[$v<tier>][$v<index>];
+   }
+   return $sum;
+}
+
+class Astar {
+   has (&!distance, &!successors, &!heuristic, &!identifier);
+
+   method best-path ($start!, $goal!) {
+      my ($id, $gid) = ($start, $goal).map: {&!identifier($^a)};
+      my %node-for = $id => {pos => $start, g => 0};
+      class PriorityQueue { ... }
+      my $queue = PriorityQueue.new;
+      $queue.enqueue($id, 0);
+      while ! $queue.is-empty {
+         my $cid = $queue.dequeue;
+         my $cx = %node-for{$cid};
+         next if $cx<visited>++;
+
+         return self!unroll($cx, %node-for) if $cid eq $gid;
+
+         my $cv = $cx<pos>;
+         for &!successors($cv) -> $sv {
+            my $sid = &!identifier($sv);
+            my $sx = %node-for{$sid} ||= {pos => $sv};
+            next if $sx<visited>;;
+            my $g = $cx<g> + &!distance($cv, $sv);
+            next if $sx<g>:exists && $g >= $sx<g>;
+            $sx<p> = $cid; # p is the id of "best previous"
+            $sx<g> = $g;   # with this cost
+            $queue.enqueue($sid, $g + &!heuristic($sv, $goal));
+         }
+      }
+      return ();
+   }
+
+   submethod BUILD (:&!distance!, :&!successors!,
+      :&!heuristic = &!distance, :&!identifier = {~$^a}) {}
+
+   method !unroll ($node is copy, %node-for) {
+      my @path = $node<pos>;
+      while $node<p>:exists {
+         $node = %node-for{$node<p>};
+         @path.unshift: $node<pos>;
+      }
+      return @path;
+   }
+
+   class PriorityQueue {
+      has @!items  = ('-');
+      method is-empty { @!items.end < 1 }
+      method dequeue () { # includes "sink"
+         return if @!items.end < 1;
+         my $r = @!items.end > 1 ?? @!items.splice(1, 1, @!items.pop)[0] !! @!items.pop;
+         my $k = 1;
+         while (my $j = $k * 2) <= @!items.end {
+            ++$j if $j < @!items.end && @!items[$j + 1]<w> < @!items[$j]<w>;
+            last if @!items[$k]<w> < @!items[$j]<w>;
+            (@!items[$j, $k], $k) = (|@!items[$k, $j], $j);
+         }
+         return $r<id>;
+      }
+      method enqueue ($id, $weight) { # includes "swim"
+         @!items.push: {id => $id, w => $weight};
+         my $k = @!items.end;
+         (@!items[$k/2, $k], $k) = (|@!items[$k, $k/2], ($k/2).Int)
+            while $k > 1 && @!items[$k]<w> < @!items[$k/2]<w>;
+         return self;
+      }
+   }
+}
diff --git a/challenge-152/polettix/raku/ch-2.raku b/challenge-152/polettix/raku/ch-2.raku
new file mode 100644
index 0000000000..7555fdd54f
--- /dev/null
+++ b/challenge-152/polettix/raku/ch-2.raku
@@ -0,0 +1,19 @@
+#!/usr/bin/env raku
+use v6;
+sub MAIN {
+   put rectangle-area([[-1, 0], [2, 2]], [[0, -1], [4, 4]]);
+   put rectangle-area([[-3, -1], [1, 3]], [[-1, -3], [2, 2]]);
+}
+
+sub rectangle-area ($r1, $r2) {
+   return area($r1) + area($r2) - area(intersection($r1, $r2));
+}
+
+sub area ($r) { return $r ?? [*] ($r[1] «-» $r[0]).List !! 0  }
+
+sub intersection ($r1, $r2) {
+   my $bottom-left = $r1[0] «max» $r2[0];
+   my $top-right = $r1[1] «min» $r2[1];
+   my $min-difference = ($top-right «-» $bottom-left).min;
+   return $min-difference > 0 ?? [$bottom-left, $top-right] !! Nil;
+}