From e437aee28cebedf938b935550694a5c0ca3ac01c Mon Sep 17 00:00:00 2001
From: Walt Mankowski <waltman@pobox.com>
Date: Tue, 25 Aug 2020 15:56:17 -0400
Subject: perl solution for challenge 75 task 1

first draft
---
 challenge-075/walt-mankowski/perl/ch-1.pl | 73 +++++++++++++++++++++++++++++++
 1 file changed, 73 insertions(+)
 create mode 100644 challenge-075/walt-mankowski/perl/ch-1.pl

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..556d2fd271
--- /dev/null
+++ b/challenge-075/walt-mankowski/perl/ch-1.pl
@@ -0,0 +1,73 @@
+#!/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;
+my $i = $#c;
+while (1) {
+    my $val = value(\@c, \@cnt);
+    if ($val >= $s) {
+        if ($val == $s) {
+            my @tmp = @cnt;
+            push @solutions, \@tmp;
+        }
+
+        # rotate "odometer"
+        $cnt[$#c] = 0;
+        my $j = $#c - 1;
+        $cnt[$j]++;
+        while ($j >= 0 && value(\@c, \@cnt) > $s) {
+            $cnt[$j] = 0;
+            $j--;
+            $cnt[$j]++;
+        }
+        last if $j < 0;
+    } else {
+        $cnt[$#c]++;
+    }
+}
+
+# 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;
+}
-- 
cgit 


From 60c1d8be5c9fac63612791b5370fb50d93d4cb2c Mon Sep 17 00:00:00 2001
From: Walt Mankowski <waltman@pobox.com>
Date: Tue, 25 Aug 2020 22:00:23 -0400
Subject: perl solution for challenge 75 task 2

first draft
---
 challenge-075/walt-mankowski/perl/ch-2.pl | 107 ++++++++++++++++++++++++++++++
 1 file changed, 107 insertions(+)
 create mode 100644 challenge-075/walt-mankowski/perl/ch-2.pl

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..a64a8aa018
--- /dev/null
+++ b/challenge-075/walt-mankowski/perl/ch-2.pl
@@ -0,0 +1,107 @@
+#!/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 " -" for 0..$cols-1;
+    print "\n";
+
+    print " ";
+    printf " %d", $a[$_] for 0..$cols-1;
+    print "\n\n";
+}
+
-- 
cgit 


From 196b6c270e7f0bbe188c40093451fca3dd52c57e Mon Sep 17 00:00:00 2001
From: Walt Mankowski <waltman@pobox.com>
Date: Wed, 26 Aug 2020 09:15:54 -0400
Subject: python solution for challenge 75 task 1

first draft
---
 challenge-075/walt-mankowski/python/ch-1.py | 36 +++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)
 create mode 100644 challenge-075/walt-mankowski/python/ch-1.py

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..b070bcb102
--- /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
+        j = -2
+        cnt[j] += 1
+        while j >= -len(cnt) and np.dot(c, cnt) > s:
+            cnt[j] = 0
+            j -= 1
+            if j >= -len(cnt):
+                cnt[j] += 1
+
+        if j < -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)
-- 
cgit 


From 730915136413554ad43fbfc9d7e4f766291a4ec0 Mon Sep 17 00:00:00 2001
From: Walt Mankowski <waltman@pobox.com>
Date: Wed, 26 Aug 2020 14:35:58 -0400
Subject: python solution for challenge 75 task 2

first draft
---
 challenge-075/walt-mankowski/python/ch-2.py | 49 +++++++++++++++++++++++++++++
 1 file changed, 49 insertions(+)
 create mode 100644 challenge-075/walt-mankowski/python/ch-2.py

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..efd720f539
--- /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] == 1 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])
+for row in range(rows):
+    for col in range(cols):
+        if row < a[col]:
+            hist[row][col] = 1
+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 aea of {best_area}.')
+
-- 
cgit 


From 59f42083ee3c1c04bf9db831430d5b9d94c446a2 Mon Sep 17 00:00:00 2001
From: Walt Mankowski <waltman@pobox.com>
Date: Wed, 26 Aug 2020 14:45:02 -0400
Subject: use dtype of bool for the histogram

---
 challenge-075/walt-mankowski/python/ch-2.py | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/challenge-075/walt-mankowski/python/ch-2.py b/challenge-075/walt-mankowski/python/ch-2.py
