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

#ifndef FALSE
#define FALSE (0!=0)
#define TRUE (0==0)
#endif

static int debug = FALSE;

unsigned int _x, _a, _b, _c;
void initRandom (unsigned int s1, unsigned int s2, unsigned int s3,
		 unsigned int x0)
{
  _x = x0;
  _a = s1;
  _b = s2;
  _c = s3;
  _x++;
  _a = (_a ^ _c ^ _x);
  _b = (_b + _a);
  _c = ((_c + (_b >> 1)) ^ _a);
}

unsigned int irand127 (void)
{
  // assert returns unsigned value that fits in an int
  _x++;
  _a = (_a ^ _c ^ _x);
  _b = (_b + _a);
  _c = ((_c + (_b >> 1)) ^ _a);
  return (int) (_c & 127);
}

typedef struct Elves
{
  char *name;
  int domicile;
  int places_willing_to_ship_to;
  int parcels_created;
} Elves;

int parcels_remaining_to_send[128];
int parcels_remaining_to_receive[128];
int parcels_received[128];

#define Europe 1
#define USA 2

//  the contents of this table may change up to the last minute...
Elves Elf[] = {
  {"James G Watt", Europe, USA + Europe, 4},
  {"Tony Lindberg", Europe, USA + Europe, 3},
  {"Torben Rieckmann", Europe, Europe, 1},
  {"Jacek Selanski", Europe, Europe, 2},
  {"Chris Romero", USA, USA + Europe, 1},
  {"Todd Williams", USA, USA, 1},
  {"Darryl Hirschler", USA, USA + Europe, 4},
  {"Toppsi Krett", Europe, Europe, 5},
  {"Robert LaCour Mitchell", USA, USA, 2},
  {"Ross Burnett", Europe, USA + Europe, 3},	// is he USA?
  {"Robin Jubber", Europe, USA + Europe, 1},
  {"Fairtrade Gorillas", Europe, USA + Europe, 3},	// I think...
  {"Olivier Orillard", Europe, Europe, 1},
  {"Graham Toal", USA, USA + Europe, 1},
  {"Brett Walach", USA, USA + Europe, 4},
  {"Ola Jaensson", Europe, USA + Europe, 1},
  {"Andreas Mathey", Europe, USA + Europe, 3},	// is he?
  {"Chris Parsons", Europe, USA + Europe, 1},	// I think...
  {"Jonathan Sailer", USA, USA + Europe, 1},
  {"Victor Marland", Europe, USA + Europe, 1},
  {"Valsitsar Amiz", Europe, USA + Europe, 3},
  {"Clay Cowgill", USA, USA + Europe, 3},
  {"Malban Vide", Europe, Europe, 1},
  {NULL, 0, 0, 0}
};

int rand_up_to (int max)
{				// return 0..max inclusive
  return (int) (irand127 () % ((unsigned int) max + 1U));
}

int shuffle[128];
void Randomise (int last)
{
  int i, j, r;

  for (i = 0; i <= last; i++)
    shuffle[i] = i;
  for (i = last; i > 0; i--) {
    r = rand_up_to (last);
    j = shuffle[i];
    shuffle[i] = shuffle[r];
    shuffle[r] = j;
  }
}

