From: Jim Weirich <jim@...>
Date: 2004-10-05T09:31:17+09:00
Subject: Re: [SOLUTION] Secret Santas (#2)

--------------010504010903070701040200
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

James Edward Gray II wrote:
> One person told me this problem is just "toy code".  While a Secret 
> Santa draw may not appeal to everyone, I assure you there are 
> interesting issues involved with the solution.  It's a fun "toy" to play 
> with, if nothing else.  ;)

Perhaps it does not count as enterprise level computing, but it is 
certainly not toy code.  At least not in our family.  My family has been 
using computer generated Christmas gift lists for at least 11 years (and 
probably longer ... October 1993 is the earliest date given in the code 
comments).

I haven't had time to partake in the Ruby Quiz yet.  But just for fun, 
I'm attaching my C version that my family has been using for years.  It 
solves essentially the same problem, although the input format is a bit 
different.  It also supports additional constraints such as MustByFor 
(added the year Aunt Helen said she found the perfect gift for cousin 
Josiah and could I "arrange" the list so that she could give his gift) 
and MustNotBuyFor (added when Aunt Mary said if she got Uncle John (a 
particularly difficult person to buy for) one more year in a row, she 
would have my head).  Oh, and I swear that the year Uncle Pat got the 
exploding gift from me, it wasn't pre-arranged.  Honestly!

My version doesn't support email addresses either, for when it was first 
written, I was probably the only person in family who knew what email 
was.  Today, I think even Grandma has an email account.  That would be a 
great way to distribute the lists.

Oh, and if you actually use a computerized Christmas list, make sure you 
archive the results.  You see, Uncle Dan can never remember whose name 
has been assigned to him. :-)

-- 
-- Jim Weirich    jim@weirichhouse.org     http://onestepback.org
-----------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct,
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)

--------------010504010903070701040200
Content-Type: text/x-csrc;
 name="xmaslist.c"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="xmaslist.c"

#define VERSION "2.01"
/*
 * XMasList -- Create a Christmas List
 *
 * History:
 *  2.00 05/Oct/93 JNWeirich -- Added Must buy list
 *  2.01 21/Dec/98 JNWeirich -- Fixed bug where the buysFor lists was
 *                  not reset when a the GenerateBuysFor was rerun.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>

#define strcmpi strcasecmp


/* module level variables */

#define TRUE	        1
#define FALSE		0

FILE *	inFile;	            /* name input file */
int verbose = FALSE;	    /* TRUE if extra printout desired */
int shorter = FALSE;	    /* TRUE if short output desired */
int debugging = FALSE;      /* TRUE if debugging output desired */

#define MAX_PERSON      50  /* maximum number of people allowed */
int nPeople = 0;	    /* number of people in data base */
char * person[MAX_PERSON];  /* names of the people */
int family[MAX_PERSON];	    /* family index */
int buysFor[MAX_PERSON];    /* index of who you buy for */

unsigned char avoid[MAX_PERSON][MAX_PERSON];
                /* matrix of unallowed combinations */
		/* i.e. if (avoid[i][j]) then P[i] cant buy for P[j] */

int nMust = 0;  /* number of entries in mustBuy */
unsigned char mustBuy[MAX_PERSON][2];
                /* matrix of must buy associations */
                /* i.e. mustBuy[i][0] must buy for mustBuy[i][1] */


unsigned int randomSeed = 0;	/* random seed used to randomize the lists */
                
/* Usage -- Display Usage */

void Usage (void)
{
    printf ("XmasList Version %s\n", VERSION);
    printf ("Usage: xmaslist <people >buylist [-h][-s][-v]\n");
}


/* Random -- Return a random number between zero and n */

int Random (int max)
{
    int n = (int) (max * (rand() / (float)RAND_MAX));
    return n;
}


/* Randomize -- Randomize the random number generator */

void Randomize ()
{
    srand (randomSeed);
}

/* StrSave -- Save a String to Dynamic Memory */

char * StrSave (char * str)
{
    char *s;

    s = malloc (strlen(str)+1);
    if (!s) {
        fprintf (stderr, "Out of Memory\n");
        exit (1);
    }
    strcpy (s, str);

    return s;
}




/*
 * GetToken -- Get the Next Token from the Input File
 *
 * A token is delimited by a comma or end of line, or one of
 * the following special characters:  ":", "%", and "=".
 * A "#" begins a comment that continues to the end of the line.
 * The name type is returned: 'A' for names, the special character
 * or EOF for end of file.
 */

