/*
 * To demonstrate this algorithm:
 *	cc -O -o risto risto.c
 *	risto G | tee rres | risto E | risto D | diff - rres
 *
 *
 * From a deck of size  (K! + K - 1), K cards are selected.
 * Devise a strategy to conceal one of those K cards,
 *  reorder the remainder, and have confederate  
 *  determine the removed card.
 * Since C(K!+K-1, K-1) * K! = C(K!+K-1, K) no strategy
 *  can exist for a decksize larger than (K! + K - 1).
 * We demonstrate a maximal solution when K = 5.
 *
 * From a deck of size 124 (1:124), 5 cards are selected.
 * Pick one, order the others so that accomplice can
 *	identify the 5th card.
 */
#include	<stdio.h>
#include	<stdlib.h>

struct foursome {
	short c[4];
};

void sort5(short *s)
{
	short	t;
	#define	CSWAP(i, j)	\
		if (s[i] > s[j]) t = s[i], s[i] = s[j], s[j] = t

	CSWAP(0, 2);
	CSWAP(1, 3);
	CSWAP(0, 1);
	CSWAP(2, 3);
	CSWAP(1, 2);
	CSWAP(3, 4);
	CSWAP(2, 3);
	CSWAP(1, 2);
	CSWAP(0, 1);
}

int ixmax(int a0, int a1, int a2, int a3)
{
	if (a0 > a1)
		if (a0 > a2)
			return a0 > a3 ? 0 : 3;
		else
			return a2 > a3 ? 2 : 3;
	else
		if (a1 > a2)
			return a1 > a3 ? 1 : 3;
		else
			return a2 > a3 ? 2 : 3;
}

int	dsub(int c1, int c2, int c3, int pix)
{
	int	loc, f;

	for (loc = 0, f = 24; loc < c1; loc++) {
		if (f-- < 0 && pix-- == 0)
			return loc;
	}
	for (f = f >= 0 ? f + 25 : 24; loc < c2; loc++) {
		if (f-- < 0 && pix-- == 0)
			return loc;
	}
	for (f = f >= 0 ? f + 25 : 24; loc < c3; loc++) {
		if (f-- < 0 && pix-- == 0)
			return loc;
	}
	for (f = f >= 0 ? f + 25 : 24; loc < 124; loc++) {
		if (f-- < 0 && pix-- == 0)
			return loc;
	}
	return -1;
}

int decoder(struct foursome a)
{
	struct foursome b = a;
	int	i, t, j4, j3, j2, pix;
	int	c1, c2, c3;

#define	SWAPWITH(x, y)	\
		t = b.c[x], b.c[x] = b.c[y], b.c[y] = t

	j4 = ixmax(b.c[0], b.c[1], b.c[2], b.c[3]);
	SWAPWITH(3, j4);
	j3 = ixmax(b.c[0], b.c[1], b.c[2], 0);
	SWAPWITH(2, j3);
	j2 = ixmax(b.c[0], b.c[1], 0, 0);
	SWAPWITH(1, j2);
	pix = j4 * 6 + j3 * 2 + j2;

	/* We now have the 4 cards and sorted order
	 * (and have remembered  code for the original
	 *  ordering as 0 <= pix < 24)
	 * But this may not be the proper sequence
	 * for the fuel-heuristic!  Rather than more
	 * coffee to find a proper sequence we'll
	 * just try them all and pick one which works!
	 */
	for (i = 0; i < 4; i++) {
		c1 = (b.c[(i+1) % 4] - b.c[i]) % 124;
		c2 = (b.c[(i+2) % 4] - b.c[i]) % 124;
		c3 = (b.c[(i+3) % 4] - b.c[i]) % 124;
		if (c3 != 123 && 123 == dsub(c1, c2, c3, 23))
			return (dsub(c1, c2, c3, pix) + b.c[i] - 1) % 124 + 1;
	}
	/* Not Reached! */
	printf("Unable to decode!\n");
	exit(1);
}

short	Deck[124];
struct foursome Offer;
int	Mysterycard;

/* Encode Deck[0] ... Deck[4] into Offer.
 * Try every possibility and use whichever one works!
 */

void encoder()
{
	int	a0, a1, a2, a3, a4;
	for (a0 = 0; a0 < 5; a0++)
	for (a1 = 0; a1 < 5; a1++)
	if (a1 != a0)
	for (a2 = 0; a2 < 5; a2++)
	if (a2 != a0 && a2 != a1)
	for (a3 = 0; a3 < 5; a3++)
	if (a3 != a0 && a3 != a1 && a3 != a2) {
		a4 = 10 - a0 - a1 - a2 - a3;
		Offer.c[0] = Deck[a0];
		Offer.c[1] = Deck[a1];
		Offer.c[2] = Deck[a2];
		Offer.c[3] = Deck[a3];
		Mysterycard = Deck[a4];
		if (decoder(Offer) == Mysterycard)
			return;
	}
	/* Not reached :-) */
	Mysterycard = -1;
}

/* To make this all self-contained, we use a trivial random() */
int rixxy(int range)
{
	static unsigned seed = 123456789;
	seed *= 1103515245;
	seed += 12345;
	return seed % range;
}

void genner()
{
	int	i, j, t, iter;

	for (i = 0; i < 124; i++)
		Deck[i] = i + 1;
	/* 10,000 random trials won't take long and should be convincing */
	for (iter = 0; iter < 10000; iter++) {
		for (i = 0; i < 5; i++) {
			j = rixxy(124 - i) + i;
			t = Deck[i], Deck[i] = Deck[j], Deck[j] = t;
		}
		sort5(Deck);
		printf("%3d %3d %3d %3d %3d\n",
			Deck[0], Deck[1], Deck[2],
			Deck[3], Deck[4]);
	}
}

int main(int argc, char **argv)
{
	int	i;

	setlinebuf(stdout);

	if (argv[1]) {
		switch (argv[1][0]) {
		case 'G':
			genner();
			exit(0);
		case 'E':
			while (5 == scanf("%3d %3d %3d %3d %3d",
					Deck + 0, Deck + 1, Deck + 2,
					Deck + 3, Deck + 4)) {
				encoder();
				printf("%3d %3d %3d %3d\n",
					Offer.c[0],
					Offer.c[1],
					Offer.c[2],
					Offer.c[3]);
			}
			exit(0);
		case 'D':
			while (4 == scanf("%3d %3d %3d %3d",
					Deck + 0, Deck + 1, Deck + 2,
					Deck + 3)) {
				for (i = 0; i < 4; i++)
					Offer.c[i] = Deck[i];
				Deck[4] = decoder(Offer);
				sort5(Deck);
				printf("%3d %3d %3d %3d %3d\n",
					Deck[0], Deck[1], Deck[2],
					Deck[3], Deck[4]);
			}
			exit(0);
		default:
			break;
		}
	}
	printf("Usage: risto X\n\
		 where X is G, E or D for Generate, Encode, Decode\n");
	exit(0);
}