Main Menu |
|
|
 |
Forums |
|
|
|
Programming
Contest |
| |
|
Documentation
|
| |
|
Partner
Sites |
|
|
Sponsors |
|
|
|
|
Code of michael
<!doctype html public "-//W3C//DTD HTML 4.0 //EN">
<html>
<head>
<title>theBrute</title>
</head>
<body>
<?php
/* PHP Cut, Shuffle, and Flip Contest
Michael Miller (aka the_jabber_wock)
michaelmiller1@hotmail.com
Build Platform: Windows2000 / English
CPU: 600Mhz Pentium3,256Megs
PHP4.2.1
Run instructions: Place a 'deck.txt' file in the same directory as the scipt
and it should go smoothly
*/
/* Information about the program:
This program attempts to order the cards in a deck back to the original
order, 'A-Za-z'. The deck.txt file contains a shuffled deck. The program
outputs a string of the three types of moves shuffle ('S'), cut ('C') or
flip ('F'), which when applied to the deck return the deck to it's original
order, or if it can't, the set of moves which get the most number of cards
in the correct positions
*/
/* Not quite optimal yet but it currently gets the best move string for all decks
upto length about 33 on my machine. For longer sets of moves the program will try
to get a non-optimal move string using a semi-random walk. Though ineffective at getting
an optimal movestring it will usually get a movestring that solves the problem.
*/
/* Great contest question. Such a deceptively simple search but seems to be unpredictable
in every way. Shall be interesting to see what other people come up with
*/
// things to do still:
// Keep better track of all the strings that score well and use them to make sure
// it creates strings that score the same or higher
// save the moves in a different format so when looking them up for above the program
// doesn't have to traverse the tree. Maybe some sort of bit packing method
function getmicrotime()
{
list($usec, $sec) = explode(" ",microtime());
return ((float)$usec + (float)$sec);
}
function ConvertToInternalFormat($aDeck)
{
//converts a deck string into the internal format we are using
$tempChar = "a";
$deckLen = strlen($aDeck);
$convertChar = chr(ord("a") + ($deckLen/2) - 1);
$newDeck = $aDeck;
for($i = 0; $i < $deckLen; $i++)
{
for($j = 0; $j < $deckLen; $j++)
{
if($tempChar == $newDeck{$j})
{
$aDeck{$j} = $convertChar;
$convertChar = chr(ord($convertChar) -1);
break;
}
}
$tempChar++;
}
return substr($aDeck,0,$deckLen/2);
}
function TakeFileInput($filename)
{
//first up grab the information from the file
if(($fp = fopen ("deck.txt", "r")) == FALSE)
{
echo "Can't Open file deck.txt";
exit();
}
$buffer = "";
while (!feof ($fp)) {
$buffer .= fgets($fp, 4096);
}
$aDeck = trim($buffer);
fclose($fp);
//then convert it to the internal format we are using
$aDeck = ConvertToInternalFormat($aDeck);
return($aDeck);
}
function CutDeck ($deck, $deckLen)
{
//cuts a deck
//does this by flipping the deck and changing the cases of all the
$deck = strrev($deck);
for($i = 0; $i < $deckLen; $i++)
{
$deck{$i} = chr(ord($deck{$i}) ^ 0x20);
}
return $deck;
}
function FlipDeck ($deck, $deckLen)
{
//flips the deck by changing the case of all the letters
$tempChar = 'a';
for ($i = 0; $i < $deckLen; $i++)
{
$deck{$i} = chr(ord($deck{$i}) ^ 0x20);
}
return $deck;
}
function ShuffleDeck($deck, $deckLen)
{
//shuffles the deck
//does this by moving the first deckLen/2 charaters to positions 2i+1
//and takes deckLen to deckLen/2 character to positions 2i while changing
//their cases
$tempDeck = $deck;
for ($i = 1,$j = 0; $i < $deckLen; $i+=2, $j++)
{
$deck{$i} = $tempDeck{$j};
}
for ($i = 0, $j = $deckLen-1; $i < $deckLen; $i+=2, $j--)
{
$deck{$i} = chr(ord($tempDeck{$j}) ^ 0x20);
}
return $deck;
}
function ReverseShuffleDeck($deck, $deckLen)
{
//do a reverse shuffle on the deck
$tempDeck = $deck;
//first move the values which do not change case
for ($i = 0, $j=1; $j < $deckLen; $j+=2, $i++)
{
$deck{$i} = $tempDeck{$j};
}
//now move and change the case of the others
for ($i = $deckLen-1, $j = 0; $j < $deckLen; $i--, $j+=2)
{
$deck{$i} = chr(ord($tempDeck{$j}) ^ 0x20);
}
return $deck;
}
function CreateADeck($lengthOfDeck)
{
//create the goal that we are aiming for
$goal = "";
$tempChar = 'A';
for ($i = 0; $i < $lengthOfDeck; $i++)
{
$goal = $goal . $tempChar;
$tempChar++;
}
return($goal);
}
function Score($deck, $goal, $deckLen)
{
//scores the deck against the goal by counting the number of cards
//in the correct place
$score = 0;
for ($i = 0; $i < $deckLen; $i++)
{
if($deck{$i} == $goal{$i})
$score++;
}
return $score;
}
function Apply($deck, $lengthOfDeck, $arrayOfMoves, $i, $arrayOfParents)
{
while ($arrayOfParents[$i] != -1)
{
if($arrayOfMoves{$i} == "S")
{
$deck = ShuffleDeck($deck, $lengthOfDeck);
}
else if($arrayOfMoves{$i} == "C")
{
$deck = CutDeck($deck, $lengthOfDeck);
}
else if($arrayOfMoves{$i} == "F")
{
$deck = FlipDeck($deck, $lengthOfDeck);
}
$i = $arrayOfParents[$i];
}
return $deck;
}
function MeetInMiddleBruteForce($deck)
//does a brute force breadth first search from the top and bottom with a
//meet-in-the middle approach
{
//here we do take a few liberties
//we have identities
//FF = CC = I
//We can only do a certain number of S in a row before we return to the
//original array so only do that number in a row
$time = getmicrotime();
$deckLen = strlen($deck);
$goal = CreateADeck($deckLen);
//first count how many shuffles it takes to get back to the original
$numPerfectShuffles = 0;
$tempDeck = $goal;
do
{
$tempDeck = ShuffleDeck($tempDeck,$deckLen);
$numPerfectShuffles++;
} while ($goal != $tempDeck);
//check if nothing was done to the deck
if($deck == $goal)
{
return '0';
}
//check if the deck was flipped only
if (FlipDeck($deck,$deckLen) == $goal)
{
return 'F1';
}
//look up tables to speed searching
//stores the address of the child in the deck array
//using the first three cards of the deck
$fC = 'a';
for ($a = 0; $a < $deckLen; $a++)
{
$sC = 'a';
for($b = 0; $b < $deckLen; $b++)
{
$tC = 'a';
for($c = 0; $c < $deckLen; $c++)
{
$bottomLookUpTable[$fC][$sC][$tC] = -1;
$tC++;
}
$tC = 'A';
for($c = 0; $c < $deckLen; $c++)
{
$bottomLookUpTable[$fC][$sC][$tC] = -1;
$tC++;
}
$sC++;
}
$sC = 'A';
for($b = 0; $b < $deckLen; $b++)
{
$tC = 'a';
for($c = 0; $c < $deckLen; $c++)
{
$bottomLookUpTable[$fC][$sC][$tC] = -1;
$tC++;
}
$tC = 'A';
for($c = 0; $c < $deckLen; $c++)
{
$bottomLookUpTable[$fC][$sC][$tC] = -1;
$tC++;
}
$sC++;
}
$fC++;
}
$fC = 'A';
for ($a = 0; $a < $deckLen; $a++)
{
$sC = 'a';
for($b = 0; $b < $deckLen; $b++)
{
$tC = 'a';
for($c = 0; $c < $deckLen; $c++)
{
$bottomLookUpTable[$fC][$sC][$tC] = -1;
$tC++;
}
$tC = 'A';
for($c = 0; $c < $deckLen; $c++)
{
$bottomLookUpTable[$fC][$sC][$tC] = -1;
$tC++;
}
$sC++;
}
$sC = 'A';
for($b = 0; $b < $deckLen; $b++)
{
$tC = 'a';
for($c = 0; $c < $deckLen; $c++)
{
$bottomLookUpTable[$fC][$sC][$tC] = -1;
$tC++;
}
$tC = 'A';
for($c = 0; $c < $deckLen; $c++)
{
$bottomLookUpTable[$fC][$sC][$tC] = -1;
$tC++;
}
$sC++;
}
$fC++;
}
//set up the top of the tree
$arrayOfDecks[0] = $deck; //root
$arrayOfMoves{0} = ''; //type of move to get to it
$arrayOfParents[0] = -1; //the number of the parent of this node
//setupthe bottom of the tree
$bottomArrayOfDecks[0] = $goal;
$bottomArrayOfMoves{0} = '';
$bottomArrayOfParents[0] = -1;
$fC = $goal{0};
$sC = $goal{1};
$tC = $goal{2};
$cV = 0;
$nD = -1;
$bottomLookUpTable[$fC][$sC][$tC]++;
$bottomLookUpTableValues[$fC][$sC][$tC][0] = 0;
$bottomParentNode = 0;
$bottomChildNode = 1;
$bottomStartOfLevelCounter = 0;
$bottomEndOfLevelCounter = 0;
$parentNode = 0;
$childNode = 1;
$numberInCurrentLevel = 1;
$startOfLevelCounter = 0;
$endOfLevelCounter = 0; //when do we move to the next level
$Done = FALSE;
$bestScore = -1;
$bestNode = 0;
$bestBottomNode = 0;
$aScore = 0;
$tempDeck = $goal;
while (1)
{
//First do the top of the array
//do a cut
if ($arrayOfMoves{$parentNode} != 'C')
{
$arrayOfDecks[$childNode] = CutDeck($arrayOfDecks[$parentNode],$deckLen);
if(strcmp($arrayOfDecks[$childNode],$arrayOfDecks[0]) == 0
|| 0 == strcmp($arrayOfDecks[$childNode],FlipDeck($arrayOfDecks[0],$deckLen)))
{
$childNode--; //erase this node
}
else
{
//otherwise add the info about this node
$arrayOfMoves{$childNode} = 'C';
$arrayOfParents[$childNode] = $parentNode;
$aScore = score($arrayOfDecks[$childNode], $goal, $deckLen);
if($aScore > $bestScore)
{
$bestNode = $childNode;
$bestScore = $aScore;
}
//check if we are done
//check all the leaves of the bottom tree
$fC = $arrayOfDecks[$childNode]{0};
$sC = $arrayOfDecks[$childNode]{1};
$tC = $arrayOfDecks[$childNode]{2};
$nD = $bottomLookUpTable[$fC][$sC][$tC];
for ($j = 0; $j <= $nD; $j++)
{
$cV = $bottomLookUpTableValues[$fC][$sC][$tC][$j];
if(0 == strcmp($arrayOfDecks[$childNode], $bottomArrayOfDecks[$cV]))
{
$Done = TRUE;
break;
}
}
if($Done == TRUE)
{
$bottomChildNode = $cV;
break;
}
//check for the flipped version too
$tempDeck = FlipDeck($arrayOfDecks[$childNode],$deckLen);
$fC = $tempDeck{0};
$sC = $tempDeck{1};
$tC = $tempDeck{2};
$nD = $bottomLookUpTable[$fC][$sC][$tC];
for ($j = 0; $j <= $nD; $j++)
{
$cV = $bottomLookUpTableValues[$fC][$sC][$tC][$j];
if(0 == strcmp($tempDeck ,$bottomArrayOfDecks[$cV]))
{
$childNode++;
$arrayOfMoves{$childNode} = 'F';
$arrayOfParents[$childNode] = $childNode-1;
$Done = TRUE;
break;
}
}
if($Done == TRUE)
{
$bottomChildNode = $cV;
break;
}
$childNode++;
}
}
//do a shuffle
$arrayOfDecks[$childNode] = ShuffleDeck($arrayOfDecks[$parentNode],$deckLen);
//check if we are duplicating any other nodes
if(0 == strcmp($arrayOfDecks[$childNode], $arrayOfDecks[0])
|| 0 == strcmp($arrayOfDecks[$childNode], FlipDeck($arrayOfDecks[0],$deckLen)))
{
$childNode--; //erase this node
}
else
{
//add the info about this node
$arrayOfMoves{$childNode} = 'S';
$arrayOfParents[$childNode] = $parentNode;
$aScore = score($arrayOfDecks[$childNode], $goal, $deckLen);
if($aScore > $bestScore)
{
$bestNode = $childNode;
$bestScore = $aScore;
}
//check if we are done
//check all the leaves of the bottom tree
$fC = $arrayOfDecks[$childNode]{0};
$sC = $arrayOfDecks[$childNode]{1};
$tC = $arrayOfDecks[$childNode]{2};
$nD = $bottomLookUpTable[$fC][$sC][$tC];
for ($j = 0; $j <= $nD; $j++)
{
$cV = $bottomLookUpTableValues[$fC][$sC][$tC][$j];
if(0 == strcmp($arrayOfDecks[$childNode], $bottomArrayOfDecks[$cV]))
{
$Done = TRUE;
break;
}
}
if($Done == TRUE)
{
$bottomChildNode = $cV;
break;
}
//check if the flip is in the table too
$tempDeck = FlipDeck($arrayOfDecks[$childNode],$deckLen);
$fC = $tempDeck{0};
$sC = $tempDeck{1};
$tC = $tempDeck{2};
$nD = $bottomLookUpTable[$fC][$sC][$tC];
for ($j = 0; $j <= $nD; $j++)
{
$cV = $bottomLookUpTableValues[$fC][$sC][$tC][$j];
if (0 == strcmp($tempDeck, $bottomArrayOfDecks[$cV]))
{
$childNode++;
$arrayOfMoves{$childNode} = 'F';
$arrayOfParents[$childNode] = $childNode-1;
$Done = TRUE;
break;
}
}
if($Done == TRUE)
{
$bottomChildNode = $cV;
break;
}
$childNode++;
}
$parentNode++;
//check if we are on the next level of the tree
if($parentNode > $endOfLevelCounter)
{
$startOfLevelCounter=$endOfLevelCounter+1;
$endOfLevelCounter=$childNode-1;
}
//////////////////////////////////////////////////////////////////
// now onto the bottom half of the deck
//do a cut on the bottom half
if ($bottomArrayOfMoves{$bottomParentNode} != 'C')
{
$bottomArrayOfDecks[$bottomChildNode] = CutDeck($bottomArrayOfDecks[$bottomParentNode],$deckLen);
//otherwise add the info about this node
$bottomArrayOfMoves{$bottomChildNode} = 'C';
$bottomArrayOfParents[$bottomChildNode] = $bottomParentNode;
//set the values in the lookup table
$fC = $bottomArrayOfDecks[$bottomChildNode]{0};
$sC = $bottomArrayOfDecks[$bottomChildNode]{1};
$tC = $bottomArrayOfDecks[$bottomChildNode]{2};
//check for duplicates and delete if necceissary
$duplicate = FALSE;
$nD = $bottomLookUpTable[$fC][$sC][$tC];
for ($g = 0; $g <= $nD; $g++)
{
$cV = $bottomLookUpTableValues[$fC][$sC][$tC][$g];
if(0 == strcmp($bottomArrayOfDecks[$cV], $bottomArrayOfDecks[$bottomChildNode]))
{
$duplicate = TRUE;
break;
}
}
if($duplicate == FALSE)
{
$bottomLookUpTable[$fC][$sC][$tC]++;
$bottomLookUpTableValues[$fC][$sC][$tC][$bottomLookUpTable[$fC][$sC][$tC]] = $bottomChildNode;
}
//we need to do a reverse lookup to be totally complete and catch solutions on the first
//try but if not it will always get it when the top generates another value
$bottomChildNode++;
}
//do a reverse shuffle on the bottom half of the deck
$bottomArrayOfDecks[$bottomChildNode] = ReverseShuffleDeck($bottomArrayOfDecks[$bottomParentNode],$deckLen);
//add the info about this node
$bottomArrayOfMoves{$bottomChildNode} = 'S';
$bottomArrayOfParents[$bottomChildNode] = $bottomParentNode;
//set the values in the lookup table
$fC = $bottomArrayOfDecks[$bottomChildNode]{0};
$sC = $bottomArrayOfDecks[$bottomChildNode]{1};
$tC = $bottomArrayOfDecks[$bottomChildNode]{2};
$nD = $bottomLookUpTable[$fC][$sC][$tC];
//check for duplicates and delete if necceissary
$duplicate = FALSE;
for ($g = 0; $g <= $nD; $g++)
{
$cV = $bottomLookUpTableValues[$fC][$sC][$tC][$g];
if(0 == strcmp($bottomArrayOfDecks[$cV], $bottomArrayOfDecks[$bottomChildNode]))
{
$duplicate = TRUE;
break;
}
}
if($duplicate == FALSE)
{
$bottomLookUpTable[$fC][$sC][$tC]++;
$bottomLookUpTableValues[$fC][$sC][$tC][$bottomLookUpTable[$fC][$sC][$tC]] = $bottomChildNode;
}
$bottomChildNode++;
$bottomParentNode++;
//check if we are on the next level of the tree
if($bottomParentNode > $bottomEndOfLevelCounter)
{
$bottomStartOfLevelCounter=$bottomEndOfLevelCounter+1;
$bottomEndOfLevelCounter=$bottomChildNode-1;
}
//check how long we've taken
//and collect the best solution and quit if we are close to 60 seconds
//this should be improved to aim for better scores
//it's random at the moment so the movestrings become very long and non optimal
//the cheep idea is to randomly walk until we hit the target of the bottom tree
//that we created
//this could be optimized by using the lookuptable to only do moves which
//don't mess up the order of the cards that are already in order
if((getmicrotime() - $time) >= 42)
{
$storedChildNode = $childNode - 2;
$moveLength = 0;
$parentNode = $childNode-1;
$percentS = rand(1,$numPerfectShuffles-1);
$numShufflesInARow = 0;
$maxMoveLength = 300;
//try to move forwards randomly until we hit the bottom tree
while((getmicrotime() - $time) < 52)
{
//randomly generate a move from the child
if((rand(0,$percentS) == 0 && $arrayOfMoves[$parentNode] != 'C') || $numShufflesInARow >= $numPerfectShuffles)
{
$arrayOfDecks[$childNode] = CutDeck($arrayOfDecks[$parentNode],$deckLen);
$arrayOfMoves{$childNode} = 'C';
$numShufflesInARow = 0;
}
else
{
$arrayOfDecks[$childNode] = ShuffleDeck($arrayOfDecks[$parentNode],$deckLen);
$arrayOfMoves{$childNode} = 'S';
$numShufflesInARow++;
}
$arrayOfParents[$childNode] = $parentNode;
$aScore = score($arrayOfDecks[$childNode], $goal, $deckLen);
if($aScore > $bestScore)
{
$bestNode = $childNode;
$bestScore = $aScore;
}
//now check if we've hit the bottom
$fC = $arrayOfDecks[$childNode]{0};
$sC = $arrayOfDecks[$childNode]{1};
$tC = $arrayOfDecks[$childNode]{2};
$nD = $bottomLookUpTable[$fC][$sC][$tC];
for ($j = 0; $j <= $nD; $j++)
{
$cV = $bottomLookUpTableValues[$fC][$sC][$tC][$j];
if(0 == strcmp($arrayOfDecks[$childNode], $bottomArrayOfDecks[$cV]))
{
$Done = TRUE;
break;
}
}
if($Done == TRUE)
{
$bottomChildNode = $cV;
break;
}
//check for the flipped version as well;
$tempDeck = FlipDeck($arrayOfDecks[$childNode],$deckLen);
$fC = $tempDeck{0};
$sC = $tempDeck{1};
$tC = $tempDeck{2};
$nD = $bottomLookUpTable[$fC][$sC][$tC];
for ($j = 0; $j <= $nD; $j++)
{
$cV = $bottomLookUpTableValues[$fC][$sC][$tC][$j];
if (0 == strcmp($tempDeck, $bottomArrayOfDecks[$cV]))
{
$childNode++;
$arrayOfMoves{$childNode} = 'F';
$arrayOfParents[$childNode] = $childNode-1;
$Done = TRUE;
break;
}
}
if($Done == TRUE)
{
$bottomChildNode = $cV;
break;
}
if($storedChildNode == $parentNode)
{
$parentNode = $childNode;
}
else
{
$parentNode++;
}
$childNode++;
//assume that the movestring will be under 300 or so in length
$moveLength++;
if($moveLength > $maxMoveLength)
{
//$if so reset the start of our random walk and create some more nodes
$storedChildNode--;
$parentNode = $storedChildNode;
$moveLength = 0;
$percentS = rand(1,$numPerfectShuffles-1);
}
}
if($Done == TRUE)
{
break;
}
else
{
$childNode = $bestNode;
$bottomChildNode = $bestBottomNode;
break;
}
}
}
//now create the string of how we got to the goal
//walk the tree
$currentNode = $childNode;
$outputString = "";
$numberOfMoves = 0;
while($arrayOfParents[$currentNode] != -1)
{
$outputString = $outputString.$arrayOfMoves[$currentNode];
$numberOfMoves++;
$currentNode = $arrayOfParents[$currentNode];
}
$outputString = strrev($outputString);
//now walk the bottom half tree
$currentNode = $bottomChildNode;
$bottomOutputString = "";
while($bottomArrayOfParents[$currentNode] != -1)
{
$bottomOutputString = $bottomOutputString.$bottomArrayOfMoves[$currentNode];
$numberOfMoves++;
$currentNode = $bottomArrayOfParents[$currentNode];
}
return $outputString.$bottomOutputString.$numberOfMoves;;
}
//The main function of the script start running everything
$aDeck = TakeFileInput("deck.txt");
echo MeetInMiddleBruteForce($aDeck);
?>
</body>
</html>
Back to results
|
|
|
