**** Thank you for your inquiry .... hope you find the time for an entry!!!!
**** THIS IS THE LONG FORM ... FOLLOWING THE SHORT FORM ARE THE DETAILS, SOME
**** TEST CASES, AND A C PROGRAM THAT MAY (or may not) BE USEFUL.
	=Fred   (fah@potm.ffast.att.com) (attmail!hicinbothem)

Put away the Scrabble game and get out the cards.  
Cards are lovely.  They have an order, a purpose, a reason.

But once you take them out of the box, and start CUTTING them, and
SHUFFLING them, and FLIPPING them ... it's real hard to get them
back to where they started!  That's the challenge of the next POTM!

For an illustration, let's assume I have a deck with only eight cards,
(call them ABCDabcd), let me define those operations a bit better:

	a CUT transforms	ABCDabcd -> abcdABCD
	a SHUFFLE transforms	ABCDabcd -> aAbBcCdD (top card changes)
	a FLIP transforms	ABCDabcd -> dcbaDCBA

The question:	What do I have to do to a deck that looks like: dbDBcaCA 
		to get it back into ABCDabcd original starting order?

The answer:  CUT, then SHUFFLE, then FLIP (obviously).

     dbDBcaCA -> caCAdbDB 
                 caCAdbDB -> dcbaDCBA
                             dcbaDCBA -> ABCDabcd	(voila!)

For the POTM, I'll give your program a deck in disarray (up to 52 cards).
Your program will have to tell me what operations to perform (CUTS, SHUFFLES,
and FLIPS) in order to return the deck to its pristine unmixed state.

==========================  END OF SHORT VERSION ==========================

DEADLINE FOR SUBMISSION OF ENTRIES IS 11:59 PM EST Sunday June 12, 1994.

IMPORTANT:  Make sure any POTM mail goes to one of the following places:

		fah@potm.ffast.att.com		(preferred)
	[or]	ffast!potm!fah
	[or]	attmail!hicinbothem

Thanks!
=Fred

============================= THE GORY DETAILS ============================

I'm concerned about this one .... I haven't a clue whether there is any
way other than brute force to attack it .... but it FEELS like there may be!
Anyhow ... I'll leave y'all plenty of time to play with it!

DEADLINE FOR SUBMISSION OF ENTRIES IS 11:59 PM EST Sunday June 12, 1994.

I.   THE SOLUTION

	1) your program will be given a shuffled deck.
	2) your program is expected to output a string of C's, S's, and F's.
	3) the string of operations will be applied to the shuffled deck
		from left to right: SCF means SHUFFLE, then CUT, then FLIP.
		The resultant deck will then be scored against the ideal
		unmixed deck for scoring.
	4) your solution must be less than 500 operations.

II.  THE OPERATIONS (CUT, SHUFFLE, and FLIP)

	The "top" or the "first" card in the deck is the first card in
	the string - the "A" in the deck "ABCDabcd"

	a CUT transforms	ABCDabcd -> abcdABCD
	a SHUFFLE transforms	ABCDabcd -> aAbBcCdD (top card changes)
	a FLIP transforms	ABCDabcd -> dcbaDCBA

	1) A cut is a perfect cut - dividing the deck into two parts and
		exchanging the two halves
	2) The shuffle is a perfect shuffle - cards from the second half of
		the deck are perfectly interleaved with those of the first
		half ... note that the new "first" card is the frist card
		from the second half of the deck - the "other" kind of
		shuffle that does not change the first card is NOT allowed.
	3) A flip simply reverses the order of the cards - the bottom card
		becomes the top card and vice-versa (throughout the deck)

III.  THE DECK

	1) there will be a minimum of 2 cards and a maximum of 52 in the deck
	2) there will be an even number of cards in the deck: 2,4,6, ... ,50,52
	3) half the deck will be upper case ASCII, the other half lower case -
		the unmixed decks will all look like Aa, ABab, ABCabc, ABCDabcd,
		ABCDEabcde, ABCDEFabcdef, ABCDEFGabcdefg, ABCDEFGHabcdefgh,
		ABCDEFGHIabcdefghi, ABCDEFGHIJabcdefghij, .... etc. up to
		ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
	4) There will be a lower case letter for each upper case letter, no
		letters will be skipped or repeated.  In short, the unshuffled
		decks will be exactly as represented in item (3) - I won't try
		anything "funny" with the makeup of the decks.
	5) I will NOT present your program with an unmixed deck.
	6) The deck I give you WILL have a solution (of some length <500).
		It MAY have more than one solution ....