index efd720f539..fb8d13b9c3 100644
--- a/challenge-075/walt-mankowski/python/ch-2.py
+++ b/challenge-075/walt-mankowski/python/ch-2.py
@@ -5,7 +5,7 @@ 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] == 1 else ' '}", end='')
+            print(f" {'#' if hist[row][col] else ' '}", end='')
         print()
 
     print('-', end='')
@@ -22,11 +22,11 @@ a = [int(x) for x in argv[1:]]
 # build the histogram
 rows = max(a)
 cols = len(a)
-hist = np.zeros([rows, cols])
+hist = np.zeros([rows, cols], dtype=bool)
 for row in range(rows):
     for col in range(cols):
         if row < a[col]:
-            hist[row][col] = 1
+            hist[row][col] = True
 print_hist(hist, a, rows, cols)
 
 best_area = 0
-- 
cgit 


From f09ff0b5b57f38aa13376ffd3cd5d642c8d75a3b Mon Sep 17 00:00:00 2001
From: Walt Mankowski <waltman@pobox.com>
Date: Wed, 26 Aug 2020 20:52:46 -0400
Subject: changed to use negative array indexing

I did this in the Python version and it made the code a bit easier to follow
---
 challenge-075/walt-mankowski/perl/ch-1.pl | 13 ++++++-------
 1 file changed, 6 insertions(+), 7 deletions(-)

diff --git a/challenge-075/walt-mankowski/perl/ch-1.pl b/challenge-075/walt-mankowski/perl/ch-1.pl
index 556d2fd271..032d6d598b 100644
--- a/challenge-075/walt-mankowski/perl/ch-1.pl
+++ b/challenge-075/walt-mankowski/perl/ch-1.pl
@@ -30,7 +30,6 @@ my @c = @ARGV;
 my @solutions;
 
 my @cnt = map {0} 0..$#c;