int main (int argc, char **argv)
{
  // First pass - select Europe only:
  int players, each, did_one, ships;
  int best_seed = 1, best_ships = 999;
  int NEXT_SEED = 0;
  int no_swaps = FALSE;

  if ((argc > 1) && (strcmp(argv[1], "--noswaps") == 0)) {
    no_swaps = TRUE;
    argv++; argc--;
  }
  
  // I'm just putting this code out for review...
  fprintf (stderr, "UNTIL THE PLEDGES ARE FINALISED ON FRIDAY NIGHT,\n");
  fprintf (stderr, "THE OUTPUT OF THIS PROGRAM IS LIABLE TO CHANGE.\n");
  fprintf (stderr, "So... do not post these results.\n");

RESTART:			// loop until there are no odd parcels left
				// over!!!
  NEXT_SEED++;
  initRandom ((argc == 2 ? (int) atol (argv[1]) : NEXT_SEED),
	      (argc == 2 ? (int) atol (argv[1]) : NEXT_SEED) >> 8,
	      (argc == 2 ? (int) atol (argv[1]) : NEXT_SEED) >> 16, 78);

  ships = 0;
  players = 0;
  for (;;) {
    if (!Elf[players].name)
      break;
    players += 1;
  }
  players -= 1;

  for (each = 0; each <= players; each++) {
    parcels_remaining_to_send[each] = Elf[each].parcels_created;
    parcels_remaining_to_receive[each] = Elf[each].parcels_created;
    parcels_received[each] = 0;
  }

  {				// extra scope to allow dynamic array
				// declaration.
  int from_to[players + 1][players + 1];	// A can't send more than 1

    // to B
  int idxfrom, from, idxto, to;

  int find_recipient (int preferred_country, int players, int me, int debug)
  {
    int idxto, to;
    int a, b, c;

    for (idxto = 0; idxto <= players; idxto++) {
      to = shuffle[idxto];
      a = (to != me);
      if ((NEXT_SEED > 1024 * 1024) && no_swaps) {
	b = (!from_to[me][to]);	// not finding any - relax the constraint on
				// no swaps a -> b -> a ...
      } else {
	b = (!from_to[me][to]) & (!from_to[to][me]);
      }
      c = ((Elf[to].domicile & preferred_country) != 0);
      if (debug) {
	fprintf (stderr, "From %s[%d]\n", Elf[me].name, me);
	fprintf (stderr, "  To %s[%d]\n", Elf[to].name, to);
	fprintf (stderr, "  to myself? %s\n", a ? "No" : "Yes");
	fprintf (stderr, "  sent one already? %s\n", b ? "No" : "Yes");
	fprintf (stderr, "  compatble destination? %s\n", c ? "Yes" : "No");
	fprintf (stderr, "     Dest: %s\n",
		 Elf[to].domicile == USA ? "USA" : "Europe");
	fprintf (stderr, "\n");
      }
      if (a && b && c && (parcels_remaining_to_receive[to] > 0)) {
	return to;
      }
    }
    return -1;
  }

    for (from = 0; from <= players; from++) {
      for (to = 0; to <= players; to++) {
	from_to[from][to] = FALSE;
      }
    }

  rerandomise:
//fprintf(stderr, "\n");
    // we only do one parcel in each loop, then re-randomise!
    // this is how we handle more than one parcel per sender
    Randomise (players);	// INclusive upper bound
    for (idxfrom = 0; idxfrom <= players; idxfrom++) {
      from = shuffle[idxfrom];
      if (parcels_remaining_to_send[from] <= 0)
	continue;

      if ((Elf[from].places_willing_to_ship_to == Europe)) {	// to Europe
								// ONLY?
	to = find_recipient (Europe, players, /* excluding */ from, FALSE);
	if (debug)
	  fprintf (stderr,
		   "Europe only: %s[@%d] (%d -> %d) -> %s[@%d] (%d -> %d)\n",
		   Elf[from].name, from, parcels_remaining_to_send[from],
		   parcels_remaining_to_send[from] - 1, Elf[to].name, to,
		   parcels_received[to], parcels_received[to] + 1);
	parcels_received[to] += 1;
	parcels_remaining_to_receive[to] -= 1;
	parcels_remaining_to_send[from] -= 1;
	from_to[from][to] = TRUE;
	goto rerandomise;
      } else if ((Elf[from].places_willing_to_ship_to == USA)) {	// to 
									// USA 
									// ONLY?
	to = find_recipient (USA, players, /* excluding */ from, FALSE);
	if (debug)
	  fprintf (stderr,
		   "USA only: %s[@%d] (%d -> %d) -> %s[@%d] (%d -> %d)\n",
		   Elf[from].name, from, parcels_remaining_to_send[from],
		   parcels_remaining_to_send[from] - 1, Elf[to].name, to,
		   parcels_received[to], parcels_received[to] + 1);
	parcels_received[to] += 1;
	parcels_remaining_to_receive[to] -= 1;
	parcels_remaining_to_send[from] -= 1;
	from_to[from][to] = TRUE;
	goto rerandomise;
      }
    }
    // fprintf (stderr, "I think that's everyone with same-continent
    // places_willing_to_ship_to taken care of!\n");

  rerandomise2:
//fprintf(stderr, "\n");
    Randomise (players);

    // Now we loop over recipients and make sure everyone receives at least
    // one present!

    for (idxto = 0; idxto <= players; idxto++) {
      to = shuffle[idxto];
      if (parcels_received[to] == 0) {
	// find someone to send to this person in the same country
	for (idxfrom = 0; idxfrom <= players; idxfrom++) {
	  from = shuffle[idxfrom];
	  if ((from != to)
	      && (parcels_remaining_to_send[from] > 0)
	      && (Elf[from].domicile == Elf[to].domicile)) {
	    if (debug)
	      fprintf (stderr,
		       "same country: %s[@%d] (%d -> %d) -> %s[@%d] (%d -> %d)\n",
		       Elf[from].name, from,
		       parcels_remaining_to_send[from],
		       parcels_remaining_to_send[from] - 1, Elf[to].name,
		       to, parcels_received[to], parcels_received[to] + 1);
	    parcels_received[to] += 1;
	    parcels_remaining_to_receive[to] -= 1;
	    parcels_remaining_to_send[from] -= 1;
	    from_to[from][to] = TRUE;
	    goto rerandomise2;
	  }
	}
	// find someone to send to this person from anywhere that's willing
	for (idxfrom = 0; idxfrom <= players; idxfrom++) {
	  from = shuffle[idxfrom];
	  if ((from != to) && (parcels_remaining_to_send[from] > 0)) {
	    ships++;
	    if ((argc == 2) && debug)
	      fprintf (stderr,
		       "transatlantic: %s[@%d] (%d -> %d) -> %s[@%d] (%d -> %d)\n",
		       Elf[from].name, from,
		       parcels_remaining_to_send[from],
		       parcels_remaining_to_send[from] - 1, Elf[to].name,
		       to, parcels_received[to], parcels_received[to] + 1);
	    parcels_received[to] += 1;
	    parcels_remaining_to_receive[to] -= 1;
	    parcels_remaining_to_send[from] -= 1;
	    from_to[from][to] = TRUE;
	    goto rerandomise2;
	  }
	}
      }
    }

    // fprintf (stderr, "Everyone has received at least one present
    // now...\n");
    // Now check if reciving more than they send?
    for (idxfrom = 0; idxfrom <= players; idxfrom++) {
      from = shuffle[idxfrom];
      if (parcels_remaining_to_send[from] > 0) {	// was while
	// start with places_willing_to_ship_to to same country if possible
	to =
	 find_recipient (Elf[from].domicile, players, /* excluding */ from,
			 FALSE);
	if (to >= 0) {
	  // this sender
	  if (debug)
	    fprintf (stderr,
		     "same country: %s[@%d] (%d -> %d) -> %s[@%d] (%d -> %d)\n",
		     Elf[from].name, from,
		     parcels_remaining_to_send[from],
		     parcels_remaining_to_send[from] - 1, Elf[to].name,
		     to, parcels_received[to], parcels_received[to] + 1);
	  parcels_received[to] += 1;
	  parcels_remaining_to_receive[to] -= 1;
	  parcels_remaining_to_send[from] -= 1;
	  from_to[from][to] = TRUE;
	  continue;
	}
	if (debug)
	  fprintf (stderr, "Looking for a recipient for %s[%d]\n",
		   Elf[from].name, from);
	// find someone to send to this person from anywhere that's willing
	to =
	 find_recipient (Elf[from].places_willing_to_ship_to, players, from,
			 FALSE);
	if (to >= 0) {
	  // this sender
	  ships++;
	  if ((argc == 2) && debug)
	    fprintf (stderr,
		     "transatlantic: %s[@%d] (%d -> %d) -> %s[@%d] (%d -> %d)\n",
		     Elf[from].name, from, parcels_remaining_to_send[from],
		     parcels_remaining_to_send[from] - 1, Elf[to].name, to,
		     parcels_received[to], parcels_received[to] + 1);
	  parcels_received[to] += 1;
	  parcels_remaining_to_receive[to] -= 1;
	  parcels_remaining_to_send[from] -= 1;
	  from_to[from][to] = TRUE;
	  continue;
	}

	goto RESTART;

	for (from = 0; from <= players; from++) {
	  if (parcels_remaining_to_send[from] == 0
	      && parcels_remaining_to_receive[from] == 0) {
	    fprintf (stdout, "%s:\n", Elf[from].name);
	  } else {
	    if (parcels_remaining_to_send[from] ==
		parcels_remaining_to_receive[from]) {
	      fprintf (stdout,
		       "%s: %d parcel%s left over that we can't allocate to anyone\n",
		       Elf[from].name, parcels_remaining_to_send[from],
		       parcels_remaining_to_send[from] > 1 ? "s" : "");
	    } else {
	      fprintf (stdout,
		       "%s: (%d remaining to send to %s; %d received, %d remaining to receive in %s)\n",
		       Elf[from].name, parcels_remaining_to_send[from],
		       Elf[from].places_willing_to_ship_to ==
		       USA ? "USA" : (Elf[from].places_willing_to_ship_to ==
				      Europe ? "Europe" : "Europe or USA"),
		       parcels_received[from],
		       parcels_remaining_to_receive[from],
		       Elf[from].domicile == USA ? "USA" : "Europe");
	    }
	  }

	  for (to = 0; to <= players; to++) {
	    if (from_to[from][to]) {
	      fprintf (stdout, "   -> %s", Elf[to].name);
              if (Elf[from].domicile != Elf[to].domicile) {
	        fprintf (stdout, " (Intl)");
              }
	      fprintf (stdout, "\n");
            }
	  }
	}
	exit (1);
      }

    }

    for (from = 0; from <= players; from++) {
      if (parcels_remaining_to_send[from] != 0
	  || parcels_remaining_to_receive[from] != 0) {
	goto rerandomise2;
      }
    }

    if (argc == 2) {
      for (from = 0; from <= players; from++) {
	if (parcels_remaining_to_send[from] == 0
	    && parcels_remaining_to_receive[from] == 0) {
	  fprintf (stdout, "%s:\n", Elf[from].name);
	} else {
	  if (parcels_remaining_to_send[from] ==
	      parcels_remaining_to_receive[from]) {
	    fprintf (stdout,
		     "%s: %d parcels left over that we can't allocate to anyone\n",
		     Elf[from].name, parcels_remaining_to_send[from]);
	  } else {
	    fprintf (stdout,
		     "%s: (%d remaining to send to %s; %d received, %d remaining to receive in %s)\n",
		     Elf[from].name, parcels_remaining_to_send[from],
		     Elf[from].places_willing_to_ship_to ==
		     USA ? "USA" : (Elf[from].places_willing_to_ship_to ==
				    Europe ? "Europe" : "Europe or USA"),
		     parcels_received[from],
		     parcels_remaining_to_receive[from],
		     Elf[from].domicile == USA ? "USA" : "Europe");
	  }
	}
	for (to = 0; to <= players; to++) {
          if (from_to[from][to]) {
            fprintf (stdout, "   -> %s", Elf[to].name);
            if (Elf[from].domicile != Elf[to].domicile) {
              fprintf (stdout, " (Intl)");
            }
            fprintf (stdout, "\n");
          }
	}
      }

      exit (0);
    }

    if (ships < best_ships) {
      best_ships = ships;
      best_seed = NEXT_SEED;
      if ((ships == 0) || !no_swaps) {
	if (debug || no_swaps) fprintf (stderr,
		 "SEED WAS %d (with no transatlantic shipping needed)\n",
		 NEXT_SEED);
	for (from = 0; from <= players; from++) {
	  if (parcels_remaining_to_send[from] == 0
	      && parcels_remaining_to_receive[from] == 0) {
	    fprintf (stdout, "%s:\n", Elf[from].name);
	  } else {
	    if (parcels_remaining_to_send[from] ==
		parcels_remaining_to_receive[from]) {
	      fprintf (stdout,
		       "%s: %d parcels left over that we can't allocate to anyone\n",
		       Elf[from].name, parcels_remaining_to_send[from]);
	    } else {
	      fprintf (stdout,
		       "%s: (%d remaining to send to %s; %d received, %d remaining to receive in %s)\n",
		       Elf[from].name, parcels_remaining_to_send[from],
		       Elf[from].places_willing_to_ship_to ==
		       USA ? "USA" : (Elf[from].places_willing_to_ship_to ==
				      Europe ? "Europe" : "Europe or USA"),
		       parcels_received[from],
		       parcels_remaining_to_receive[from],
		       Elf[from].domicile == USA ? "USA" : "Europe");
	    }
	  }
	  for (to = 0; to <= players; to++) {
	    if (from_to[from][to])
	      fprintf (stdout, "   -> %s\n", Elf[to].name);
	  }
	}

	exit (0);
      } else {
	if (debug || no_swaps) fprintf (stderr, "SEED WAS %d (with %d transatlantic shippings)\n",
		 NEXT_SEED, ships);
      }
    }

    goto RESTART;
  }
  return 1;
}