from functools import cache
from collections import Counter, defaultdict

# pool = Counter(map(int, "000226688"))
# counted_digits = (0, 2, 6, 8)
# counts = (3, 2, 2, 2)

# 268

# 208
#  60
#   0


@cache
def choose_n_unique(counts, n):
    if sum(counts) < n:
        raise "you done fucked up"
    if sum(counts) == n:
        return set([counts])
    out = set([])
    for i, count in enumerate(counts):
        if count <= 0:
            continue
        out.update(
            choose_n_unique(counts[:i] + (count - 1,) + counts[i + 1 :], n)
        )
    return out


def sub(a, b):  # a-b
    return tuple(x - y for x, y in zip(a, b))


# print(choose_n_unique(counts, 3))
# print(find_sums(counts))
# print(possible_sums((3, 2, 2, 2)))


def has_len_digit(tup, length):
    for t in tup:
        if len(str(t)) == length:
            return True
    return False


# tup_0, tup_1 = (826,), (0, 0, 6, 820)

# print(has_len_digit(tup_0, 2))
# print(has_len_digit(tup_1, 2))
# exit()


def find_solutions(counted_digits, counts):

    @cache
    def possible_sums(counts):  # sum -> set(tuple(addend))
        if sum(counts) == 0:
            return {0: set()}
        if sum(counts) == 1:
            for i, count in enumerate(counts):
                if count == 0:
                    continue
                digit = counted_digits[i]
            out = {digit: set([(digit,)])}
            return out

        out = defaultdict(set)

        for i, count in enumerate(counts):
            if count <= 0:
                continue
            digit = counted_digits[i]
            sub = possible_sums(counts[:i] + (count - 1,) + counts[i + 1 :])
            for s, tups in sub.items():
                for tup in tups:
                    out[s + digit].add(tuple(sorted((digit,) + tup)))
            # try appending the digit to all sub subms
            for tups in sub.values():
                for tup in tups:
                    for j, val in enumerate(tup):
                        if j > 0 and val == tup[j - 1]:
                            continue
                        new_tup = tuple(
                            sorted((val * 10 + digit,) + tup[:j] + tup[j + 1 :])
                        )
                        out[sum(new_tup)].add(new_tup)
        return out

    out = []
    for counts_0 in choose_n_unique(counts, 3):
        counts_1 = sub(counts, counts_0)
        # print(counts_1)
        possible_0 = possible_sums(counts_0)
        possible_1 = possible_sums(counts_1)
        # print(possible_0.get(268, "nope"))
        # print(possible_1.get(268, "nope"))
        # print()
        for total in possible_0.keys() & possible_1.keys():
            tups_0 = possible_0[total]
            tups_1 = possible_1[total]
            for tup_0 in tups_0:
                for tup_1 in tups_1:
                    if not (has_len_digit(tup_0, 1) or has_len_digit(tup_1, 1)):
                        continue
                    if not (has_len_digit(tup_0, 2) or has_len_digit(tup_1, 2)):
                        continue
                    if not (has_len_digit(tup_0, 3) or has_len_digit(tup_1, 3)):
                        continue
                    out.append((tup_0, tup_1))
    return out


# print(find_solutions(counted_digits=(0, 2, 6, 8), counts=(3, 2, 2, 2)))
import random

rng = random.Random(4)
# best = 100
# for i in range(1000):

#     # rng.randint()
#     def r(radius):
#         return rng.randint(-radius, radius)

#     candidate = find_solutions(
#         counted_digits=(1 + r(1), 2 + r(1), 6 + r(1), 8 + r(1)),
#         counts=(3 + r(1), 2 + r(1), 2 + r(1), 2 + r(1)),
#     )
#     if not candidate:
#         continue

#     if len(candidate) <= best:
#         best = len(candidate)
#         print("yay")
#         for tup in candidate:
#             print("   ", tup)


def counted_digits_and_counts_from_solution(solution):
    s = str(solution)
    for to_remove in "(), ":
        s = s.replace(to_remove, "")
    print(s)
    print("".join(sorted(s)))
    c = Counter(s)
    counted_digits = tuple(int(k) for k in sorted(c))
    counts = tuple(int(c[k]) for k in sorted(c))
    return counted_digits, counts


print(counted_digits_and_counts_from_solution("((261,), (7, 27, 227)))"))
print(find_solutions((1, 2, 6, 7), (1, 4, 1, 3)))