IV. SCORING AND WINNING

	I will present five shuffled decks, you will generate five
	sets of operations .... I will apply your operations to
	their respective shuffled decks - this should result in
	five decks which are (to some degree) unshuffled.  Each
	deck will then be scored against its ideal unmixed deck.

     a) You will get one point for every card in the correct position.
	For example,  in an eight card deck, if you come up with

	ABcdCbaD  then the cards marked with X are in the correct spot:
	XX---X--  (when compared with the unmixed ABCDabcd deck.  Thus
		  this answer would score three points.

	Obviously, the best score for a deck is the number of cards in
	the deck - assuming you get them back to the unmixed state.

	Scores for the five decks will be added together - high sum
	wins .... but in the event of ties, we apply the first tiebreaker:

     b) First tiebreaker is the minimum number of operations you needed
	for your solutions (summed over all five finals).  For example:

	prog1  dcbaDCBA  runs and prints out "F" - one flip
	prog2  dcbaDCBA  runs and prints out "FCC" - one flip, two cuts

	Since both answers yield ABCDabcd for a score of 8, prog1 would
	win because it required one move as opposed to three.

     c) Second tiebreaker - (sys+user) time on all five final runs.  Quickest
	program wins - but I'm betting it doesn't get this far!
	(Note there is a 10 minute limit on each run - see below!)

V.  YOUR PROGRAM

	o must eventually be compilable on the target machine ... 
	  K&R C is preferred for this one, since I will be running the
	  contest on a SPARCstation.  Bottom line: 
	  send whatever you want and I'll work hard to get it to compile.
	  (Sorry - I haven't found a C++ compiler yet on the box, nor do 
	  I really know how much ANSI-ness the C compiler will accept.)

	o must generate an a.out such that ARG1 is read as a string of
		cards representing the mixed-upo deck - one character per
		card, no whitespace, no surprises!

	o should ignore standard input

	o should generate its output on standard output, with nothing
	  appearing on standard error

	o should generate ONLY the following output:

		a) A single character string with one character for every move
		b) ... consisting of only the upper case letters C, S, and F
		c) ... with a new-line after the string

	  such that 	a.out DIRNAME > outfile

	  generates an outfile one line long with no white space
	  
	o LIMIT:  10,000 characters worth of source code - this will be
		  enforced (regardless of language) (comments not counted).
		  (My goal is to prevent humongous listings of all 
			possible (??) solutions - NOT to discourage legibility)

	o LIMIT:  Regardless of the length of the deck (up to 52 cards) and
		  the length of the solution (less than 500 operations), your
		  program should take no more than 10 minutes sys+user time.
		  If you have a "brute force" solution, I'd suggest you use
		  the times(2) system call to print out your best solution
		  when the time limit approaches!  (times(2) allows access to
		  "timex"-like information.)  Any program which runs for more
		  than 615 seconds without terminating will receive a score 
		  of zero for that run.  (My goal here is to avoid a repeat
		  of a previous POTM - where I had an entry that ran for over
		  a week ... oh well - no loophole THIS time)

VI.  SENDING ME THE SOURCE CODE - PLEASE USE EMAIL THIS TIME!!!!

	Unlike previous POTMs, please DO NOT USE UUTO to send me the
	source code.  Please email me the source code to me at:

		fah@potm.ffast.att.com		(preferred)
		attmail!hicinbothem		(will forward correctly)

	IMPORTANT:  Please use the following (or equivalent) lines at the
	front of the program you mail to me (this will help immeasurably!):

	/*  POTM ENTRY:  entryname (something clever please!		*/
	/*  Your Name:   First Last					*/
	/*  Your email:  log@machine.att.com (or whatever)		*/
	/*  compilation instructions (if other than "make entryname")	*/

	IMPORTANT:  ENTER EARLY - you will receive weekly standings and
	you will resolve any portability issues early.  You may improve
	your entry at any time by simply sending me another entry - so it
	pays to enter earlier!

	IMPORTANT:  AFTER you mail me an entry, I will run a system test on
	it and ship you the results - the system test results comprise the
	weekly standings.

	IMPORTANT:  If you don't hear from me within a few days - it may mean
	that my mail got screwed up .... please follow up with an inquiry to
	attmail!hicinbothem .... hopefully all the bugs are worked out!

