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

Branch for challenge 075

2 files changed, 85 insertions, 0 deletions

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}')
+