import string


def reduce_names(names, keep=40):
    """Reduce the number of names in an alphabetically balanced manner.

    The reduction is made on a letter-by-letter basis with the goal to keep a
    balanced number of words with different letters on each position. Longer
    words are removed before shorter, letters between lowest and highest
    order are removed first.

    :param names: List of strings.
    :param keep: Max number of strings to keep.

    :ret: A reduced, alphabetically balanced, list of strings.
    """
    if len(names) < keep:
        return names
    elif keep < 1:
        return []

    def build_tree(names):
        """Create a Huffman tree based on names

        The tree is a dict where keys denotes a letter in the name, and the
        value is a node in the tree:
            tree :== {char: [count, tree] or {None: None} when leaf
        where count is the number of leafs in the sub tree.
        """
        def insert(letters, tree):
            if letters:
                key = letters[0]
                if key in tree:
                    # add tail to sub tree
                    value = tree[key]
                    subtree = value[1]
                    if insert(letters[1:], subtree):
                        value[0] += 1 # increase count
                        return True
                else:
                    # insert into new sub tree
                    subtree = {}
                    insert(letters[1:], subtree)
                    tree[key] = [1, subtree]
                    return True
            elif not None in tree:
                # end of word
                tree[None] = None
                return True

        # build_tree
        tree = {}
        for name in names:
            insert(name, tree)
        return tree

    def remove_one(tree):
        """Remove one leaf from the largest child node in the tree."""
        c = 0 # longest count
        chars = [] # candidate chars to remove
        keys = tree.keys()
        keys.sort()
        # search candidate chars to remove
        for key in keys:
            if tree[key]:
                count = tree[key][0]
                if count > c:
                    c = count
                    chars = [key]
                elif count == c:
                    chars.append(key)
        # remove
        char = None
        if chars:
            # look for highest-valued punctuation
            for c in reversed(chars):
                if c in string.punctuation:
                    char = c
                    break
            else:
                # remove middle char
                char = chars[len(chars) // 2]
        if char is None:
            del tree[None]
        else:
            remove_one(tree[char][1]) # subtree
            tree[char][0] -= 1
            if not tree[char][0]:
                del tree[char]

    def size_of(tree):
        """Return the number of leafs in the tree"""
        n = 0
        for value in tree.itervalues():
            if value:
                n += value[0]
        return n

    def get_names(tree, letters='', buf=None):
        """Return a list with names based on Huffman tree"""
        if buf is None:
            buf=[]
        for key, value in tree.iteritems():
            if key is None:
                buf.append(letters)
            else:
                subtree = value[1]
                get_names(subtree, letters+key, buf)
        return buf

    # reduce_names
    tree = build_tree(names)
    while size_of(tree) > keep:
        remove_one(tree)
    return get_names(tree)