trocador.py

from itertools import combinations
from functools import cache

NOTAS = [50, 20, 10, 5, 2]

@cache
def int_div(a, b):
    return a // b


@cache
def mod(a, b):
    return a % b


def diminishing_combinations(arr: list):
    for i in range(len(arr)):
        for c in combinations(arr, i):
            if len(c) < 1:
                continue

            yield c

    yield tuple(arr)


def contador_base(valor, notas):
    out = []
    for nt in sorted(notas, reverse=True):
        num_nt = int_div(valor, nt)
        valor = mod(valor, nt)
        [out.append(nt) for _ in range(num_nt)]

    if valor != 0:
        return

    return out


def contador(valor, notas=NOTAS):
    options = []
    prev = valor / min(notas)

    for comb in diminishing_combinations(notas):
        note_count = contador_base(valor, comb)
        if note_count and len(note_count) < prev:
            options = note_count
            prev = len(note_count)

    return options

  
  
  # Test cases
assert contador(100) == [50, 50]
assert contador(70) == [50, 20]
assert contador(10) == [10]
assert contador(55) == [50, 5]
assert contador(56) == [50, 2, 2, 2]
assert contador(51) == []