Add Perl solution to challenge 075

6 files changed, 167 insertions, 0 deletions

diff --git a/challenge-075/paulo-custodio/Makefile b/challenge-075/paulo-custodio/Makefile
new file mode 100644
index 0000000000..c3c762d746
--- /dev/null
+++ b/challenge-075/paulo-custodio/Makefile
@@ -0,0 +1,2 @@
+all:
+	perl ../../challenge-001/paulo-custodio/test.pl
diff --git a/challenge-075/paulo-custodio/README b/challenge-075/paulo-custodio/README
new file mode 100644
index 0000000000..87dc0b2fbd
--- /dev/null
+++ b/challenge-075/paulo-custodio/README
@@ -0,0 +1 @@
+Solution by Paulo Custodio
diff --git a/challenge-075/paulo-custodio/perl/ch-1.pl b/challenge-075/paulo-custodio/perl/ch-1.pl
new file mode 100644
index 0000000000..390a2f3bd1
--- /dev/null
+++ b/challenge-075/paulo-custodio/perl/ch-1.pl
@@ -0,0 +1,49 @@
+#!/usr/bin/env perl
+
+# Challenge 075
+#
+# TASK #1 › Coins Sum
+# Submitted by: Mohammad S Anwar
+# You are given a set of coins @C, assuming you have infinite amount of each
+# coin in the set.
+#
+# Write a script to find how many ways you make sum $S using the coins from
+# the set @C.
+#
+# Example:
+# Input:
+#     @C = (1, 2, 4)
+#     $S = 6
+#
+# Output: 6
+# There are 6 possible ways to make sum 6.
+# a) (1, 1, 1, 1, 1, 1)
+# b) (1, 1, 1, 1, 2)
+# c) (1, 1, 2, 2)
+# d) (1, 1, 4)
+# e) (2, 2, 2)
+# f) (2, 4)
+
+use Modern::Perl;
+use List::Util qw( sum0 );
+
+my($S, @C) = @ARGV;
+
+show_coins($S, [], \@C, {});
+
+sub show_coins {
+    my($want, $have, $coins, $seen) = @_;
+    my $sum_have = sum0(@$have);
+    if ($sum_have > $want) {
+        # busted sum
+    }
+    elsif ($sum_have == $want) {
+        my $out = join(", ", sort {$a<=>$b} @$have);
+        say $out unless $seen->{$out}++;
+    }
+    else {
+        for my $coin (@$coins) {
+            show_coins($want, [@$have, $coin], $coins, $seen);
+        }
+    }
+}
diff --git a/challenge-075/paulo-custodio/perl/ch-2.pl b/challenge-075/paulo-custodio/perl/ch-2.pl
new file mode 100644
index 0000000000..4979fec29f
--- /dev/null
+++ b/challenge-075/paulo-custodio/perl/ch-2.pl
@@ -0,0 +1,94 @@
+#!/usr/bin/env perl
+
+# Challenge 075
+#
+# TASK #2 › Largest Rectangle Histogram
+# Submitted by: Mohammad S Anwar
+# You are given an array of positive numbers @A.
+#
+# Write a script to find the largest rectangle histogram created by the given
+# array.
+#
+# BONUS: Try to print the histogram as shown in the example, if possible.
+#
+# Example 1:
+#
+# Input: @A = (2, 1, 4, 5, 3, 7)
+#      7           #
+#      6           #
+#      5       #   #
+#      4     # #   #
+#      3     # # # #
+#      2 #   # # # #
+#      1 # # # # # #
+#      _ _ _ _ _ _ _
+#        2 1 4 5 3 7
+# Looking at the above histogram, the largest rectangle (4 x 3) is formed by
+# columns (4, 5, 3 and 7).
+#
+# Output: 12
+#
+# Example 2:
+#
+# Input: @A = (3, 2, 3, 5, 7, 5)
+#      7         #
+#      6         #
+#      5       # # #
+#      4       # # #
+#      3 #   # # # #
+#      2 # # # # # #
+#      1 # # # # # #
+#      _ _ _ _ _ _ _
+#        3 2 3 5 7 5
+# Looking at the above histogram, the largest rectangle (3 x 5) is formed by
+# columns (5, 7 and 5).
+#
+# Output: 15
+
+use Modern::Perl;
+use List::Util qw( max );
+
+my @A = @ARGV;
+my @hist = make_histogram(@A);
+my $max_area = max_area(@hist);
+say $max_area;
+
+
+sub make_histogram {
+    my(@a) = @_;
+    my $max = max(@a);
+    my @hist;
+    for my $c (0 .. $#a) {
+        for my $r (0 .. $max-1) {
+            $hist[$r][$c] = $r>=$a[$c] ? 0 : 1;
+        }
+    }
+    return @hist;
+}
+
+sub max_area {
+    my(@hist) = @_;
+    my $max_area = 0;
+    for my $r0 (0 .. @hist-1) {
+        for my $c0 (0 .. @{$hist[$r0]}-1) {
+            if ($hist[$r0][$c0]) {
+                for my $height (1 .. @hist-$r0) {
+                    for my $width (1 .. @{$hist[$r0]}-$c0) {
+                        my $all_ones = 1;
+                        for my $r ($r0 .. $r0+$height-1) {
+                            for my $c ($c0 .. $c0+$width-1) {
+                                if (!$hist[$r][$c]) {
+                                    $all_ones = 0;
+                                }
+                            }
+                        }
+                        if ($all_ones) {
+                            $max_area = max($max_area, $width*$height);
+                        }
+                    }
+                }
+            }
+        }
+    }
+    return $max_area;
+}
diff --git a/challenge-075/paulo-custodio/t/test-1.yaml b/challenge-075/paulo-custodio/t/test-1.yaml
new file mode 100644
index 0000000000..515e5725e9
--- /dev/null
+++ b/challenge-075/paulo-custodio/t/test-1.yaml
@@ -0,0 +1,11 @@
+- setup:
+  cleanup:
+  args:     6   1 2 4
+  input:
+  output:   |
+            |1, 1, 1, 1, 1, 1
+            |1, 1, 1, 1, 2
+            |1, 1, 2, 2
+            |1, 1, 4
+            |2, 2, 2
+            |2, 4
diff --git a/challenge-075/paulo-custodio/t/test-2.yaml b/challenge-075/paulo-custodio/t/test-2.yaml
new file mode 100644
index 0000000000..8e7d517888
--- /dev/null
+++ b/challenge-075/paulo-custodio/t/test-2.yaml
@@ -0,0 +1,10 @@
+- setup:
+  cleanup:
+  args:     2 1 4 5 3 7
+  input:
+  output:   12
+- setup:
+  cleanup:
+  args:     3 2 3 5 7 5
+  input:
+  output:   15