Merge pull request #2804 from nunovieira220/challenge-087

Add solution to challenge 087

4 files changed, 240 insertions, 0 deletions

diff --git a/challenge-087/nunovieira220/js/ch-1.js b/challenge-087/nunovieira220/js/ch-1.js
new file mode 100644
index 0000000000..ee330470eb
--- /dev/null
+++ b/challenge-087/nunovieira220/js/ch-1.js
@@ -0,0 +1,26 @@
+// Input
+const N = [20, 19, 9, 11, 10];
+
+// Longest Consecutive Sequence
+const nums = {};
+let end = -1;
+let counter = 1;
+
+for (const num of N.sort((a, b) => a - b)) {
+  if(nums[num - 1]) {
+    const val = nums[num - 1] + 1;
+    nums[num] = val;
+
+    if (val >= counter) {
+      counter = val;
+      end = num;
+    }
+  } else {
+    nums[num] = 1;
+    if(counter === 1) end = num;
+  }
+}
+
+// Output
+const start = end - counter;
+console.log(Array.from({ length: counter }, (v, k) => start + k + 1));
\ No newline at end of file
diff --git a/challenge-087/nunovieira220/js/ch-2.js b/challenge-087/nunovieira220/js/ch-2.js
new file mode 100644
index 0000000000..79a95c013c
--- /dev/null
+++ b/challenge-087/nunovieira220/js/ch-2.js
@@ -0,0 +1,88 @@
+// Input
+const N = [
+  [0, 0, 0, 1, 1, 1],
+  [1, 1, 1, 1, 1, 1],
+  [0, 0, 1, 0, 0, 1],
+  [0, 0, 1, 1, 1, 1],
+  [0, 0, 1, 1, 1, 1],
+];
+
+// Largest Rectangle
+const R = [];
+let points = [];
+let totalArea = 0;
+
+for (let x = 0; x < N.length; x++) {
+  if(R[x] === undefined) R[x] = [];
+
+  for (let y = 0; y < N[0].length; y++) {
+    if(N[x][y] === 1) {
+      let left = 1, up = 1;
+      let leftArea = 1, upArea = 1, maxArea = 1;
+      let leftPoint = [], upPoint = [], maxPoint = [];
+
+      // Count left and up values
+      if(y > 0) left = R[x][y-1][0] + 1;
+      if(x > 0) up = R[x-1][y][1] + 1;
+
+      // Get maximum area on the left side
+      if(y > 0) {
+        let limitUp = up;
+        let leftArea = up;
+        leftPoint = [x - limitUp + 1, y];
+
+        for(let d = 1; d < left; d++) {
+          limitUp = Math.min(limitUp, R[x][y-d][1]);
+          const area = (d + 1) * limitUp;
+
+          if(area > leftArea) {
+            leftArea = area;
+            leftPoint = [x - limitUp + 1, y - d];
+          }
+        }
+      }
+
+      // Get maximum area on the upper side
+      if(x > 0) {
+        let limitLeft = left;
+        upArea = left;
+        upPoint = [x, y - limitLeft + 1];
+
+        for(let d = 1; d < up; d++) {
+          limitLeft = Math.min(limitLeft, R[x-d][y][0]);
+          const area = (d + 1) * limitLeft;
+
+          if(area > upArea) {
+            upArea = area;
+            upPoint = [x - d, y - limitLeft + 1];
+          }
+        }
+      }
+
+      // Get maximum area until now
+      if(leftArea > upArea) {
+        maxPoint = leftPoint;
+        maxArea = leftArea;
+      } else {
+        maxPoint = upPoint;
+        maxArea = upArea;
+      }
+
+      if(maxArea > totalArea) {
+        points = [maxPoint[0], maxPoint[1], x, y];
+        totalArea = maxArea;
+      }
+
+      R[x][y] = [left, up];
+    } else {
+      R[x][y] = [0, 0];
+    }
+  }
+}
+
+// Output
+if(totalArea <= 1) {
+  console.log('No rectangule was found on the matrix.');
+} else {
+  console.log(`Result rectangule is located between (${points[0]}, ${points[1]}) and (${points[2]}, ${points[3]}) with total area of ${totalArea}.`);
+}
\ No newline at end of file
diff --git a/challenge-087/nunovieira220/perl/ch-1.pl b/challenge-087/nunovieira220/perl/ch-1.pl
new file mode 100644
index 0000000000..23d1a64951
--- /dev/null
+++ b/challenge-087/nunovieira220/perl/ch-1.pl
@@ -0,0 +1,31 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+use feature qw(say);
+
+# Input
+my @N = (20, 19, 9, 11, 10);
+
+# Longest Consecutive Sequence
+my %nums = ();
+my $res = -1;
+my $counter = 1;
+
+for (sort {$a <=> $b} @N) {
+  if(defined $nums{$_ - 1}) {
+    my $val = $nums{$_ - 1} + 1;
+    $nums{$_} = $val;
+
+    if ($val >= $counter) {
+      $counter = $val;
+      $res = $_;
+    }
+  } else {
+    $nums{$_} = 1;
+    $res = $_ if($counter == 1);
+  }
+}
+
+# Output
+say join(',', $res - $counter + 1..$res);
\ No newline at end of file
diff --git a/challenge-087/nunovieira220/perl/ch-2.pl b/challenge-087/nunovieira220/perl/ch-2.pl
new file mode 100644
index 0000000000..19cae5f6ee
--- /dev/null
+++ b/challenge-087/nunovieira220/perl/ch-2.pl
@@ -0,0 +1,95 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+use feature qw(say);
+use List::Util qw[min];
+use Data::Dumper::OneLine;
+
+# Input
+my @N = (
+  [0, 0, 0, 1, 1, 1],
+  [1, 1, 1, 1, 1, 1],
+  [0, 0, 1, 0, 0, 1],
+  [0, 0, 1, 1, 1, 1],
+  [0, 0, 1, 1, 1, 1],
+);
+
+# Largest Rectangle
+my @R = ();
+my @points = ();
+my $totalArea = 0;
+
+for (my $x = 0; $x < scalar @N; $x++) {
+  for (my $y = 0; $y < scalar @{$N[0]}; $y++) {
+    if($N[$x][$y] == 1) {
+      my $left = 1, my $up = 1;
+      my $leftArea = 1, my $upArea = 1, my $maxArea = 1;
+      my $leftPoint, my $upPoint, my $maxPoint;
+
+      # Count left and up values
+      $left = @{$R[$x][$y-1]}[0] + 1 if($y > 0);
+      $up = @{$R[$x-1][$y]}[1] + 1 if($x > 0);
+
+      # Get maximum area on the left side
+      if($y > 0) {
+        my $limitUp = $up;
+        $leftArea = $up;
+        $leftPoint = [$x - $limitUp + 1, $y];
+
+        for(my $d = 1; $d < $left; $d++) {
+          $limitUp = min($limitUp, @{$R[$x][$y-$d]}[1]);
+          my $area = ($d + 1) * $limitUp;
+
+          if($area > $leftArea) {
+            $leftArea = $area;
+            $leftPoint = [$x - $limitUp + 1, $y - $d];
+          }
+        }
+      }
+
+      # Get maximum area on the upper side
+      if($x > 0) {
+        my $limitLeft = $left;
+        $upArea = $left;
+        $upPoint = [$x, $y - $limitLeft + 1];
+
+        for(my $d = 1; $d < $up; $d++) {
+          $limitLeft = min($limitLeft, @{$R[$x-$d][$y]}[0]);
+          my $area = ($d + 1) * $limitLeft;
+
+          if($area > $upArea) {
+            $upArea = $area;
+            $upPoint = [$x - $d, $y - $limitLeft + 1];
+          }
+        }
+      }
+
+      # Get maximum area until now
+      if($leftArea > $upArea) {
+        $maxPoint = $leftPoint;
+        $maxArea = $leftArea;
+      } else {
+        $maxPoint = $upPoint;
+        $maxArea = $upArea;
+      }
+
+      if($maxArea > $totalArea) {
+        @points = (@$maxPoint[0], @$maxPoint[1], $x, $y);
+        $totalArea = $maxArea;
+      }
+
+      $R[$x][$y] = [$left, $up];
+    } else {
+      $R[$x][$y] = [0, 0];
+    }
+  }
+}
+
+# Output
+if($totalArea <= 1) {
+  say "No rectangule was found on the matrix.";
+} else {
+  say "Result rectangule is located between (".$points[0].", ".$points[1].") and (".$points[2].", ".$points[3].") ".
+    "with total area of ".$totalArea.".";
+}
\ No newline at end of file