Anyone for Cards ??? Hmm.. just imagine that brand new deck of cards, just out the box and all in a nice perfect order. Well that's were I come in, im going to get hold of them and CUT, FLIP and SHUFFLE them all out of sequence. Guess what - your going to get them all back into order...eck 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 this Contest, I'll give your script a deck in disarray (up to 52 cards). Your script will have to tell me what operations to perform (CUTS, SHUFFLES, and FLIPS) in order to return the deck to its pristine unmixed state. =========================================================================== DEADLINE FOR SUBMISSION OF ENTRIES IS - Monday 14th April 2003 at 23.59 (GMT) SUBMISSION: send to firstname.lastname@example.org ============================= FULL DETAILS ================================ I. THE SOLUTION 1) your script will be given a shuffled deck - ... in a text file named 'deck.txt' 2) your script 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. 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 script with an unmixed deck. 6) The deck I give your script WILL have a solution. 7) Decks will be supplied using a text file named 'deck.txt' IV. SCORING AND WINNING You script will be tested with 5 decks of cards (5 runs). 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 - time on all five final runs. Quickest script wins. V. YOUR SCRIPT AND RESTRICTIONS o Your script should generate ONLY the following output (on screen): a) A single character string with one character for every move b) ... consisting of only the upper case letters C, S, and F c) ... ending with the total number of moves. o Restrictions a) Maximum execution time of 60 seconds per run (per deck) b) One text file is allowed for temporary storage if required. c) No databases systems allowed, only one flatfile type. d) Must run on Windows, Unix systems e) Must run with PHP4.2+ (default config and lib) f) No Client Scripts g) No Flash ============================== EXAMPLES ================================= Here's some messed up decks for you to try ... along with answers your script may generate ... CAcaDBdb --> SCF dbDBcaCA --> CSF AcCeJgbidEfGBIDaFhHj --> SSSCFSCSS 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. **Remember that your solution must have the operation count taged to the end. Note that there may be BETTER solutions than these, but these at least work!