Main Menu |
|
|
 |
Forums |
|
|
|
Programming
Contest |
| |
|
Documentation
|
| |
|
Partner
Sites |
|
|
Sponsors |
|
|
|
|
Code of wayne
<?
define("MAX_SECONDS_RUN",54); //allow for approx. 6 seconds of overhead
$startTime = time();
include('deck.class.php');
$deckFileName = "deck.txt";
$fp = fopen($deckFileName,"r");
if (!$fp) die("$deckFileName can not be opened for reading");
$deck = array();
//priming read
$character = fread($fp,1);
while ( !feof($fp) && $character >= 'A' && $character <= 'z' ) {
$cards[] = $character;
$character = fread($fp,1);
}
fclose($fp);
$sortedCards = $cards;
sort($sortedCards);
$rslt = dostuff($cards);
echo $rslt . strlen($rslt);
function dostuff($cards) {
global $startTime;
$numCardsInDeck = count($cards);
$highestScore = scoreDeck($cards);
$highestScoreOperations = "";
if ($highestScore == $numCardsInDeck) {
return $highestScoreOperations;
}
$i = 0;
$x[$i]['deck'] = deckShuffle($cards);
$x[$i]['ops'] = 'S';
$tmpScore = scoreDeck($x[$i]['deck']);
if ($tmpScore > $highestScore) {
$highestScore = $tmpScore;
$highestScoreOperations = $x[$i]['ops'];
if ($highestScore == $numCardsInDeck) {
return $highestScoreOperations;
}
}
$i++;
$x[$i]['deck'] = deckCut($cards);
$x[$i]['ops'] = 'C';
$tmpScore = scoreDeck($x[$i]['deck']);
if ($tmpScore > $highestScore) {
$highestScore = $tmpScore;
$highestScoreOperations = $x[$i]['ops'];
if ($highestScore == $numCardsInDeck) {
return $highestScoreOperations;
}
}
$i++;
$x[$i]['deck'] = deckFlip($cards);
$x[$i]['ops'] = 'F';
$tmpScore = scoreDeck($x[$i]['deck']);
if ($tmpScore > $highestScore) {
$highestScore = $tmpScore;
$highestScoreOperations = $x[$i]['ops'];
if ($highestScore == $numCardsInDeck) {
return $highestScoreOperations;
}
}
$i++;
$y = array();
$numIterations = 0;
$lastElTime = -1;
$elapsedTime = time() - $startTime;
while ($elapsedTime < (MAX_SECONDS_RUN)) {
$numIterations++;
$numDecks = count($x);
$j = 0;
for ($i = 0; $i < $numDecks && ($elapsedTime < (MAX_SECONDS_RUN)); $i++) {
//two cuts in a row produces the original deck, so if the
// last operation was a cut we only do a shuffle
$lastOp = substr($x[$i]['ops'],-1,1);
if ($lastOp == 'S' || $lastOp == 'F') {
$y[$j]['deck'] = deckShuffle($x[$i]['deck']);
$y[$j]['ops'] = $x[$i]['ops'] . 'S';
$tmpScore = scoreDeck($y[$j]['deck']);
if ($tmpScore > $highestScore) {
$highestScore = $tmpScore;
$highestScoreOperations = $y[$j]['ops'];
if ($highestScore == $numCardsInDeck) {
return $highestScoreOperations;
}
}
$j++;
$y[$j]['deck'] = deckCut($x[$i]['deck']);
$y[$j]['ops'] = $x[$i]['ops'] . 'C';
$tmpScore = scoreDeck($y[$j]['deck']);
if ($tmpScore > $highestScore) {
$highestScore = $tmpScore;
$highestScoreOperations = $y[$j]['ops'];
if ($highestScore == $numCardsInDeck) {
return $highestScoreOperations;
}
}
$j++;
} else {
$y[$j]['deck'] = deckShuffle($x[$i]['deck']);
$y[$j]['ops'] = $x[$i]['ops'] . 'S';
$tmpScore = scoreDeck($y[$j]['deck']);
if ($tmpScore > $highestScore) {
$highestScore = $tmpScore;
$highestScoreOperations = $y[$j]['ops'];
if ($highestScore == $numCardsInDeck) {
return $highestScoreOperations;
}
}
$j++;
}
$elapsedTime = time() - $startTime;
}
$x = $y;
}
//I found that adding these two lines shaved approximately 3 seconds off the total run time
unset($x);
unset($y);
return $highestScoreOperations;
}
function deckFlip($cards) {
return array_reverse($cards);
}
function deckCut($cards) {
$arrayHalfIndex = count($cards) / 2;
$half1 = array_slice($cards,0,$arrayHalfIndex);
$half2 = array_slice($cards,$arrayHalfIndex);
return array_merge($half2,$half1);
}
function deckShuffle($cards) {
$shuffledDeck = array();
$deckSize = count($cards);
for ($i = 0; $i < ($deckSize/2); $i++) {
$shuffledDeck[] = $cards[$i+($deckSize/2)];
$shuffledDeck[] = $cards[$i];
}
return $shuffledDeck;
}
function scoreDeck($cards) {
$score = 0;
for ($i = 0; $i < count($cards); $i++) {
if ($cards[$i] == $GLOBALS['sortedCards'][$i]) {
$score++;
}
}
return $score;
}
?>
Back to results
|
|
|
