subtree(users/wpcarro): docking briefcase at '24f5a642' r/3226

git-subtree-dir: users/wpcarro
git-subtree-mainline: 464bbcb15c09813172c79820bcf526bb10cf4208
git-subtree-split: 24f5a642af3aa1627bbff977f0a101907a02c69f
Change-Id: I6105b3762b79126b3488359c95978cadb3efa789

1 files changed, 61 insertions, 0 deletions

diff --git a/users/wpcarro/scratch/facebook/cake_thief.py b/users/wpcarro/scratch/facebook/cake_thief.py
new file mode 100644
index 000000000000..90a2add06658
--- /dev/null
+++ b/users/wpcarro/scratch/facebook/cake_thief.py
@@ -0,0 +1,61 @@
+from math import floor
+
+def print_table(table):
+    print('\n-- TABLE --')
+    for row in range(len(table)):
+        x = ''
+        for col in range(len(table[row])):
+            x += ' ' + str(table[row][col])
+        print(x)
+
+def leftover(capacity, kg):
+    n = floor(capacity / kg)
+    return n, capacity - (n * kg)
+
+def init_table(num_rows, num_cols):
+    table = []
+    for _ in range(num_rows):
+        row = []
+        for _ in range(num_cols):
+            row.append(0)
+        table.append(row)
+    return table
+
+def get(table, row, col):
+    if row < 0 or col < 0:
+        return 0
+    return table[row][col]
+
+def max_haul(items, capacity):
+    table = init_table(len(items), capacity)
+
+    for row in range(len(table)):
+        for col in range(len(table[row])):
+            curr_capacity = col + 1
+            kg, val = items[row]
+            # A
+            a = get(table, row - 1, col)
+            # B
+            n, lo = leftover(curr_capacity, kg)
+            b = (val * n) + get(table, row - 1, lo - 1)
+            # commit
+            if kg > curr_capacity:
+                table[row][col] = a
+            else:
+                print(n, lo)
+                table[row][col] = max([a, b])
+            print_table(table)
+    return table[-1][-1]
+
+# There are multiple variants of this problem:
+#   1. We're allowed to take multiple of each item.
+#   2. We can only take one of each item.
+#   3. We can only take a fixed amount of each item.
+
+items = [(7,160), (3,90), (2,15)]
+capacity = 20
+result = max_haul(items, capacity)
+expected = None
+print("Result: {} == Expected: {}".format(result, expected))
+assert result == expected
+print("Success!")