1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
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]
|
