#!/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]