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 contest@php-editors.com
============================= 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!