Unseen Problem Example: When the Limits Allow the Brute Force

At most 12 songs to split across the two sides of a tape: 4,096 ways to split them is few enough to try every one.

Small limits are a signal too: they say the brute force may already be the whole solution. This example applies the six steps for an unseen problem to splitting a playlist of at most 12 songs across the two sides of a cassette, so that the sides run as close to equal as possible. With 12 songs there are 2¹² = 4,096 ways to assign them to the two sides, few enough to try every one.

Clarify: up to 12 songs, each a whole number of minutes; every song goes on exactly one side; the answer is the two sides. Work examples: songs of 4, 7, 3, 5 and 6 minutes total 25, so the best possible split is 12 against 13. Brute force: each song goes on side A or side B, so n songs give 2ⁿ splits, each summed in n additions. For n = 12 that is 4,096 × 12, about 5 × 10⁴ steps, set against a budget of about 10⁸ a second. The bottleneck step finds nothing worth removing, and the budget table shows why.

A rough budget at about 10⁸ simple steps a second: 12 songs sit well inside the 2ⁿ row, which holds up to n = 20
Largest n	Complexity that fits
10	O(n!)
20	O(2ⁿ)
500	O(n³)
5,000	O(n²)
10⁶	O(n log n) or O(n)
Larger	O(log n) or O(1)

The listing tries every split by counting through the whole numbers from 0 to 2ⁿ − 1, where bit i of the count says which side song i goes on, and keeps the split whose sides differ least. It runs the example and two edge cases: one song, and every song the same length.

tape_split.pypy

def best_split(songs: list[int]) -> tuple[list[int], list[int], int]:
    total = sum(songs)
    best_mask, best_gap = 0, total
    for mask in range(1 << len(songs)):
        side_a = sum(song for i, song in enumerate(songs) if mask >> i & 1)
        gap = abs(total - 2 * side_a)
        if gap < best_gap:
            best_mask, best_gap = mask, gap
    side_a = [song for i, song in enumerate(songs) if best_mask >> i & 1]
    side_b = [song for i, song in enumerate(songs) if not best_mask >> i & 1]
    return side_a, side_b, 1 << len(songs)


for songs in ([4, 7, 3, 5, 6], [9], [4, 4, 4, 4]):
    side_a, side_b, tried = best_split(songs)
    print(f"{songs}: A {side_a} = {sum(side_a)}, B {side_b} = {sum(side_b)}, {tried} splits tried")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

[4, 7, 3, 5, 6]: A [7, 5] = 12, B [4, 3, 6] = 13, 32 splits tried
[9]: A [] = 0, B [9] = 9, 2 splits tried
[4, 4, 4, 4]: A [4, 4] = 8, B [4, 4] = 8, 16 splits tried

The run tried 32 splits for five songs and found 7 + 5 = 12 against 4 + 3 + 6 = 13. One song cannot be split, so one side stays empty, and four equal songs divide evenly. Stating this brute force and its cost is the complete answer: hunting for something cleverer would spend the time and gain nothing the limits asked for. The same search on 40 songs would need about 10¹² splits, and there a faster idea would be the whole problem.

← → move through sections and cards