/*
#### ## # # ##### ##
# # # ## # # # #
#### # # # # # # # #
# ###### # # # # ######
# # # # # ## # # #
#### # # # # # # #
This is a program that's only likely to be needed one day a year :-)
Given a list of people, where they live, where they're willing to ship to,
and how many presents they are willing to swap... it generates a graph of
who sends to whom, limited by some constraints:
1) some people will only ship to their own continent (the choices are USA or Europe)
2) if possible, a recipient is chosen on the same continent (to reduce shipping costs)
even if the person is willing to ship abroad
3) If there is international shipping necessary, no one person will be asked to
mail more than one gift abroad
4) we will try to minimise - preferably to zero:
A) international shipments
B) left-over gifts
C) swaps (i.e. when A sends to B, and B sends to A)
The program is heuristic driven and different results can be obtained with
different combinations of --noswaps --nospares --nointl
- there's a bit of hill-climbing involved, and there's no clean-up phase
after a solution is found (such as a genetic algorithm or simulated annealing).
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/*
./santa --noswap
SEED WAS 76346 (intl: 0 swap: 0 spare: 0)
Improved Results:
James G Watt -> Brett Walach -> Darryl Hirschler -> Jonathan Kade -> Jonathan Kade -> Brett Walach
-> Ross Burnett Todd Williams -> Brett Walach Brett Walach Victor Marland -> Jonathan Kade
-> Olivier Orillard -> Nathan Hulett Ross Burnett -> Darryl Hirschler -> James G Watt Laucsap Noslohcin
-> Andreas Mathey Darryl Hirschler -> Torben Rieckmann -> Graham Toal Valsitsar Amiz -> Robin Jubber
-> Chris Malcolm -> Chris Romero -> Toppsi Krett -> Clay Cowgill -> James G Watt Jonathan Kade
Tony Lindberg -> Todd Williams -> Valsitsar Amiz -> Jonathan Sailer -> Toppsi Krett -> Darryl Hirschler
-> Toppsi Krett -> Jonathan Sailer Robin Jubber Ola Jaensson -> Andreas Mathey -> Brett Walach
-> Andreas Mathey -> Nathan Hulett -> Toppsi Krett -> Fairtrade Gorillas Clay Cowgill -> Clay Cowgill
-> Laucsap Noslohcin Toppsi Krett Fairtrade Gorillas Andreas Mathey -> Darryl Hirschler Jonathan Sailer
Torben Rieckmann -> James G Watt -> Tony Lindberg -> Toppsi Krett -> Robert LaCour Mitchell -> Clay Cowgill
-> Tony Lindberg -> Jacek Selanski -> Jacek Selanski -> Ross Burnett -> Nathan Hulett Chris Malcolm
Jacek Selanski -> Fairtrade Gorillas -> Ross Burnett -> Fairtrade Gorillas Malban Vide -> Chris Parsons
-> James G Watt -> Victor Marland Olivier Orillard Chris Parsons -> Valsitsar Amiz
-> Ola Jaensson -> Malban Vide -> Tony Lindberg -> Valsitsar Amiz Nathan Hulett
Chris Romero Robert LaCour Mitchell Graham Toal Jonathan Sailer -> Robert LaCour Mitchell
*/
#ifndef FALSE
#define FALSE (0!=0)
#define TRUE (0==0)
#endif
static int debug = FALSE;
static int verbose = 0;
static int no_intl = FALSE, no_swaps = FALSE, no_spares = 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...
const 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},
{"Robin Jubber", Europe, USA + Europe, 1},
{"Fairtrade Gorillas", Europe, USA + Europe, 3},
{"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},
{"Chris Parsons", Europe, USA + Europe, 1},
{"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},
// NOT CONFIRMED:
{"Nathan Hulett", USA, USA + Europe, 3},
{"Laucsap Noslohcin", Europe, Europe, 1},
{"Jonathan Kade", USA, USA + Europe, 3},
{"Jonathan Sailer", USA, USA + Europe, 1},
{"Chris Malcolm", Europe, USA + 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;
int intls = 0, swaps = 0, spares = 0;
int best_intls = 999, best_swaps = 999, best_spares = 999;
int manual_seed = FALSE, NEXT_SEED = 0, best_seed = 1, TARGET_SEED = -1;
int can_finish_now = FALSE;
while ((argc > 1) && (*argv[1] == '-')) {
if (strncmp (argv[1], "--noswap", 8) == 0) {
no_swaps = TRUE;
argv++;
argc--;
continue;
}
if (strcmp (argv[1], "--nointl") == 0) {
no_intl = TRUE;
argv++;
argc--;
continue;
}
if (strcmp (argv[1], "--nospares") == 0) {
no_spares = TRUE;
argv++;
argc--;
continue;
}
if (strncmp (argv[1], "--swap", 6) == 0) {
no_swaps = FALSE;
argv++;
argc--;
continue;
}
if (strcmp (argv[1], "--intl") == 0) {
no_intl = FALSE;
argv++;
argc--;
continue;
}
if (strcmp (argv[1], "--spares") == 0) {
no_spares = FALSE;
argv++;
argc--;
continue;
}
if ((strcmp (argv[1], "--help") == 0) || (strcmp (argv[1], "-h") == 0)) {
fprintf (stderr,
"syntax: santa [--[no]swaps] [--[no]intl] [--[no]spares] [--seed NUM]\n\n");
exit (0);
continue;
}
if ((strcmp (argv[1], "--verbose") == 0) || (strcmp (argv[1], "-v") == 0)) {
verbose++;
argv++;
argc--;
continue;
}
if ((strcmp (argv[1], "--debug") == 0) || (strcmp (argv[1], "-d") == 0)) {
debug = TRUE;
argv++;
argc--;
continue;
}
if (strcmp (argv[1], "--seed") == 0) {
manual_seed = TRUE;
argv++;
argc--;
TARGET_SEED = (int) atol (argv[1]);
argv++;
argc--;
continue;
}
fprintf (stderr, "santa: unknown option %s - try --help\n\n", argv[1]);
exit (1);
}
if (argc > 1) {
fprintf (stderr, "santa: unknown parameter %s - try --help\n\n", argv[1]);
exit (1);
}
// 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++; if (NEXT_SEED == TARGET_SEED) can_finish_now = TRUE;
// ######################## COMPLETE RE-INITIALISATION ########################
initRandom (NEXT_SEED & 255, (NEXT_SEED >> 8) & 255, (NEXT_SEED >> 16) & 255, (NEXT_SEED >> 24) & 255);
intls = 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 (no_swaps) {
b = (!from_to[me][to]) && (!from_to[to][me]);
} else {
b = (!from_to[me][to]);
}
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;
}
void PRINT_RESULTS (FILE * stdout)
{
for (from = 0; from <= players; from++) {
fprintf (stdout, "%s", Elf[from].name);
if ((parcels_remaining_to_send[from] != 0)
&& (parcels_remaining_to_send[from] ==
parcels_remaining_to_receive[from])) {
fprintf (stdout, " (%d unallocated)",
parcels_remaining_to_send[from]);
}
fprintf (stdout, "\n");
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, " (I)");
}
if (from_to[to][from]) {
fprintf (stdout, " (S)");
}
fprintf (stdout, "\n");
}
}
}
}
for (from = 0; from <= players; from++) {
for (to = 0; to <= players; to++) {
from_to[from][to] = FALSE;
}
}
// ######################## END OF INITIALISATION ########################
rerandomise:
// we only do one parcel in each loop, then re-randomise!
// this is how we handle more than one parcel per sender
// ######################## FORCED SAME-CONTINENT DELIVERIES ########################
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 = 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 = 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;
}
}
// ######################## END OF FORCED SAME-CONTINENT DELIVERIES ########################
rerandomise2:
Randomise (players);
// Now we loop over recipients and make sure everyone receives at least one present!
// ######################## GUARANTEE AT LEAST ONE EACH ########################
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[from][to])
continue; // already sent one to them
if (no_swaps && from_to[to][from])
continue; // they've already sent one to me, and not allowed
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[from][to])
continue; // already sent one to them
if (no_swaps && from_to[to][from])
continue; // they've already sent one to me, and not allowed
if ((from != to) && (parcels_remaining_to_send[from] > 0)) {
intls++;
if (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;
}
}
}
}
// ######################## END OF GUARANTEE AT LEAST ONE EACH ########################
// ######################## RANDOM ASSIGNMENTS WITH PREF TO SAME CONTINENT ########################
for (idxfrom = 0; idxfrom <= players; idxfrom++) {
from = shuffle[idxfrom];
if (parcels_remaining_to_send[from] > 0) {
// 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) {
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) {
intls++;
if (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;
}
}
// ######################## END OF RANDOM ASSIGNMENTS WITH PREF TO SAME CONTINENT ########################
// ######################## ELIMIMATE INCOMPLETES ########################
spares = 0;
swaps = 0;
{
int this_persons_intls;
for (from = 0; from <= players; from++) {
this_persons_intls = 0;
for (to = 0; to <= players; to++) {
if (from_to[from][to] && from_to[to][from])
swaps += 1;
if ((from_to[from][to]) && (Elf[from].domicile != Elf[to].domicile))
this_persons_intls += 1;
}
if (this_persons_intls)
goto RESTART; // don't penalise one person by having them
// send out multiple international packets!
if (parcels_remaining_to_send[from] != 0
|| parcels_remaining_to_receive[from] != 0) {
if (parcels_remaining_to_send[from] ==
parcels_remaining_to_receive[from]) {
if (no_spares)
goto rerandomise2;
spares += parcels_remaining_to_send[from];
} else {
goto rerandomise2;
}
}
}
}
swaps = swaps >> 1;
// ######################## EXAMINE RESULTS ########################
// reject outright?
if (no_intl && (intls != 0))
goto RESTART;
if (no_swaps && (swaps != 0))
goto RESTART;
if (no_spares && (spares != 0))
goto RESTART;
// otherwise, hill-climb
if (
((intls < best_intls) && (no_swaps || swaps <= best_swaps) && (no_spares || spares <= best_spares))
||
((swaps < best_swaps) && (no_intl || intls <= best_intls) && (no_spares || spares <= best_spares))
||
((spares < best_spares) && (no_intl || intls <= best_intls) && (no_swaps || swaps <= best_swaps))
) {
best_intls = intls;
best_swaps = swaps;
best_spares = spares;
best_seed = NEXT_SEED;
fprintf (stdout,
"SEED WAS %d (intl: %d swap: %d spare: %d)\n",
NEXT_SEED, intls, swaps, spares);
if (manual_seed && can_finish_now) {
PRINT_RESULTS (stdout); // no columns
} else if (!manual_seed || ((manual_seed && can_finish_now))) {
FILE *pipe; // OK, a wee bit hacky...
pipe = popen ("/home/gtoal/src/santa/mcol", "w");
if (pipe == NULL) pipe = popen ("./mcol", "w");
if (pipe == NULL) pipe = popen ("mcol", "w");
fprintf (stdout, "Improved Results:\n\n"); fflush(stdout);
if (pipe) {
PRINT_RESULTS (pipe);
fclose (pipe);
} else PRINT_RESULTS (stdout);
}
if (manual_seed && can_finish_now) { // trying to reproduce previous result using a given seed
exit (0);
}
}
if (!intls && !swaps && !spares && !manual_seed) exit (0);
goto RESTART;
}
return 1;
}