#!/usr/bin/python

#############
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
# 
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
# 
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.
#############

#############
# Christmas Gift Exchange Name Matcher
# Copyright (c)2010, Adam Monsen <haircut@gmail.com>
#
# Rules:
# 1. give to a different person than last year
# 2. partners can't be nuclear family members
# 3. can't choose yourself
# 4. participants give one gift only
# 5. participants receive one gift only
#############

participants = [ 'Jim', 'Suzy', 'D.J.', 'Grandma', 'Grandpa', 'Amika', 'Ruby', 'Jose']

last_years_pairs = [
    ('Jim', 'Amika'),
    ('Amika', 'D.J.'),
    ('Ruby', 'Jim'),
    ('Grandma', 'Suzy'),
    ('D.J.', 'Grandpa'),
    ('Grandpa', 'Ruby'),
    ('Jose', 'Grandma'),
    ('Suzy', 'Jose'),
]

families = [
    ('Grandma', 'Grandpa'),
    ('Suzy', 'Jim', 'D.J.'),
    ('Ruby', 'Jose'),
]

import random
import sys

debug_on = False
debug_fine_on = False

from copy import copy

def debug(msg):
    if debug_on: print msg

def debug_fine(msg):
    if debug_fine_on: print msg

def possible_givers(participants, chosen):
    # rule 4 - participants give one gift only
    possible_givers = copy(participants)
    for giver in map(lambda x: x[0], chosen):
        possible_givers.remove(giver)
    return possible_givers

def possible_recipients(giver, participants, chosen, last_years_pairs, families):
    """Exclude all rule-breaking recipients and return whatever's left, if
    anything."""

    possible_recipients = copy(participants)

    # rule 3 - can't choose yourself
    possible_recipients.remove(giver)

    # rule 1 - different pairing than last year
    for tmp_giver, recipient in last_years_pairs:
        if tmp_giver == giver and (giver, recipient) in last_years_pairs \
                and recipient in possible_recipients:
            debug_fine("%s gave to %s last year, excluding" % (giver, recipient))
            possible_recipients.remove(recipient)

    # rule 2 - give outside nuclear family
    for family in families:
        if giver in family:
            for recipient in family:
                if recipient in possible_recipients:
                    debug_fine("%s and %s are family, excluding" % (giver, recipient))
                    possible_recipients.remove(recipient)

    # rule 5 - participants receive one gift only
    for pair in chosen:
        if pair[1] in possible_recipients:
            debug_fine("%s is already paired, excluding" % pair[1])
            possible_recipients.remove(pair[1])

    return possible_recipients

if __name__ == '__main__':
    chosen = []

    while len(chosen) != len(participants):
        givers = possible_givers(participants, chosen)
        # if we omit randomization here, our "abort/retry" (below) may fail,
        # although I'm not really sure why
        giver = random.choice(givers)
        debug_fine("GIVER: %s" % giver)
        recipients = possible_recipients(giver, participants, \
                chosen, last_years_pairs, families)
        # brute force abort/retry
        if len(recipients) == 0:
            debug("No recipients, trying a different giver...")
            if len(givers) <= 1:
                debug("No other givers to try! Starting over...")
                chosen = []
            if len(givers) == 2:
                debug("Stalemate! Two givers left but they can't give to eachother. Starting over...")
                chosen = []
            continue
        recipient = random.choice(recipients)
        debug_fine("RECIPIENT: %s" % recipient)
        chosen.append( (giver, recipient) )
        debug("PAIRS ARE NOW: %s" % chosen)

    chosen.sort()
    for giver, recipient in chosen:
        print "%s gives to %s" % (giver, recipient)