from collections import Counter
from itertools import combinations_with_replacement

def is_valid_hand(counts):
    """Recursive function to check if counts can be split into 4 melds."""
    if sum(counts.values()) == 0:
        return True, []
    
    for i in range(1, 10):
        if counts[i] >= 3:
            counts[i] -= 3
            ok, melds = is_valid_hand(counts)
            counts[i] += 3
            if ok:
                return True, [[i]*3] + melds

        if i <= 7 and counts[i] >= 1 and counts[i+1] >= 1 and counts[i+2] >= 1:
            counts[i] -= 1
            counts[i+1] -= 1
            counts[i+2] -= 1
            ok, melds = is_valid_hand(counts)
            counts[i] += 1
            counts[i+1] += 1
            counts[i+2] += 1
            if ok:
                return True, [[i, i+1, i+2]] + melds

    return False, []

def winning_splits(tiles):
    """Given 13 tiles, returns a list of (tile_added, full_split) that results in a valid hand."""
    if len(tiles) != 13:
        raise ValueError("Exactly 13 tiles must be provided")

    base_counts = Counter(int(c) for c in tiles)
    results = []

    for tile in range(1, 10):
        if base_counts[tile] >= 4:
            continue  # Cannot have more than 4 of the same tile
        counts = base_counts.copy()
        counts[tile] += 1

        for i in range(1, 10):
            if counts[i] >= 2:
                counts[i] -= 2
                valid, melds = is_valid_hand(counts)
                counts[i] += 2
                if valid:
                    pair = [i, i]
                    results.append((tile, melds + [pair]))
                    break  # Only need one valid split
    return results

tiles = "1223334455678"
for tile, split in winning_splits(tiles):
    print(f"Adding {tile} gives split: {split}")