Code of peter
<?PHP
# Peter Csaba - cpeter@webnova.ro
$time_start = getmicrotime();
define('MAXTIME' ,59.7);
define('MAXLEVEL' ,28);
# get input data
$input = join('',file('deck.txt'));
# if input data is not 100% correct, new line will be removed
$input = str_replace("\r","",str_replace("\n","",$input));
$N = strlen($input);
$n = $N/2;
/* translate letters into numbers */
for($p=0;$p<strlen($input); $p++){
$ideck[0][$p] = $input{$p} < 'a' ? ord($input{$p})-ord('A') : ord($input{$p})-ord('a')+$n;
}
/* original and its flipped version */
for($i = 0; $i < $N; $i++){
$rev[$N-1-$i] = $id[$i] = $i;
}
$maxmatches = matches($id, $ideck[0]);
$nummatches = matches($rev, $ideck[0]);
if($nummatches > $maxmatches) {
$maxmatches = $nummatches;
$bestF = 1;
}
if($maxmatches == $n)
done();
$movebits = $bestbits = 0;
$bestlevel = 0;
$bestF = 0;
for($maxlevel = 2; $maxlevel <= MAXLEVEL; $maxlevel += 2) {
$down = 1;
$level = 1;
while($level) {
if($down) {
$movebits <<= 1;
_Shuffle($ideck[$level-1], $ideck[$level]);
} else if($movebits & 3) {
$movebits >>= 1;
$level--;
} else {
$movebits++;
_Cut($ideck[$level-1], $ideck[$level]);
$down = 1;
}
if($down && $level > $maxlevel - 2) {
/*
* We have a deck, check both
* it and its flipped version.
*/
for($fflag = 0; $fflag < 2; $fflag++) {
if($fflag)
_Flip($ideck[$level], $tmpdeck2);
else
_Copy($ideck[$level], $tmpdeck2);
/*
* Check first to see if tmpdeck2 is
* is better than the previous best
* deck.
*/
$nummatches = matches($id, $tmpdeck2);
if($nummatches > $maxmatches) {
$maxmatches = $nummatches;
$bestbits = $movebits;
$bestlevel = $level;
$bestF = $fflag;
}
/*
* Check that time isn't running out.
*/
if(Elapsed() > MAXTIME)
done();
} # end for
} # end if
if($down)
$level++;
if($level > $maxlevel) {
$down = 0;
$level--;
}
/*
* Check for perfect solution with the direct
* approach.
*/
if($maxmatches == $n)
done();
} # end while
} # end for
function done(){
GLOBAL $maxmatches,$bestlevel,$bestF,$bestbits;
$final = "";
if($bestlevel || $bestF)
$final .= decode($bestbits, $bestlevel, $bestF);
else
$final .= "FF";
$len = strlen($final);
print "$final$len";
exit;
}
function _Copy(&$old,&$new){
$new = $old;
}
function _Cut(&$old, &$new)
{
GLOBAL $n;
for($i = 0, $j = $n; $i < $n; $i++, $j++) {
$new[$i] = $old[$j];
$new[$j] = $old[$i];
}
}
function _Shuffle($old, &$new)
{
GLOBAL $n,$N;
for($i = 0, $j = $n; $i < $N; $i += 2, $j++)
$new[$i] = $old[$j];
for($i = 1, $j = 0; $j < $n; $i += 2, $j++)
$new[$i] = $old[$j];
}
function _Flip(&$old, &$new)
{
GLOBAL $N;
for($i = 0, $j = $N-1; $i < $N; $i++, $j--)
$new[$i] = $old[$j];
}
/*
* Compute the number of matches between two decks.
* central symmetry
*/
function matches(&$x, &$y)
{
GLOBAL $n;
$t = 0;
for($i = 0; $i < $n; $i++)
if($x[$i] == $y[$i])
$t++;
return $t;
}
/*
* Convert a bit-vector representation of a move sequence into a
* sequence of 'S' and 'C' characters
*/
function decode($bits, $m, $F)
{
$seq = "";
if(!empty($F))
$seq .= 'F';
while($m--)
$seq .= ($bits & (1 << $m)) ? 'C' : 'S';
return $seq;
}
/*
* Keep track of number of elapsed seconds.
*/
function Elapsed()
{
GLOBAL $time_start;
$time_end = getmicrotime();
$time = $time_end - $time_start;
return $time;
}
/*
* get microtime to see how much time has spent
*/
function getmicrotime(){
list($usec, $sec) = explode(" ",microtime());
return ((float)$usec + (float)$sec);
}
?>
Back to results
|
|