int GetToken (           /* RETURN Name Type */
    char *  buf)	/* IN buffer to get new name */
{
    int ch, i;
    int tok;

/* skip white space */

    buf[0] = 0;
    do {
        ch = getc(inFile);
        if (ch == '#') {
            while (ch != '\n' && ch != EOF)
                ch = getc(inFile);
        }
    } while (isspace(ch));

    if (ch == EOF)
        return EOF;

    switch (ch) {
    case ';':
    case '=':
    case '%':
    case ',':
        tok = ch;
        buf[0] = ch;
        buf[1] = 0;
        break;

    default:
        if (isalpha(ch)) {
            tok = 'A';
            i = 0;
            while (isalnum(ch) || isspace(ch) || ch=='.') {
                buf[i++] = ch;
                ch = getc(inFile);
            }
            ungetc (ch, inFile);
            while (i>0 && isspace(buf[i-1]))
        	i--;
            buf[i] = '\0';
	}
        else {
	    tok = '?';
	    strcpy (buf, "?");
	}
	break;
    }

    if (debugging)
        fprintf (stderr, "GT: %c [%s]\n", tok, buf);
 
    return tok;
}


/* LookupName -- Find the Index of a Name (-1 if not found) */

int LookupName (        /* OUT index of name (-1 if not found) */
    char *  name)	/* IN name to lookup */
{
    int i;

    for (i=0; i<nPeople; i++) {
        if (strcmpi (name, person[i]) == 0)
            return i;
    }
    return -1;
}


/* ReadPerson -- Read a Person Name (-1 if not a person) */

int ReadPerson (void)
{
    int tok;
    int p;
    static char buf[80];
    
    while ((tok = GetToken (buf))== ',') {
    }

    if (tok != 'A') {
        if (debugging)
            fprintf (stderr, "ReadPerson: %c [%s]\n", tok, buf);
        return -1;
    }
    p = LookupName (buf);
    if (debugging)
        fprintf (stderr, "ReadPerson: %c [%s] %d\n", tok, buf, p);

    return p;
}


/* AddBuyer -- Add a buyer to the buysFor list */

void AddBuyer (int iBuyer, int iReceiver, int who[])
{
    buysFor[iBuyer] = iReceiver;
    who[iReceiver] = -1;
    if (debugging) {
	printf ("%d buys for %d\n", iBuyer, iReceiver);
    }
}

/* GenerateBuyList -- Generate the Buys For List */

int GenerateBuyList (void)
{
    int i, j, nLeft, randIndex;
    int who[MAX_PERSON];
    static int count = 0;

    for (i=0; i<MAX_PERSON; i++)
        buysFor[i] = -1;

    if (debugging) {
	printf ("Generating Buy List -- Attempt #%d\n", ++count);
    }

    /* initialize who array with people left to buy for */

    for (i=0; i<nPeople; i++)
        who[i] = i;     

    /* copy the must buy information in to the buysFor array */
    /* ... and remove the target from the who array */

    if (debugging) {
	printf ("#Must Buys = %d\n", nMust);
    }
    for (i=0; i<nMust; i++) {
	AddBuyer (mustBuy[i][0], mustBuy[i][1], who);
    }

    /* compress the who array */
    
    for (i=0, j=0; i<nPeople; i++)
        if (who[i] >= 0)
            who[j++] = who[i];
    nLeft = j;

    /* for each person, pick someone from the who array */
    /* that doesn't violate the avoid constraints */

    for (i=0; i<nPeople; i++) {
        if (buysFor[i] >= 0)        /* skip this person if already handled*/
            continue;

        for (j=0; j<nLeft; j++)     /* check for at least one possible */
	    if (!avoid[i][who[j]])  /* ... match */
	        break;

        if (j >= nLeft)
            return FALSE;	/* can not find a match for i */
		
        /* search for a match */

        for (j=0; j<100; j++) {
            randIndex = Random(nLeft);
	    if (!avoid[i][who[randIndex]])
	        break;
        }
        if (j >= 100)
	    return FALSE;       /* still cannot find match */
		
        buysFor[i] = who[randIndex];
	for (j=randIndex; j<nLeft-1; j++)
	    who[j] = who[j+1];
        nLeft--;
    }

    return TRUE;		/* we did it */
}




/* Main -- Main Program */