-my $i = $#c;
 while (1) {
     my $val = value(\@c, \@cnt);
     if ($val >= $s) {
@@ -40,17 +39,17 @@ while (1) {
         }
 
         # rotate "odometer"
-        $cnt[$#c] = 0;
-        my $j = $#c - 1;
+        $cnt[-1] = 0;
+        my $j = -2;
         $cnt[$j]++;
-        while ($j >= 0 && value(\@c, \@cnt) > $s) {
+        while ($j >= -@c && value(\@c, \@cnt) > $s) {
             $cnt[$j] = 0;
             $j--;
-            $cnt[$j]++;
+            $cnt[$j]++ if $j >= -@c;
         }
-        last if $j < 0;
+        last if $j < -@c;
     } else {
-        $cnt[$#c]++;
+        $cnt[-1]++;
     }
 }
 
-- 
cgit 


From 000fc96aced80bc918100ff92372400197e619da Mon Sep 17 00:00:00 2001
From: Walt Mankowski <waltman@pobox.com>
Date: Wed, 26 Aug 2020 20:54:30 -0400
Subject: changed j to i

This is because I thought I needed 2 loop variables but only ended up
needing the inner one.
---
 challenge-075/walt-mankowski/perl/ch-1.pl   | 14 +++++++-------
 challenge-075/walt-mankowski/python/ch-1.py | 16 ++++++++--------
 2 files changed, 15 insertions(+), 15 deletions(-)

diff --git a/challenge-075/walt-mankowski/perl/ch-1.pl b/challenge-075/walt-mankowski/perl/ch-1.pl
index 032d6d598b..5fda97155e 100644
--- a/challenge-075/walt-mankowski/perl/ch-1.pl
+++ b/challenge-075/walt-mankowski/perl/ch-1.pl
@@ -40,14 +40,14 @@ while (1) {
 
         # rotate "odometer"
         $cnt[-1] = 0;
-        my $j = -2;
-        $cnt[$j]++;
-        while ($j >= -@c && value(\@c, \@cnt) > $s) {
-            $cnt[$j] = 0;
-            $j--;
-            $cnt[$j]++ if $j >= -@c;
+        my $i = -2;
+        $cnt[$i]++;
+        while ($i >= -@c && value(\@c, \@cnt) > $s) {
+            $cnt[$i] = 0;
+            $i--;
+            $cnt[$i]++ if $i >= -@c;
         }
-        last if $j < -@c;
+        last if $i < -@c;
     } else {
         $cnt[-1]++;
     }
diff --git a/challenge-075/walt-mankowski/python/ch-1.py b/challenge-075/walt-mankowski/python/ch-1.py
index b070bcb102..83ed4c23f9 100644
--- a/challenge-075/walt-mankowski/python/ch-1.py
+++ b/challenge-075/walt-mankowski/python/ch-1.py
@@ -15,15 +15,15 @@ while (True):
 
         # rotate "odometer"
         cnt[-1] = 0
-        j = -2
-        cnt[j] += 1
-        while j >= -len(cnt) and np.dot(c, cnt) > s:
-            cnt[j] = 0
-            j -= 1
-            if j >= -len(cnt):
-                cnt[j] += 1
+        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 j < -len(cnt):
+        if i < -len(cnt):
             break
     else:
         cnt[-1] += 1
-- 
cgit 


From 4c7aa6d402ab4dbf985cbf9e2271ee9d7a2df6f5 Mon Sep 17 00:00:00 2001
From: Walt Mankowski <waltman@pobox.com>
Date: Wed, 26 Aug 2020 20:58:43 -0400
Subject: fixed typo and got output to match the perl version

---
 challenge-075/walt-mankowski/python/ch-2.py | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/challenge-075/walt-mankowski/python/ch-2.py b/challenge-075/walt-mankowski/python/ch-2.py
index fb8d13b9c3..af82ba5642 100644
--- a/challenge-075/walt-mankowski/python/ch-2.py
+++ b/challenge-075/walt-mankowski/python/ch-2.py
@@ -45,5 +45,5 @@ for height in range(1, rows+1):
                     best_height = height
                     best_width = width
 
-print(f'The best rectangle is {best_height} x {best_width} for an aea of {best_area}.')
+print(f'The best rectangle is {best_height} x {best_width} for an area of {best_area}')
 
-- 
cgit 


From ba2e1996a82b6d186ae66497600950881c72471f Mon Sep 17 00:00:00 2001
From: Walt Mankowski <waltman@pobox.com>
Date: Wed, 26 Aug 2020 22:25:26 -0400
Subject: removed a loop from print_hist()

---
 challenge-075/walt-mankowski/perl/ch-2.pl | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/challenge-075/walt-mankowski/perl/ch-2.pl b/challenge-075/walt-mankowski/perl/ch-2.pl
index a64a8aa018..a201d51bd6 100644
--- a/challenge-075/walt-mankowski/perl/ch-2.pl
+++ b/challenge-075/walt-mankowski/perl/ch-2.pl
@@ -97,7 +97,7 @@ sub print_hist($hist, $a, $rows, $cols) {
     }
 
     print "-";
-    print " -" for 0..$cols-1;
+    print " -" x $cols;
     print "\n";
 
     print " ";
-- 
cgit 


From 1ab5919fb2e0bfd425995e20233442578b114640 Mon Sep 17 00:00:00 2001
From: Walt Mankowski <waltman@pobox.com>
Date: Wed, 26 Aug 2020 22:25:54 -0400
Subject: removed trailing newline

---
 challenge-075/walt-mankowski/perl/ch-2.pl | 1 -
 1 file changed, 1 deletion(-)

diff --git a/challenge-075/walt-mankowski/perl/ch-2.pl b/challenge-075/walt-mankowski/perl/ch-2.pl
index a201d51bd6..6c2a680d7d 100644
--- a/challenge-075/walt-mankowski/perl/ch-2.pl
+++ b/challenge-075/walt-mankowski/perl/ch-2.pl
@@ -104,4 +104,3 @@ sub print_hist($hist, $a, $rows, $cols) {
     printf " %d", $a[$_] for 0..$cols-1;
     print "\n\n";
 }
-
-- 
cgit 


From 712f3a4f659daf2cf65c5e803d27a12552aae0fe Mon Sep 17 00:00:00 2001
From: Walt Mankowski <waltman@pobox.com>
Date: Wed, 26 Aug 2020 22:44:06 -0400
Subject: blog post link for challenge 75

---
 challenge-075/walt-mankowski/blog.txt | 1 +
 1 file changed, 1 insertion(+)
 create mode 100644 challenge-075/walt-mankowski/blog.txt

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/
-- 
cgit