Main Menu |
|
|
 |
Forums |
|
|
|
Programming
Contest |
| |
|
Documentation
|
| |
|
Partner
Sites |
|
|
Sponsors |
|
|
|
|
Code of alan
<?php
//////////////////////////////////////////////////////////////////////
//
// cards.php - proposed solution to PHP contest at
// https://www.php-editors.com/contest_b_1.htm
//
// by Alan Krueger (alan_krueger@g1.com) of Group 1 Software
// written 4/2003
//
// For submission, this has been trimmed of diagnostics and alternate
// search algorithms. At one point, this was doing both a breadth-
// first search and a depth-first search. It first tried the BFS
// optimistically for part of the timeout period and dropped down to
// do a DFS (actually an iterative-deepening DFS, since I assume these
// sequences can be indefinitely long and we don't want it to search
// forever...) The DFS has been clipped out because it really only
// added something to the processing of this when we have a total
// timeout of around 120s. In 60s, the BFS seems to work well enough.
//
// The BFS is guaranteed to eventually find a solution with the
// smallest length, since it tries all sequences of increasing length.
//
// This uses the optimization that only one "F" is needed (more than
// once cancel each other out in pairs) and their position appears
// unimportant. Thus, we check for a result and compute scores based
// on both the desired arrangement and its flip. If it matches the
// latter, an "F" is tacked onto the current sequence. Thus, it's
// possible that there could be a solution of sequence length N and
// the search will find an N+1 solution first, ending in "F".
//
//////////////////////////////////////////////////////////////////////
$cards = array_reduce( file( "deck.txt" ), "trimAndAppend", "" );
$numcards = strlen( $cards );
$half = $numcards / 2;
$maxSeqLength = 300;
$maxDictSeqLength = 1;
$desired = getDesiredCards( $numcards );
$desiredFlip = myFlip( $desired );
// apparently, the cut and shuffle operations
// are invariant over flip, so we don't generate
// flipped trials, we simply test for either
// the desired string or the flipped desired string
$start = time();
$totalTimeout = ini_get( "max_execution_time" );
if ( $totalTimeout <= 0 ) $totalTimeout = 60;
$totalTimeout = $totalTimeout - 5; // give us some leeway, just in case
// track these to further prune the search space
$identities = array();
$flips = array();
//
// Breadth-First Search
//
$timeout = $totalTimeout;
$result = computeResultBFS( $cards );
$verified = verifyResult( $cards, $result );
//
// Done
//
if ( $result != "" )
echo $result.strlen( $result )."\n";
//echo "verified=".( $verified ? 1 : 0 )." time=".( time() - $start )."\n";
//echo "iterations=$iterations\n";
exit( 0 );
//////////////////////////////////////////////////////////////////////
// Functions
//////////////////////////////////////////////////////////////////////
function trimAndAppend( $current, $more )
{
return $current.trim( $more );
}
function computeResultBFS( $cards )
{
global $start, $timeout, $numcards, $half, $desired, $desiredFlip;
global $identities, $flips, $iterations, $maxSeqLength, $maxDictSeqLength;
$bestScore = 0;
$bestOps = "";
$origCards = $cards;
$origCardsFlip = myFlip( $cards );
$current = array();
$next = array( $cards => "" );
$seen = array();
$dictionary = array( "C" => TRUE, "S" => TRUE );
$iterations = 0;
$iterPerSec = 1000;
while ( $next != array() )
{
$current = $next;
$next = array();
foreach ( $current as $c => $ops )
{
$opslen = strlen( $ops );
++$iterations;
if ( $iterations % $iterPerSec == 0 )
{
$elapsed = time() - $start;
// recompute for better timeout accuracy
if ( $elapsed * 4 > $timeout )
$iterPerSec = $iterations / $elapsed;
if ( $elapsed > $timeout )
return $bestOps;
}
if ( isset( $seen[$c] ) ) continue; // we've already seen this one
$seen[$c] = TRUE;
if ( $c == $desired )
return $ops;
// see comment above regarding $desiredFlip
if ( $c == $desiredFlip )
return $ops."F";
$testScore = score( $c, $desired );
if ( $testScore > $bestScore )
{
$bestScore = $testScore;
$bestOps = $ops;
}
$testScore = score( $c, $desiredFlip );
if ( $testScore > $bestScore )
{
$bestScore = $testScore;
$bestOps = $ops."F";
}
// don't allow ones that end in identity transformations or flips,
// as these will have already been examined elsewhere
if ( hasTailingIdentity( $ops ) || hasTailingFlip( $ops ) )
continue;
// don't go beyond the max sequence length
if ( $opslen >= $maxSeqLength )
continue;
// notice features about this set of operations
if ( $opslen > 0 )
{
// take this time to track identity transformations!
if ( $c == $origCards )
{
$identities[$ops] = TRUE;
}
// take this time to track flip equivalents!
elseif ( $c == $origCardsFlip )
{
$flips[$ops] = TRUE;
}
// otherwise, is this an appropriate dictionary entry
elseif ( $opslen > 1 && $opslen <= $maxDictSeqLength )
{
$dictionary[$ops] = TRUE;
}
}
// traverse outbound edges of BFS
foreach ( array_keys( $dictionary ) as $dictOps )
{
$temp = performOps( $c, $dictOps );
$next[$temp] = $ops.$dictOps;
}
}
}
if ( $bestOps == "" && $bestScore > 0 )
$bestOps = "CC"; // apparently doing nothing was best - return a no-op
return $bestOps;
}
function hasTailingIdentity( $ops )
{
global $identities;
foreach ( array_keys( $identities ) as $ident )
{
if ( stringEndsWith( $ops, $ident ) )
{
return TRUE;
}
}
return FALSE;
}
function addIdentity( $ops )
{
global $identities;
$identities[$ops] = TRUE;
}
function hasTailingFlip( $ops )
{
global $flips;
foreach ( array_keys( $flips ) as $flip )
{
if ( stringEndsWith( $ops, $flip ) )
{
return TRUE;
}
}
return FALSE;
}
function addFlip( $ops )
{
global $flips;
$flips[$ops] = TRUE;
}
function getDesiredCards( $len )
{
$ordA = ord( "A" );
$half = $len / 2;
$cards = "";
for ( $i = 0; $i < $half; ++$i )
{
$cards = $cards.chr( $ordA + $i );
}
return $cards.strtolower( $cards );
}
function score( $cards, $desired )
{
global $half;
$score = 0;
foreach ( range( 0, $half - 1 ) as $i )
{
if ( $cards[$i] == $desired[$i] )
++$score;
}
$score = $score * 2;
return $score;
}
function myCut( $cards )
{
global $half;
return substr( $cards, $half ).substr( $cards, 0, $half );
}
function myFlip( $cards )
{
return strrev( $cards );
}
function myShuffle( $cards )
{
global $half;
$out = "";
for ( $i = 0; $i < $half; ++$i )
$out = $out.$cards[$half+$i].$cards[$i];
return $out;
}
function stringEndsWith( $string, $tail )
{
$taillen = strlen( $tail );
$stringlen = strlen( $string );
if ( $taillen > $stringlen )
return FALSE;
if ( $taillen == $stringlen )
return ( strcmp( $string, $tail ) == 0 );
foreach( range( 1, $taillen ) as $i )
{
if ( $string[$stringlen-$i] != $tail[$taillen-$i] )
return FALSE;
}
return TRUE;
}
function performOps( $cards, $ops )
{
global $numcards, $half;
$numops = strlen( $ops );
for ( $i = 0; $i < $numops; ++$i )
{
$ch = $ops[$i];
switch ( $ch )
{
case "S":
$cards = myShuffle( $cards );
break;
case "C":
$cards = myCut( $cards );
break;
case "F":
$cards = myFlip( $cards );
break;
default:
return FALSE;
}
}
return $cards;
}
function verifyResult( $cards, $ops )
{
global $numcards, $desired;
$numcards = strlen( $cards );
if ( $ops != "" )
$cards = performOps( $cards, $ops );
return ( $cards == $desired );
}
?>
Back to results
|
|
|
