1 files changed, 96 insertions, 0 deletions
diff --git a/len_map.py b/len_map.py
new file mode 100644
index 0000000..89642ba
--- /dev/null
+++ b/len_map.py
@@ -0,0 +1,96 @@
+#!/usr/bin/env python3
+
+# This script calculates the optimal cut distribution to reduce waste while matching the desired 2:2:4 segment count
+# It applies brute force since the problem space is very small.
+
+import numpy as np
+import itertools
+
+l_tot = 500
+
+a, b, c = 94, 124, 80
+n, m, l = 2, 2, 4
+arr = np.array([a, b, c], dtype=int)
+arr_count = np.array([n, m, l], dtype=int)
+
+# Find all possible splits of a [l_tot] m led tape into segments of lengths [a], [b] and [c] that leave a remainder
+# that's smaller than any of [a], [b] and [c].
+candidates = []
+for i in range(l_tot//a + 1):
+    l_rem_i = l_tot - i*a
+    if l_rem_i < 0:
+        continue
+
+    for j in range(l_rem_i//b + 1):
+        l_rem_j = l_rem_i - j*b
+        if l_rem_j < 0:
+            continue
+
+        k = l_rem_j // c
+        l_rem_k = l_rem_j - k*c
+
+        print(f'Candidate: ({i} {j} {k}) {i=}*{a} {j=}*{b=} {k=}*{c=} => remainder {l_rem_k}')
+        candidates.append((i, j, k))
+candidates = np.array(candidates, dtype=int)
+print()
+
+# Find all ways to combine the cuts found above to cut [num_rolls] into segments, where the amount of segments of length
+# [a], [b], and [c] that we get in total best matches the proportions we need ([n] times [a], [m] times [b], [l] times
+# [c], so 2:2:4 times for 94:124:80 cm)
+num_rolls = 3
+indices_seen = set()
+out = []
+for indices in itertools.product(candidates, repeat=num_rolls):
+    indices = np.array(indices)
+    index_tup = tuple(sorted(map(tuple, indices)))
+    if index_tup in indices_seen:
+        continue
+    indices_seen.add(index_tup)
+    rem = l_tot - (indices * arr).sum(axis=1)
+    rem_total = rem.sum()
+    count_total = indices.sum(axis=0).astype(float)
+    count_total /= arr_count
+    spread = count_total.max() - count_total.min()
+
+    if spread > 2 or (rem < 2).any():
+        continue
+    print(indices.tolist(), f'{rem_total=} {spread=}')
+    out.append((spread, rem_total, indices.tolist(), rem.tolist(), indices.sum(axis=0).tolist()))
+print()
+
+# Print out the n best matches found. Sort first by how close we match our target 2:2:4 ratio, then by how much waste
+# we leave.
+print('Best matches:')
+for spread, rem_total, indices, rem, index_sum in sorted(out, key=lambda x: (x[0], x[1]))[:25]:
+    print(indices, f'{spread=} {rem_total=} {rem=} {index_sum=}')
+
+# Here's the output for future reference. There are a number of combinations that produce 68 cm of waste split across
+# three 5m rolls of tape. We selected # 1 since it leaves leftovers of useful lengths.
+#
+# Best matches:
+# [[0, 0, 6], [0, 4, 0], [4, 0, 1]] spread=0.25 rem_total=68 rem=[20, 4, 44] index_sum=[4, 4, 7]
+# [[0, 0, 6], [1, 3, 0], [3, 1, 1]] spread=0.25 rem_total=68 rem=[20, 34, 14] index_sum=[4, 4, 7]
+# [[0, 2, 3], [0, 2, 3], [4, 0, 1]] spread=0.25 rem_total=68 rem=[12, 12, 44] index_sum=[4, 4, 7]
+# [[0, 2, 3], [1, 1, 3], [3, 1, 1]] spread=0.25 rem_total=68 rem=[12, 42, 14] index_sum=[4, 4, 7]
+# [[0, 2, 3], [2, 1, 2], [2, 1, 2]] spread=0.25 rem_total=68 rem=[12, 28, 28] index_sum=[4, 4, 7]
+# [[0, 3, 1], [1, 0, 5], [3, 1, 1]] spread=0.25 rem_total=68 rem=[48, 6, 14] index_sum=[4, 4, 7]
+# [[0, 4, 0], [1, 0, 5], [3, 0, 2]] spread=0.25 rem_total=68 rem=[4, 6, 58] index_sum=[4, 4, 7]
+# [[1, 0, 5], [1, 3, 0], [2, 1, 2]] spread=0.25 rem_total=68 rem=[6, 34, 28] index_sum=[4, 4, 7]
+# [[0, 0, 6], [0, 3, 1], [3, 1, 1]] spread=0.5 rem_total=82 rem=[20, 48, 14] index_sum=[3, 4, 8]
+# [[0, 0, 6], [0, 4, 0], [3, 0, 2]] spread=0.5 rem_total=82 rem=[20, 4, 58] index_sum=[3, 4, 8]
+# [[0, 0, 6], [1, 3, 0], [2, 1, 2]] spread=0.5 rem_total=82 rem=[20, 34, 28] index_sum=[3, 4, 8]
+# [[0, 1, 4], [0, 2, 3], [3, 1, 1]] spread=0.5 rem_total=82 rem=[56, 12, 14] index_sum=[3, 4, 8]
+# [[0, 2, 3], [0, 2, 3], [3, 0, 2]] spread=0.5 rem_total=82 rem=[12, 12, 58] index_sum=[3, 4, 8]
+# [[0, 2, 3], [1, 0, 5], [2, 2, 0]] spread=0.5 rem_total=82 rem=[12, 6, 64] index_sum=[3, 4, 8]
+# [[0, 2, 3], [1, 1, 3], [2, 1, 2]] spread=0.5 rem_total=82 rem=[12, 42, 28] index_sum=[3, 4, 8]
+# [[0, 3, 1], [1, 0, 5], [2, 1, 2]] spread=0.5 rem_total=82 rem=[48, 6, 28] index_sum=[3, 4, 8]
+# [[0, 4, 0], [1, 0, 5], [2, 0, 3]] spread=0.5 rem_total=82 rem=[4, 6, 72] index_sum=[3, 4, 8]
+# [[1, 0, 5], [1, 1, 3], [1, 3, 0]] spread=0.5 rem_total=82 rem=[6, 42, 34] index_sum=[3, 4, 8]
+# [[0, 0, 6], [0, 3, 1], [4, 0, 1]] spread=0.5 rem_total=112 rem=[20, 48, 44] index_sum=[4, 3, 8]
+# [[0, 0, 6], [1, 2, 1], [3, 1, 1]] spread=0.5 rem_total=112 rem=[20, 78, 14] index_sum=[4, 3, 8]
+# [[0, 0, 6], [1, 3, 0], [3, 0, 2]] spread=0.5 rem_total=112 rem=[20, 34, 58] index_sum=[4, 3, 8]
+# [[0, 0, 6], [2, 1, 2], [2, 2, 0]] spread=0.5 rem_total=112 rem=[20, 28, 64] index_sum=[4, 3, 8]
+# [[0, 1, 4], [0, 2, 3], [4, 0, 1]] spread=0.5 rem_total=112 rem=[56, 12, 44] index_sum=[4, 3, 8]
+# [[0, 1, 4], [1, 1, 3], [3, 1, 1]] spread=0.5 rem_total=112 rem=[56, 42, 14] index_sum=[4, 3, 8]
+# [[0, 1, 4], [2, 1, 2], [2, 1, 2]] spread=0.5 rem_total=112 rem=[56, 28, 28] index_sum=[4, 3, 8]
+