VII.  CONSOLATION AWARDS:

	o best entry name:  please do NOT be boring, and please DO
	  include your program name and your email address in the
	  opening comments of your program (see VI)!

	o best answers to the theoretical questions

Thanks!  Looking forward to your entry.

=Fred

============================== TEST CASES =================================

Here's some messed up decks for you to try ... along with answers your
program may generate ... if your program is cleverly named a.out, then

a.out CAcaDBdb 			  --> SCF
a.out dbDBcaCA 			  --> CSF
a.out AcCeJgbidEfGBIDaFhHj	  --> SSSCFSCSS
a.out DeEfFgaGAbBcCd 		  --> CFSSSCFSSSCFSSSCFSSSFCSSSFCSSSFCSSS

In each case, applying the operations in order to the shuffled deck will
return it to its unmixed state.  For example shuffling, then cutting, then
flipping (SCF) the deck CAcaDBdb will return it to ABCDabcd.

Note that there may be BETTER solutions than these, but these at least work!

========================== THEORETICAL ISSUES =============================

I'll collect any email answers to these and publish along with the results!

* what is the minimum number of shuffles needed to return a deck of 2N 
	cards to its starting state?  (not so obvious!)

* can you ALWAYS find some combination of shuffles, cuts, and flips that
	will return ANY mixed deck with 2N cards to it unmixed state?

* can a shuffle be expressed as a series of cuts and flips?  for any
	deck size?

* is there any way to do this problem other than brute force?  (the winner
	will share with us I'm sure!)

=============================== A PROGRAM ==================================

/* This program will apply a series of operations to a deck - I will
	use it to test the output of your program entry.  Unlike your
	entry, this program requires TWO arguments - but you may find
	the Cut, Shuffle, and Flip routines useful.			*/

#define MAXCARDS 100
static char tmpdeck[MAXCARDS];		/* a temporary deck 		*/

/************************************************************************/

void Cut(deck,len) 			/* cut a deck in half */
char *deck;
int len;
{
register char *p,*q;
    strcpy(tmpdeck,deck);
    /* move bottom to top */
    for(p=tmpdeck+len/2,q=deck;*p!='\0';p++,q++) { *q = *p; }
    /* move top to bottom */
    for(p=tmpdeck;*q!='\0';p++,q++) { *q = *p; }
}

void Flip(deck,len)			/* flip a deck */
char *deck;
int len;
{
register char *p,*q;
    strcpy(tmpdeck,deck);
    /* reverse deck */
    for(q=deck,p=tmpdeck+len-1;*q!='\0';q++,p--) { *q = *p; }
}

void Shuffle(deck,len)			/* shuffle a deck perfectly */
char *deck;
int len;
{
register char *p,*q;
    strcpy(tmpdeck,deck);
    /* shuffle bottom half */
    for(p=tmpdeck+len/2,q=deck;*p!='\0';p++,q+=2) { *q = *p; }
    /* shuffle top half */
    for(p=tmpdeck,q=deck+1;q < deck+len;p++,q+=2) { *q = *p; }
}

/******************  MAIN PROGRAM  **************************************/

main(argc,argv)
int argc;
char **argv;
{
char deck[MAXCARDS];
char moves[500];
int index,NUMCARDS,NUMMOVES;

/*  argv[1] is the collection of moves to make on the deck		*/
/*  argv[2] contains the shuffled deck of cards				*/
/*  deck[0] is the top card in the deck,  deck[1] is the next card,
	and so forth to the bottom of the deck				*/

if(argc<3)
	{
	printf("Sorry - Usage: ARG1=move_string; ARG2=deck_string\n");
	exit(1);
	}

strcpy(moves,argv[1]);
NUMMOVES=strlen(moves);
strcpy(deck,argv[2]);
NUMCARDS=strlen(deck);
	printf("The input deck had %d cards:\n	%s\n",NUMCARDS,deck);
	printf("   To which we apply the %d moves: %s\n",NUMMOVES,moves);
index=0;
while(index












Make your own free website on Tripod.com