Merge pull request #2150 from waltman/branch-for-challenge-075

Branch for challenge 075

5 files changed, 264 insertions, 0 deletions

diff --git a/challenge-075/walt-mankowski/blog.txt b/challenge-075/walt-mankowski/blog.txt
new file mode 100644
index 0000000000..06a82fce4e
--- /dev/null
+++ b/challenge-075/walt-mankowski/blog.txt
@@ -0,0 +1 @@
+http://www.mawode.com/blog/blog/2020/08/26/perl-weekly-challenge-75/
diff --git a/challenge-075/walt-mankowski/perl/ch-1.pl b/challenge-075/walt-mankowski/perl/ch-1.pl
new file mode 100644
index 0000000000..5fda97155e
--- /dev/null
+++ b/challenge-075/walt-mankowski/perl/ch-1.pl
@@ -0,0 +1,72 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+use feature qw(:5.32);
+use experimental qw(signatures);
+
+# 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)
+
+my $s = shift @ARGV;
+my @c = @ARGV;
+my @solutions;
+
+my @cnt = map {0} 0..$#c;
+while (1) {
+    my $val = value(\@c, \@cnt);
+    if ($val >= $s) {
+        if ($val == $s) {
+            my @tmp = @cnt;
+            push @solutions, \@tmp;
+        }
+
+        # rotate "odometer"
+        $cnt[-1] = 0;
+        my $i = -2;
+        $cnt[$i]++;
+        while ($i >= -@c && value(\@c, \@cnt) > $s) {
+            $cnt[$i] = 0;
+            $i--;
+            $cnt[$i]++ if $i >= -@c;
+        }
+        last if $i < -@c;
+    } else {
+        $cnt[-1]++;
+    }
+}
+
+# print out the solutions
+say "There are " . scalar @solutions . " ways to make sum $s";
+for my $sol (@solutions) {
+    my @tmp;
+    for my $i (0..$#c) {
+        push @tmp, $c[$i] for 0..$sol->[$i]-1;
+    }
+    say "@tmp";
+}
+
+sub value($c, $cnt) {
+    my $sum = 0;
+    for my $i (0..$#$c) {
+        $sum += $c->[$i] * $cnt->[$i];
+    }
+    return $sum;
+}
diff --git a/challenge-075/walt-mankowski/perl/ch-2.pl b/challenge-075/walt-mankowski/perl/ch-2.pl
new file mode 100644
index 0000000000..6c2a680d7d
--- /dev/null
+++ b/challenge-075/walt-mankowski/perl/ch-2.pl
@@ -0,0 +1,106 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+use feature qw(:5.32);
+use experimental qw(signatures);
+use List::Util qw(max sum);
+
+# 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 larget 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
+
+my @a = @ARGV;
+
+# build the histogram
+my $rows = max(@a);
+my $cols = @a;
+my @hist;
+for my $col (0..$#a) {
+    for my $row (0..$rows-1) {
+        $hist[$row][$col] = $row < $a[$col] ? 1 : 0;
+    }
+}
+
+print_hist(\@hist, \@a, $rows, $cols);
+
+my $best_area = 0;
+my $best_height = -1;
+my $best_width = -1;
+
+for my $height (1..$rows) {
+    for my $width (1..$cols) {
+        my $area = $height * $width;
+        next if $area <= $best_area;
+        for my $r0 (0..$rows-$height) {
+            for my $c0 (0..$cols-$width) {
+                my $sum = 0;
+                for my $r ($r0..$r0+$height-1) {
+                    $sum += sum($hist[$r]->@[$c0..$c0+$width-1]);
+                }
+                if ($sum == $area) {
+                    $best_area = $area;
+                    $best_height = $height;
+                    $best_width = $width;
+                }
+            }
+        }
+    }
+}
+
+say "The best rectangle is $best_height x $best_width for an area of $best_area";
+
+sub print_hist($hist, $a, $rows, $cols) {
+    for (my $row = $rows-1; $row >= 0; $row--) {
+        printf "%d", $row+1;
+        for my $col (0..$cols-1) {
+            printf " %s", $hist[$row][$col] ? '#' : ' ';
+        }
+        print "\n";
+    }
+
+    print "-";
+    print " -" x $cols;
+    print "\n";
+
+    print " ";
+    printf " %d", $a[$_] for 0..$cols-1;
+    print "\n\n";
+}
diff --git a/challenge-075/walt-mankowski/python/ch-1.py b/challenge-075/walt-mankowski/python/ch-1.py
new file mode 100644
index 0000000000..83ed4c23f9
--- /dev/null
+++ b/challenge-075/walt-mankowski/python/ch-1.py
@@ -0,0 +1,36 @@
+from sys import argv
+from copy import deepcopy
+import numpy as np
+
+s = int(argv[1])
+c = np.array([int(x) for x in argv[2:]])
+solutions = []
+
+cnt = np.array([0 for _ in range(len(c))])
+while (True):
+    val = np.dot(c, cnt)
+    if val >= s:
+        if val == s:
+            solutions.append(deepcopy(cnt))
+
+        # rotate "odometer"
+        cnt[-1] = 0
+        i = -2
+        cnt[i] += 1
+        while i >= -len(cnt) and np.dot(c, cnt) > s:
+            cnt[i] = 0
+            i -= 1
+            if i >= -len(cnt):
+                cnt[i] += 1
+
+        if i < -len(cnt):
+            break
+    else:
+        cnt[-1] += 1
+
+print("There are", len(solutions), "ways to make sum", s)
+for sol in solutions:
+    tmp = []
+    for i in range(len(c)):
+        tmp += [c[i] for _ in range (sol[i])]
+    print(tmp)
diff --git a/challenge-075/walt-mankowski/python/ch-2.py b/challenge-075/walt-mankowski/python/ch-2.py
new file mode 100644
index 0000000000..af82ba5642
--- /dev/null
+++ b/challenge-075/walt-mankowski/python/ch-2.py
@@ -0,0 +1,49 @@
+from sys import argv
+import numpy as np
+
+def print_hist(hist, a, rows, cols):
+    for row in range(rows-1, -1, -1):
+        print(row+1, end='')
+        for col in range(cols):
+            print(f" {'#' if hist[row][col] else ' '}", end='')
+        print()
+
+    print('-', end='')
+    print(" -" * cols)
+
+    print(' ', end='')
+    for i in range(cols):
+        print(f' {a[i]}', end='')
+    print()
+    print()
+
+a = [int(x) for x in argv[1:]]
+
+# build the histogram
+rows = max(a)
+cols = len(a)
+hist = np.zeros([rows, cols], dtype=bool)
+for row in range(rows):
+    for col in range(cols):
+        if row < a[col]:
+            hist[row][col] = True
+print_hist(hist, a, rows, cols)
+
+best_area = 0
+best_height = -1
+best_width = -1
+
+for height in range(1, rows+1):
+    for width in range(1, cols+1):
+        area = height * width
+        if area <= best_area:
+            continue
+        for r0 in range(row-height+1):
+            for c0 in range(0, cols-width+1):
+                if sum(sum(hist[r0:r0+height,c0:c0+width])) == area:
+                    best_area = area
+                    best_height = height
+                    best_width = width
+
+print(f'The best rectangle is {best_height} x {best_width} for an area of {best_area}')
+