int main (int argc, char *argv[])
{
    char termCh;
    char abuf[81], tbuf[81];
    int familyHead, i, j, agent, target;
    int p1, p2;
    int tok;
    
    randomSeed = (unsigned int)time(NULL);
    inFile = stdin;

    for (i=1; i<argc; i++) {
        if (strcmpi (argv[i],"-v") == 0) {
            verbose = TRUE;
        }
        else if (strcmpi (argv[i], "-s") == 0) {
            shorter = TRUE;
        }
        else if (strcmpi (argv[i], "-x") == 0) {
            fprintf (stderr, "DEBUGGING ON\n");
            debugging = TRUE;
        }
        else if (strcmpi (argv[i], "-h") == 0) {
            Usage();
            exit (0);
        }
	else if (strcmpi (argv[i], "-r") == 0 && i<argc-1) {
	    i++;
	    randomSeed = (unsigned int)atol(argv[i]);
	}
        else {
            inFile = fopen (argv[i], "r");
            if (!inFile) {
                fprintf (stderr, "Unable to Open File [%s]\n", argv[i]);
                exit (1);
            }
        }
    }

/* initialize the avoidance and must buy matricies */

    memset (avoid, 0, sizeof (avoid));
    memset (mustBuy, 0, sizeof(mustBuy));

/* read the input file */

    familyHead = 0;
    while ((tok=GetToken(abuf)) != EOF) {
        switch (tok) {
        case ';':        /* end of family */
            if (debugging) {
                fprintf (stderr, "Finishing Family: ");
                for (i=familyHead; i<nPeople; i++ )
                    fprintf (stderr, "%s, ", person[i]);
                fprintf (stderr, "\n");
            }
            familyHead = nPeople;
	    break;

        case 'A':       /* add a member to the list and current family */
            if (LookupName (abuf) >= 0) {
                fprintf (stderr, "Name [%s] is a Duplicate\n", abuf);
                exit (1);
            }
            if (nPeople >= MAX_PERSON) {
                fprintf (stderr, "Too Many People in List\n");
                exit (1);
            }

            person[nPeople] = StrSave (abuf);
            for (i=familyHead; i<=nPeople; i++) {
                avoid[i][nPeople] = TRUE;
                avoid[nPeople][i] = TRUE;
            }
            nPeople++;
            break;

        case '%':       /* add an avoidance */
            p1 = ReadPerson ();
            p2 = ReadPerson ();
	    if (p1 < 0 || p2 < 0) {
	        fprintf (stderr, "Bad Avoid List\n");
		exit(1);
	    }
            avoid[p1][p2] = TRUE;
	    if (debugging) {
                fprintf (stderr, "Avoid: %s, %s\n",
                    person[p1], person[p2]);
	    }
            break;

        case '=':       /* add a must buy */
            p1 = ReadPerson ();
            p2 = ReadPerson ();
	    if (p1 < 0 || p2 < 0) {
	        fprintf (stderr, "Bad Must Buy List\n");
		exit(1);
	    }
	    if (nMust >= MAX_PERSON) {
                fprintf (stderr, "Too Many Must Buy Lists\n");
                exit (1);
	    }
            if (debugging) {
                fprintf (stderr, "MustBuy: %s, %s\n",
                    person[p1], person[p2]);
	    }
            mustBuy[nMust][0] = p1;
            mustBuy[nMust][1] = p2;
            nMust++;
            break;

        case ',':           /* ignore commas */
            break;

        default:
            fprintf (stderr, "Syntax error in file ");
            if (nPeople > 0) 
                fprintf (stderr, "after: %s\n", person[nPeople-1]);
            else
                fprintf (stderr, "before any people\n");
            break;
        }
    }

/* print the names and avoid list */

    if (verbose) {
        for (i=0; i<nPeople; i++)
            printf ("[%2d] %s\n", i, person[i]);
    
        printf ("\n\n");
        for (i=0; i<nPeople; i++) {
            for (j=0; j<nPeople; j++)
                printf (" %c", (avoid[i][j] ? 'X' : '-'));
            printf ("\n");
        }
        printf ("\n\n");
        for (i=0; i<nMust; i++)
            printf ("[%2d] %-10s Must Buy For [%2d] %s\n",
                mustBuy[i][0], person[mustBuy[i][0]],
                mustBuy[i][1], person[mustBuy[i][1]]);
    }
    
/* generate the buys for list */

    Randomize ();

    for (i=0; i<100; i++)
        if (GenerateBuyList())
            break;

    if (i>= 100) {
        fprintf (stderr, 
            "Unable to Generate Buy List after %d attempts\n", i);
        exit (1);
    }

/* print the buy list */

    printf ("# Seed %u\n\n", randomSeed);
    for (i=0; i<nPeople; i++) {
        printf ("%-*s Buys For %s\n", 
            (shorter ? 10 : 50), person[i], person[buysFor[i]]);
        if (!shorter)
            printf ("\n\n"
                "-------------------------------------------------------\n"
                "\n\n");
    }

    return 0;
}

--------------010504010903070701040200--