Code of daniel
<?
/**
* I hope I understud the requirements, and then
* deck.txt is working on this
*
* The Idea: Using Recursive Programming and
* walk down the Tree, in direktion at the same
* time. Little Array-Cache for Stack, because
* this is not a real recursive-Language
* Skip already Tested Decks which boosts the
* app quite a lot.
* Detect Loops in Way and dont test this branch.
* have optimization with "CSS", but this adds a little
* risk, but most test-decks are solved with this
* if this $fasttry is off, then no risk but slower
* the DTj... is too slow then.
*
* somebody might write faster code ;)
* But Hey, why do I have Zend and lots of CPU ;)
*
* Daniel Unterberger (2003-04-08)
*/
/**
* Read in decks to Process.
*/
set_time_limit(60);
$deck= trim( join( "", file( "./deck.txt" ) ) );
### Have some Testdecks which work
#$deck="bfDaeCdBFcAE";
#$deck="bjBJaiAIdlDLckCKfnFNemEMhpHPgoGO";
#$deck="nTyhNsYzeKtZEfLqWFkQrXClRwDiOxcIjPudJoUvaGpVAbHmSBgM";
#$deck="IynUJzwlaPxmbtiXEujgVKshWLodSHpeTQFvcRGYNCkZODAqfMBr";
#$deck='AcCeJgbidEfGBIDaFhHj';
#$deck='DfabCEgAceFGBd';
#$deck="zrjbTLDumeWOGxphZRJBskcUMEvnfXPHyqiaSKCtldVNFwogYQIA";
#$deck='DTjzpGWmcsJZPfvMCSiyoFVlbrIYOeuLBRhxnEUkaqHXNdtKAQgw';
#$deck='MyIubtkpwifQXdTmSEOAHZqVCoLxeJaszlvhNgWcjURDKPGYFrBn';
#clear some values
$start_deck=$deck;
$half =strlen($start_deck)/2;
$result ="";
#set this to 0 if the result is too long or no match
$fasttry=1;
$fill=$start_deck;
$deck=$start_deck;
$tested =Array();
$loops =Array();
$full_loops =Array();
$test ="";
$test2 ="";
$work_point =0;
#combination of CS is more likely so we guess around FCSCSCSCS..
$moves[1] =Array( "F", "S", "C" );
$moves[2] =Array( "C", "S" );
$moves[3] =Array( "S", "C" );
$moveswap=1;
$decks =Array();
$ways =Array();
#calculate the good-deck
for ($i=0;$i<$half and $result==""; $i++)
{
$test1 .=chr( 65+$i );
$test2 .=chr( 97+$i );
}
$test =$test1 . $test2;
#initialize
$ways [1]="";
$decks[1]= $deck ;
$tested[$deck]= "-root-";
$res_len=0;
#can speed up with this LOOPS, but then some will
#conflict with the CSS-Trick
#
#$loops[]="FF";
#$loops[]="CC";
#show a numer if way-length is next level
# if ( strlen($way) >$res_len ) { print ( $res_len=strlen($way) ) . "( $loop_killer ) $way \n"; }
$loop_killer=0;
while( $result=="" and $loop_killer++<1000000 )
{
# get next work task.
$work_point++;
$way = $ways [$work_point];
$deck = $decks[$work_point];
if ($deck=="")
{
#tried all way but no result
#perhaps to much speed-optimizers
die( "not found");
}
foreach( $moves[$moveswap] as $move )
{
$waymove=$way.$move;
if ( way_has_loop() == false )
{
$move( ); #breaks if test is valid, hit->exit
# see if we already have the mod_deck-combination , then try to detect the
# loop pattern
if ( $loop_killer>1 and ($old_way= $tested[ $mod_deck ])!="" )
{
#debug: print "\nhit, we already had deck: ".strlen( $mod_deck )." $mod_deck way: ".$tested[ $mod_deck ] . " loop( ". $way.$move ." )";
if( strpos( $waymove , $old_way ) > 0 )
{
# print "\nsub ";
$loops[] = substr( $waymove , strlen( $old_way ) );
}
elseif( $old_way=='-root-' )
{
# print "\n begining from start :: " .$waymove;
$full_loops[]=$waymove;
}
#detect loop pattern here....
}
else
{
# indicate iterator
# if ($u++ > 1000) { print ",". $u2++; $u=0; flush(); }
#add new deck to tested, so we can find it later as a loop
$tested[ $mod_deck ]=$waymove;
#could not find loopstring, so add it to decks[]
$ways []=$waymove;
$decks[]=$mod_deck;
}
}
}
if ($moveswap==2)
{
$moveswap=3;
}
else
{
$moveswap=2;
}
#$moveswap=2;
#$moves[2]=array_reverse( $moves[2] );
#There can only be one F in the string, because FF is a mirror-function!
#it is not important, where the next F is, they delete themselves,
#so we only test combinations of S and C which works good
}
print "\n". $result . strlen($result);
# !!! Uncomment next 3 code-lines to se a nice looking result (proof)
#
# print "\n\nneeded iterations:".$loop_killer ."\n";
# include "./cards.php";
# $x=new Deck( $start_deck , $result );
############################ some helpers...
function S()
{
global $deck, $test,$fill, $mod_deck, $half, $result, $way, $move;
$mod_deck=$fill;
for ( $i=0; $i<$half; $i++)
{
$mod_deck{ 2*$i }= $deck{$i+$half};
$mod_deck{ 2*$i+1}= $deck{$i };
}
if ( ($mod_deck)==$test )
{
$result=$way.$move;
}
}
function F()
{
global $deck, $test,$fill, $mod_deck, $half, $result, $way, $move;
$mod_deck= strrev( $deck );
if ( ($mod_deck)==$test )
{
$result=$way.$move;
}
}
function C()
{
global $deck, $test,$fill, $mod_deck, $half, $result, $way, $move;
$mod_deck= substr( $deck, $half )
. substr( $deck, 0 ,$half );
if ( ($mod_deck)==$test )
{
$result=$way.$move;
}
}
function way_has_loop()
{
global $loops, $full_loops, $way, $move, $fasttry;
$waymove=$way.$move;
#test if we have a loop in the way of next move
foreach ( $loops as $loop )
{
# if loop is in way then dont use this branch!
if ( preg_match( "/$loop\$/", $waymove ) )
{
return true;
}
if ( $fasttry==1 and ( substr_count( $waymove, "CSS" ) >1 and !preg_match( "/CSS$/", $waymove ) ) )
{
return true;
}
}
foreach ( $full_loops as $loop )
{
# the way contains a loop which ends at start_deck, so it is tested elsewhere.
if ( preg_match( "/$loop/", $waymove ) )
{
return true;
}
}
return false;
}
?>
Back to results
|
|
