Secret Santa algorithm

#!/usr/bin/python3 -O

import random
import collections
import codecs  # for obfuscation

OBFUSCATORS= "%$#^{}"

def obfuscate(text, max_len):
    while len(text.encode("utf8")) < max_len:
        text+= random.choice(OBFUSCATORS)
    text= random.choice(OBFUSCATORS) + random.choice(OBFUSCATORS) + text
    return codecs.encode(
        codecs.encode(
            codecs.encode(text, "rot13").encode("utf8"),
            "base64").decode("utf8"),
        "rot13")


def deobfuscate(text):
    return codecs.decode(
        codecs.decode(
            codecs.decode(text, "rot13").encode("utf8"),
            "base64").decode("utf8"),
        "rot13").rstrip(OBFUSCATORS)[2:]

class Statistics:

    def __init__(self):
        self.tags= collections.defaultdict(int)

    def tags_value(self, tags):
        return sum(1./self.tags[tag] for tag in tags)

    def account(self, tags):
        for tag in tags:
            self.tags[tag]+= 1

    def abbreviated_tags(self):
        output= {}
        abbreviations= set()
        for tag in sorted(self.tags, key=len):
            for prefixlen in range(1, len(tag)+1):
                prefix= tag[:prefixlen]
                if prefix not in abbreviations:
                    abbreviations.add(prefix)
                    output[tag]= prefix
                    break
        return output

    def most_disjoined(self, tags, groups):
        return max(
            groups.items(),
            key=lambda kv: (
                -self.tags_value(kv[0] & tags),
                len(kv[1]),
                self.tags_value(tags - kv[0]) - self.tags_value(kv[0] - tags),
            )
        )


class Person(collections.namedtuple("Person", "name tags")):
    __slots__= ()

    def name_abbr_tags(self, abbreviated_tags):
        return "%s [%s]" % (
            self.name,
            ",".join(abbreviated_tags[t] for t in self.tags),
        )


def secret_santa(people_and_their_tags, ignore_tags=()):
    """Secret santa algorithm.

    The lottery function expects a sequence of:
    (name, tags)

    For example:

    [
        ("person1", ("male", "company1")),
        ("person2", ("female", "company2")),
        ("person3", ("male", "company1")),
        ("husband1", ("male", "company2", "marriage1")),
        ("wife1", ("female", "company1", "marriage1")),
        ("husband2", ("male", "company3", "marriage2")),
        ("wife2", ("female", "company2", "marriage2")),
    ]

    husband1 is married to wife1 as seen by the common marriage1 tag
    person1, person3 and wife1 work at the same company.

    The algorithm will try to match people with the least common characteristics
    between them, to maximize entrop— ehm, mingling!

    Have fun."""

    # let's split the persons into groups

    groups= collections.defaultdict(list)
    stats= Statistics()

    for person, tags in people_and_their_tags:
        tags= frozenset(tag.lower() for tag in tags if tag not in ignore_tags)
        stats.account(tags)
        groups[tags].append(Person(person, tags))
    del tags, person

    # shuffle all lists
    for group in groups.values():
        random.shuffle(group)
    del group

    abbreviations= stats.abbreviated_tags()
    output_chain= []
    prev_tags= frozenset()
    while 1:
        next_tags, next_group= stats.most_disjoined(prev_tags, groups)
        next_person= next_group.pop()
        output_chain.append(next_person.name_abbr_tags(abbreviations))
        if not next_group: # it just got empty
            del groups[next_tags]
            if not groups: break
        prev_tags= next_tags

    return output_chain


if __name__ == "__main__":
    example_sequence= [
        ("person1", ("male", "company1")),
        ("person2", ("female", "company2")),
        ("person3", ("male", "company1")),
        ("husband1", ("male", "company2", "marriage1")),
        ("wife1", ("female", "company1", "marriage1")),
        ("husband2", ("male", "company3", "marriage2")),
        ("wife2", ("female", "company2", "marriage2")),
    ]

    print("Secret Santa assignments")
    chain= secret_santa(example_sequence)
    output_chain= []
    max_len= max(len(i.encode("utf8")) for i in chain)
    for i in reversed(range(len(chain))):
        assignee= chain[i]
        assignment= obfuscate(chain[i-1], max_len)
        output_chain.append((assignee, assignment))
    output_chain.sort()
    for assignee, assignment in output_chain:
        print("%s→%s" % (assignee, assignment.rstrip()))