Main Menu |
|
|
 |
Forums |
|
|
|
Programming
Contest |
| |
|
Documentation
|
| |
|
Partner
Sites |
|
|
Sponsors |
|
|
|
|
Code of leon
<?php
/***********************************************************
* lspencer_santarosa_edu.php
*
* This script was developed as an entry into the PHP-Editors.com contest.
* It takes a mixed deck of cards contained within the file deck.txt, and prints
* the set of SHUFFLE, CUT, and FLIP operations necesary to unmix the deck.
*
* Author: Leon Spencer <mail@leonspencer.com>
* School: Santa Rosa Junior College, Santa Rosa, CA
* Instructor: David Pearson [ removed for contest ]
* Date: March 26, 2003
*
************************************************************/
/*
RULES OF NEXT STEP:
--------------------------------------------------------------------------------------
Note: These rules were determine by examining the state of the operation list tree after
each iteration. Initially, the need was to avoid array index overflow by keeping
references to sets of invalid operations (i.e. operations that would lead you back
to the string you started with OR operations seen before that did not produce a
desire result). For example, if you perform two consecutive CUT operations on a
string/deck, you'll have the same string you started with. As a result, one of the
rules is you CANNOT perform consecutive CUT operations.
Rule #1: You cannot perform consecutive cuts - substring 'CC' not allowed in operation list.
Rule #2: You cannot perform consecutive flips - substring 'FF' not allowed in operation list.
Rule #3: The number of consecutive shuffles for a src string cannot exceed the length of the string
- substring matching pattern '[S]{string_length}' not allowed in operation list.
Rule #4: The number of consecutive shuffles/flip pairs for a src string cannot exceed the length of the string
- substring matching pattern '[SF]{string_length}' not allowed in operation list.
Rule #5: The number of consecutive flip/shuffles pairs for a src string cannot exceed the length of the string + 1
- substring matching pattern '[FS]{string_length + 1}' not allowed in operation list.
Rule #6: The number of consecutive shuffles/cut pairs for a src string cannot exceed the 2*length of the string
- substring matching pattern '[SC]{2 * string_length}' not allowed in operation list.
Rule #7: The number of consecutive cut/shuffles pairs for a src string cannot exceed the 2*length of the string
- substring matching pattern '[CS]{2 * string_length}' not allowed in operation list.
Rule #8: Two consecutive Cut/Flip pairs not allowed - requires 4 lookback.
- substring matching pattern 'CFCF' not allowed in operation list.
Rule #9: Two consecutive Flip/Cut pairs not allowed - requires 4 lookback.
- substring matching pattern 'FCFC' not allowed in operation list.
Rule #10: I NEED A TENTH RULE SO IT'S AN EVEN NUMBER OF RULES! Just looks better! :-)
*/
/*
KNOWN TARGET STRINGS
--------------------------------------------------------------------------------------
Note: This script relies on a comparison with a known target string to determin whether a
solution has been reached. Since restrictions on the data include even character counts between 2 and 52; and
no alpha chars skipped or repeated, the targeted string can be determined by looking at the length of the
mixed deck string. For example, if the mixed string has a length of 2, the I know 'A' and it's corresponding
'a' (lowercase) compose the string and the unmixed target is 'Aa'.
Looking at the possible lengths to 52, the below list of known unmixed deck target strings was computed.
*/
$target2 = 'Aa';
$target4 = 'ABab';
$target6 = 'ABCabc';
$target8 = 'ABCDabcd';
$target10 = 'ABCDEabcde';
$target12 = 'ABCDEFabcdef';
$target14 = 'ABCDEFGabcdefg';
$target16 = 'ABCDEFGHabcdefgh';
$target18 = 'ABCDEFGHIabcdefghi';
$target20 = 'ABCDEFGHIJabcdefghij';
$target22 = 'ABCDEFGHIJKabcdefghijk';
$target24 = 'ABCDEFGHIJKLabcdefghijkl';
$target26 = 'ABCDEFGHIJKLMabcdefghijklm';
$target28 = 'ABCDEFGHIJKLMNabcdefghijklmn';
$target30 = 'ABCDEFGHIJKLMNOabcdefghijklmno';
$target32 = 'ABCDEFGHIJKLMNOPabcdefghijklmnop';
$target34 = 'ABCDEFGHIJKLMNOPQabcdefghijklmnopq';
$target36 = 'ABCDEFGHIJKLMNOPQRabcdefghijklmnopqr';
$target38 = 'ABCDEFGHIJKLMNOPQRSabcdefghijklmnopqrs';
$target40 = 'ABCDEFGHIJKLMNOPQRSTabcdefghijklmnopqrst';
$target42 = 'ABCDEFGHIJKLMNOPQRSTUabcdefghijklmnopqrstu';
$target44 = 'ABCDEFGHIJKLMNOPQRSTUVabcdefghijklmnopqrstuv';
$target46 = 'ABCDEFGHIJKLMNOPQRSTUVWabcdefghijklmnopqrstuvw';
$target48 = 'ABCDEFGHIJKLMNOPQRSTUVWXabcdefghijklmnopqrstuvwx';
$target50 = 'ABCDEFGHIJKLMNOPQRSTUVWXYabcdefghijklmnopqrstuvwxy';
$target52 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';
/*
SOURCE DECK / TARGET DECK global variables used while stepping through the
operation list tree and enforcing rules.
*/
$src_deck = NULL; // The mixed deck string passed to this script.
$target_deck = NULL; // The unmixed target string (determined using known targets and
// length of mixed deck string passed to this script).
$src_len = NULL; // Length of mixed deck string passed to this script.
$src_len2 = NULL; // Twice length of mixed deck string passed to this script. Used so I
// don't compute this value each time I step through operation list tree.
$src_middle = NULL; //Half the length of the mixed deck. Used to avoid re-computing this number.
$oplists = NULL; // List of list of valid operation steps performed on the original deck
$resultList = NULL; // List of corresponding result decks to the operations in oplists
/**
* Shuffles a deck of cards
*
* Shuffles a deck of cards. 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.
* A SHUFFLE transforms 'ABCDabcd' -> 'aAbBcCdD'. (top card changes)
*
* @author Leon Spencer <mail@leonspencer.com>;
*
* @param string $deck Deck of cards to be shuffled once. The original deck is not modified.
*
* @global integer $src_len Number of cards in the deck.
*
* @global integer $src_middle Half the length of the mixed deck. Used to avoid
* re-computing this number.
*
* @return string A copy of the supplied deck shuffled once.
*/
function shuffle_deck($deck) {
global $src_len;
global $src_middle;
$result_deck = $deck;
for($i=$src_middle,$j=0,$k=0;$i<$src_len;$i++,$j++,$k+=2) {
$result_deck{$k} = $deck{$i};
$result_deck{$k+1} = $deck{$j};
}
return $result_deck;
}
/**
* Cuts a deck of cards
*
* Cuts a deck of cards. A cut is a perfect cut - dividing the deck into two parts and
* exchanging the two halves. A CUT transforms 'ABCDabcd' -> 'abcdABCD'.
*
* @author Leon Spencer <mail@leonspencer.com>;
*
* @param string $deck Deck of cards to be cut once. The original deck is not modified.
*
* @global integer $src_middle Half the length of the mixed deck. Used to avoid
* re-computing this number.
*
* @return string A copy of the supplied deck cut once.
*/
function cut_deck($deck) {
global $src_middle;
$result_deck = substr($deck,$src_middle,$src_middle) . substr($deck,0,$src_middle);
return $result_deck;
}
/**
* Flips a deck of cards
*
* Flips a deck of cards. A flip simply reverses the order of the cards - the bottom card
* becomes the top card and vice-versa (throughout the deck).
* A a FLIP transforms 'ABCDabcd' -> 'dcbaDCBA'.
*
* @author Leon Spencer <mail@leonspencer.com>;
*
* @param string $deck Deck of cards to be flipped once. The original deck is not modified.
*
* @return string A copy of the supplied deck flipped once.
*/
function flip_deck($deck) {
return strrev($deck);
}
/**
* Compares deck to target deck.
*
* @author Leon Spencer <mail@leonspencer.com>;
*
* @param string $deck Deck of cards to perform the specified operation on. The deck is not
* modified.
*
* @global string $target_deck The unmixed deck that is the basis for the comparison.
*
* @return boolean TRUE if specified deck matches targeted deck. Otherwise FALSE.
*/
function reachedTarget($deck) {
global $target_deck;
return ($target_deck == $deck);
}
/**
* Performs possible next steps.
*
* Performs ALL possible next steps then saves result in a global operation lists array.
* The global operations list array contains all valid paths through operations tree. See below.
*
* OPERATION LIST TREE
* S C F
* |-------|------| |---|---| |---|--|
* S C F S F S C
* /|\ /|\ / \ /|\ / \ /|\ / \
* S C F S F S C S C F S C S C F S F
*
* Initially, you able to do either a shuffle, cut, or flip. If you do a cut, your next choices are either
* a shuffle or flip. Consecutive cut operations are not allowed. Note how invalid operations like 'CC'
* and 'FF' are not included in the tree because they put deck back to where you started processing.
* There are other invalid operations. For a list of invalid operations, see the 'RULES OF NEXT STEP'.
*
* Given, the tree above, the operations list array (global $oplists), would contain the following values
* after 3 THREE ITERATIONS with no solution (i.e. the resulting deck does not match the target deck):
* $oplists[0] = 'SSS';
* $oplists[1] = 'SSC';
* $oplists[2] = 'SSF';
* $oplists[3] = 'SCS';
* $oplists[4] = 'SCF';
* $oplists[5] = 'SFS';
* $oplists[6] = 'SFC';
* $oplists[7] = 'CSS';
* $oplists[8] = 'CSC';
* $oplists[9] = 'CSF';
* $oplists[10] = 'CFS';
* $oplists[11] = 'CFC';
* $oplists[12] = 'FSS';
* $oplists[13] = 'FSC';
* $oplists[14] = 'FSF';
* $oplists[15] = 'FCS';
* $oplists[16] = 'FCF';
*
* NOTE: THE TREE AND ARRAY ARE BACKWARDS. During testing I realized the least time expensive operation was
* a FLIP. As a result, the code actual tries a FLIP, CUT, then SHUFFLE. The $oplists array indices should be
* reveresed.
*
* @author Leon Spencer <mail@leonspencer.com>;
*
* @global array $oplists List of all valid paths toward a solution. Paths are not complete. They
* only reflect current steps towards a solution.
*
* @global string $src_deck Original mixed deck passed to this script.
*
* @global integer $src_len Number of cards in the deck.
*
* @global integer $src_len2 Twice the number of cards in the deck. Used to avoid re-computing this
* value each time through loops checking rules #6 and #7 of the 'RULES OF
* NEXT STEP'.
*
* @return boolean TRUE if specified deck matches targeted deck. Otherwise FALSE.
*/
function opTreeNextSteps($start = false) {
global $oplists;
global $resultList;
global $src_deck;
global $src_len;
global $src_len2;
$result_deck;
if($start) {
$oplists = NULL;
$resultList = NULL;
$oplists[] = 'F';
$resultList[] = flip_deck($src_deck);
if(reachedTarget($resultList[0]))
return 'F1';
$oplists[] = 'C';
$resultList[] = cut_deck($src_deck);
if(reachedTarget($resultList[1]))
return 'C1';
$oplists[] = 'S';
$resultList[] = shuffle_deck($src_deck);
if(reachedTarget($resultList[2]))
return 'S1';
return true;
} elseif($oplists) {
$startListCount = count($oplists);
$addAtIndex = $startListCount;
$index = 0;
for($opIndex=0; $opIndex<$startListCount; $opIndex++) {
if(!$oplists[$opIndex])
continue;
$ops = &$oplists[$opIndex];
$op_num = strlen($ops);
$result_deck = $resultList[$opIndex];
switch($ops{$op_num - 1}) {
case 'F':
// Try cut
if($ops{$i-3} != 'F' && $ops{$i-2} != 'C') {
// You can perform a cut
$oplists[$index = $addAtIndex++] = $ops . 'C';
$resultList[$index] = cut_deck($result_deck);
if(reachedTarget($resultList[$index]))
return $oplists[$index] . strlen($oplists[$index]);
}
// Try shuffle
if($op_num + 1 < $src_len + 1) {
// Perform a shuffle
$oplists[$index = $addAtIndex++] = $ops . 'S';
$resultList[$index] = shuffle_deck($result_deck);
if(reachedTarget($resultList[$index]))
return $oplists[$index] . strlen($oplists[$index]);
} else {
// Check for maximum consecutive FS pairs
$fs_count = 0;
// Stop before last operation
$stopIndex = $op_num-2;
for($i=0;$i+1<=$stopIndex;$i+=2) {
if($ops{$i} == 'F' && $ops{$i+1} == 'S')
$fs_count++;
else
break;
}
if($fs_count < ($src_len+1) && $i > $stopIndex) {
// Perform a flip
$oplists[$index = $addAtIndex++] = $ops . 'S';
$resultList[$index] = shuffle_deck($result_deck);
if(reachedTarget($resultList[$index]))
return $oplists[$index] . strlen($oplists[$index]);
}
}
unset($oplists[$opIndex]);
unset($resultList[$opIndex]);
break;
case 'C':
// Try flip
if($ops{$i-3} != 'C' && $ops{$i-2} != 'F') {
// You can perform a flip
$oplists[$index = $addAtIndex++] = $ops . 'F';
$resultList[$index] = flip_deck($result_deck);
if(reachedTarget($resultList[$index]))
return $oplists[$index] . strlen($oplists[$index]);
}
// Try shuffle
if($op_num + 1 < $src_len2) {
// Perform a shuffle
$oplists[$index = $addAtIndex++] = $ops . 'S';
$resultList[$index] = shuffle_deck($result_deck);
if(reachedTarget($resultList[$index]))
return $oplists[$index] . strlen($oplists[$index]);
} else {
// Check for maximum consecutive CS pairs
$cs_count = 0;
// Stop before last operation
$stopIndex = $op_num-2;
for($i=0;$i+1<=$stopIndex;$i+=2) {
if($ops{$i} == 'C' && $ops{$i+1} == 'S')
$cs_count++;
else
break;
}
if($cs_count < $src_len2 && $i > $stopIndex) {
// Perform a flip
$oplists[$index = $addAtIndex++] = $ops . 'S';
$resultList[$index] = shuffle_deck($result_deck);
if(reachedTarget($resultList[$index]))
return $oplists[$index] . strlen($oplists[$index]);
}
}
unset($oplists[$opIndex]);
unset($resultList[$opIndex]);
break;
case 'S':
if($op_num + 1 < $src_len2) {
// Do a cut
$oplists[$index = $addAtIndex++] = $ops . 'C';
$resultList[$index] = cut_deck($result_deck);
if(reachedTarget($resultList[$index]))
return $oplists[$index] . strlen($oplists[$index]);
} else {
// Check for consecutive 'SC' pairs
$sc_count = 0;
// Stop before last operation
$stopIndex = $op_num-2;
for($i=0;$i+1<=$stopIndex;$i+=2) {
if($ops{$i} == 'S' && $ops{$i+1} == 'C')
$sc_count++;
else
break;
}
if($sc_count < $src_len2 && $i > $stopIndex) {
// Perform a cut
$oplists[$index = $addAtIndex++] = $ops . 'C';
$resultList[$index] = cut_deck($result_deck);
if(reachedTarget($resultList[$index]))
return $oplists[$index] . strlen($oplists[$index]);
}
}
if($op_num + 1 < $src_len) {
// Do a flip
$oplists[$index = $addAtIndex++] = $ops . 'F';
$resultList[$index] = flip_deck($result_deck);
if(reachedTarget($resultList[$index]))
return $oplists[$index] . strlen($oplists[$index]);
// Do a shuffle
$oplists[$index = $addAtIndex++] = $ops . 'S';
$resultList[$index] = shuffle_deck($result_deck);
if(reachedTarget($resultList[$index]))
return $oplists[$index] . strlen($oplists[$index]);
} else {
// Check for consecutive 'SF' pairs
$sf_count = 0;
// Stop before last operation
$stopIndex = $op_num-2;
for($i=0;$i+1<=$stopIndex;$i+=2) {
if($ops{$i} == 'S' && $ops{$i+1} == 'F')
$sf_count++;
else
break;
}
if($sf_count < $src_len && $i > $stopIndex) {
// Perform a flip
$oplists[$index = $addAtIndex++] = $ops . 'F';
$resultList[$index] = flip_deck($result_deck);
if(reachedTarget($resultList[$index]))
return $oplists[$index] . strlen($oplists[$index]);
}
// Check for maximum consecutive shuffle count
$ss_count = 1;
for($i=$op_num-2; ($i > 0) && ($ss_count < ($src_len-1)); $i-=2) {
if($ops{$i} == 'S')
$ss_count++;
}
if($ss_count < $src_len-1) {
// You can perform a shuffle
$oplists[$index = $addAtIndex++] = $ops . 'S';
$resultList[$index] = shuffle_deck($result_deck);
if(reachedTarget($resultList[$index]))
return $oplists[$index] . strlen($oplists[$index]);
}
}
unset($oplists[$opIndex]);
unset($resultList[$opIndex]);
break;
}
}
// Re-index Array because we removed values
$oplists = array_values($oplists);
$resultList = array_values($resultList);
if($oplists)
return true;
else
return false;
} else {
return false;
}
}
/**
* Main Function
*
* Main Function. Loads a deck from a local 'deck.txt' file them attempts to find a solution.
*
* @author Leon Spencer <mail@leonspencer.com>;
*
* @global string $target_deck The unmixed deck that is the basis for the comparison.
*
* @return void This function will fail if a 'deck.txt' with at a valid deck appearing on the
* first line is NOT present.
*/
function main() {
global $src_deck;
global $target_deck;
global $src_len;
global $src_len2;
global $src_middle;
global $target2;
global $target4;
global $target6;
global $target8;
global $target10;
global $target12;
global $target14;
global $target16;
global $target18;
global $target20;
global $target22;
global $target24;
global $target26;
global $target28;
global $target30;
global $target32;
global $target34;
global $target36;
global $target38;
global $target40;
global $target42;
global $target44;
global $target46;
global $target48;
global $target50;
global $target52;
$decks = file('deck.txt');
$src_deck = trim($decks[0]);
$src_len = strlen($src_deck);
$src_len2 = 2 * $src_len;
$src_middle = (int)($src_len / 2);
$target_deck = ${'target' . $src_len};
$result = opTreeNextSteps(true);
while($result === true) {
$result = opTreeNextSteps();
}
if(is_string($result)) {
print "$result";
} else {
print "NO SOLUTION!";
}
}
main();
?>
Back to results
|
|
|
