Code of mourgogiannis
<?php
// Written by Mourgoyiannis Spiros
// cypher@otenet.gr
//3..2..1 GO!
$temp=gettimeofday();
$start_sec=(int)$temp["sec"];
set_time_limit(60);
function getmicrotime()
{
list($usec, $sec) = explode(" ",microtime());
return ((float)$usec + (float)$sec);
}
if(strlen($TimeIt) == 0)
$TimeIt = $_GET['TimeIt'];
if(strlen($TimeIt))
$time_start = getmicrotime();
//code to select algo...
$param = urldecode($LowMem);
if(strlen($param) == 0)
$param = $_GET['LowMem'];
if($param != "1")
{ //use more memory to optimize performance - DEFAULT ALGORITHM!!!
function CFS($n)
{
global $row, $com, $rlen, $hrlen, $bSuccess, $RecursionDepth, $BestMatchSoFar, $FullCallEndings, $SemiCallEndings, $StartDepth, $EndDepth, $StartPos, $EndPos, $BestMatchCom, $start_sec, $mxShfVl, $crShf;
if($bSuccess)
return;
if($n == $StartDepth)
$SemiCallEndings++;
if($n == $EndDepth && $com[$n-1] != 1)
$FullCallEndings++;
if($n == $RecursionDepth)
{
if($crShf < $mxShfVl)
{
$temp=gettimeofday();
$stop_sec=(int)$temp["sec"];
if ($stop_sec-$start_sec >= 59)
{
$depth = strlen($BestMatchCom);
if($depth)
echo "$BestMatchCom$depth";
$bSuccess = true;
return;
}
$Match = 0;
$SemiBase = ($SemiCallEndings - 1)*$hrlen;
$FullBase = ($FullCallEndings - 1)*$hrlen;
for($i = 0; $i < $hrlen; $i++)
{
//compute the final position for each card
$pos = $StartPos[$SemiBase + $i];
for($j = $StartDepth; $j < $RecursionDepth; $j++)
switch($com[$j])
{
case 0:
$pos = ($hrlen + $pos) % $rlen;
break;
case 1:
$pos = $rlen - $pos - 1;
break;
case 2:
if($pos >= $hrlen)
$pos = ($pos - $hrlen)<<1;
else
$pos = ($pos<<1) + 1;
break;
}
if($pos == $row[$i])
$Match++;
if($EndDepth == $RecursionDepth && $com[$n-1] != 1)
$EndPos[$FullBase + $i] = $pos;
}
if($Match > $BestMatchSoFar)
{
$BestMatchSoFar = $Match;
$BestMatchCom = "";
for($i = 0; $i < $RecursionDepth; $i++)
switch($com[$i])
{
case 0:
$BestMatchCom .= 'C';
break;
case 1:
$BestMatchCom .= 'F';
break;
case 2:
$BestMatchCom .= 'S';
break;
}
// echo "<p>Best Match $BestMatchSoFar / $hrlen</p>\n";
}
if($Match == $hrlen)
{
//all cards match their final position through the 'com' transformation
$bSuccess = true;
echo "$BestMatchCom$RecursionDepth";
}
}
}
else
{
if($n == 0 || $com[$n-1])
{
$bck = $crShf;
$crShf = 0;
$com[$n] = 0;
CFS($n+1);
$crShf = $bck;
}
// only one flip is enough, so try it only in the last move
if($n == $RecursionDepth - 1)
{
$com[$n] = 1;
CFS($n+1);
}
$crShf++;
$com[$n] = 2;
CFS($n+1);
$crShf--;
}
}
$row = array();
$com = array();
$StartPos = array();
$EndPos = array();
$mxShf = array(1 => 1, 2, 3, 3, 5, 6, 4, 4, 9, 6, 11, 10, 9, 14, 5, 5, 12, 18, 12, 10, 7, 12, 23, 21, 8, 26);
$fh = fopen("deck.txt", "r");
if(!$fh)
echo "<p>Error: Unable to open deck.txt!</p>\n";
else
{
fscanf($fh, "%[a-zA-Z]", $flrow);
fclose($fh);
$rlen = strlen($flrow);
$hrlen = $rlen >> 1;
for($i = 0; $i < $rlen; $i++)
if($flrow[$i] >= 'a' && $flrow[$i] <= 'z')
$row[$i] = $hrlen + (ord($flrow[$i]) - ord("a"));
else
$row[$i] = ord($flrow[$i]) - ord("A");
$mxShfVl = $mxShf[$hrlen];
$RecursionDepth = 1;
$bSuccess = false;
$BestMatchSoFar = 0;
$BestMatchCom = "";
while(($bSuccess == false) && ($RecursionDepth < 100))
{
// if($RecursionDepth < 20) //use this option to decrease memory usage
{
$StartDepth = $RecursionDepth - 1;
$EndDepth = $RecursionDepth;
if($StartDepth)
$StartPos = $EndPos;
else
{
for($i = 0; $i < $hrlen; $i++)
$StartPos[$i] = $i;
}
}
$FullCallEndings = 0;
$SemiCallEndings = 0;
$crShf = 0;
CFS(0);
// echo "$RecursionDepth, ";
$RecursionDepth++;
}
}
}
else
{ //use less memory - SLOWER ALGORITHM, ONLY FOR TESTS!!!
function ComputeShuffles()
{
global $rlen, $hrlen, $MaxShn, $bshf, $is1, $is2, $is3, $is4;
$MaxShn = 0;
$bRepeat = true;
do
{
for($i = 0; $i < $rlen; $i++)
{
if($MaxShn == 0)
{
if($i >= $hrlen)
$shf[$rlen + $i] = ($i - $hrlen) << 1;
else
$shf[$rlen + $i] = ($i << 1) + 1;
}
else
{
if($shf[$MaxShn * $rlen + $i] >= $hrlen)
$shf[($MaxShn+1) * $rlen + $i] = ($shf[$MaxShn * $rlen + $i] - $hrlen) << 1;
else
$shf[($MaxShn+1) * $rlen + $i] = ($shf[$MaxShn * $rlen + $i] << 1) + 1;
}
}
for($i = 0; $i < $hrlen; $i++)
if($shf[($MaxShn+1) * $rlen + $i] != $i)
break;
if($i == $hrlen)
$bRepeat = false;
else
{
for($i = 0; $i < $hrlen; $i++)
if($shf[($MaxShn+1) * $rlen + $i] != $rlen - $i - 1)
break;
if($i == $hrlen)
$bRepeat = false;
}
$MaxShn++;
} while($bRepeat);
$MaxShn--;
$is1 = $rlen;
$is2 = $is1 * ($MaxShn + 1);
$is3 = $is2 * ($MaxShn + 1);
$is4 = $is3 * ($MaxShn + 1);
// $bshf = new char[$is4*($MaxShn + 1)];
for($k = 0; $k <= $MaxShn; $k++)
for($i = 0; $i < $rlen; $i++)
$bshf[$is1 * $k + $i] = $shf[$k * $rlen + $i];
$lcCom[8] = array();
for($i1 = 0; $i1 <= $MaxShn; $i1++)
{
if($i1)
{
$lcCom[0] = $i1;
}
else
{
$lcCom[0] = -2;
}
for($i2 = $i1 ? 1 : 0; $i2 <= $MaxShn; $i2++)
{
if($i2)
{
$lcCom[1] = 0;
$lcCom[2] = $i2;
}
else
{
$lcCom[1] = $lcCom[2] = -2;
}
for($i3 = 1; $i3 <= $MaxShn; $i3++)
{
$lcCom[3] = 0;
$lcCom[4] = $i3;
for($i4 = 1; $i4 <= $MaxShn; $i4++)
{
$lcCom[5] = 0;
for($i = 0; $i < $rlen; $i++)
{
$pos = $shf[$i4 * $rlen + $i];
for($j = 5; $j >= 0; $j--)
{
switch($lcCom[$j])
{
case 0:
$pos = ($hrlen + $pos) % $rlen;
break;
case -2:
break; // do nothing, blank position
default:
$pos = $shf[$lcCom[$j] * $rlen + $pos];
break;
}
}
$bshf[$i1 * $is4 + $i2 * $is3 + $i3 * $is2 + $i4 * $is1 + $i] = $pos;
}
}
}
}
}
}
function CFS($n)
{
global $row, $com, $rlen, $hrlen,
$bSuccess, $RecursionDepth,
$BestMatchSoFar, $BestMatchCom,
$start_sec, $lpos, $lcpos,
$MaxShn, $ComLen,
$bshf, $is1, $is2, $is3, $is4;
if($bSuccess)
return;
if($ComLen == $RecursionDepth)
{
$temp=gettimeofday();
$stop_sec=(int)$temp["sec"];
if ($stop_sec-$start_sec >= 59)
{
$depth = strlen($BestMatchCom);
if($depth)
echo "$BestMatchCom$depth";
$bSuccess = true;
return;
}
$Match = 0;
for($i = 0; $i < $hrlen; $i++)
{
//compute the final position for each card
if($i > $lcpos)
{
$pos = $i;
$j = 0;
}
else
{
$pos = $lpos[$i];
$j = $n - 1;
}
for(; $j < $n; $j++)
{
if($j == $n - 1)
$lpos[$i] = $pos;
switch($com[$j])
{
case 0:
$pos = ($hrlen + $pos) % $rlen;
break;
case -1:
$pos = $rlen - $pos - 1;
break;
default:
$i1 = 0;
$i2 = 0;
$i3 = 0;
$i4 = $com[$j] * $is1;
$jp = $j+2;
if($jp < $n && $com[$jp] > 0)
{
$i3 = $com[$jp] * $is2;
$j = $jp;
$jp += 2;
if($jp < $n && $com[$jp] > 0)
{
$i2 = $com[$jp] * $is3;
$j = $jp;
$jp +=2;
if($jp < $n && $com[$jp] > 0)
{
$i1 = $com[$jp] * $is4;
$j = $jp;
}
}
}
$pos = $bshf[$i1 + $i2 + $i3 + $i4 + $pos];
break;
}
}
if($pos == $row[$i])
$Match++;
}
$lcpos = $rlen;
if($Match > $BestMatchSoFar)
{
$BestMatchSoFar = $Match;
$BestMatchCom = "";
for($i = 0; $i < $n; $i++)
switch($com[$i])
{
case 0:
$BestMatchCom .= 'C';
break;
case -1:
$BestMatchCom .= 'F';
break;
default:
for($k = 0; $k < $com[$i]; $k++)
$BestMatchCom .= 'S';
break;
}
// echo "<p>Best Match $BestMatchSoFar / $hrlen</p>\n";
}
if($Match == $hrlen)
{
//all cards match their final position through the 'com' transformation
$bSuccess = true;
echo "$BestMatchCom$RecursionDepth";
}
}
else
{
$lcpos = -1;
if($n == 0 || $com[$n-1])
{
$ComLen++;
$com[$n] = 0;
CFS($n+1);
$ComLen--;
}
// only one flip is enough, so try it only in the last move
if($ComLen == $RecursionDepth - 1)
{
$ComLen++;
$com[$n] = -1;
CFS($n+1);
$ComLen--;
}
if($n == 0 || $com[$n-1] < 1)
{
$lclMaxSfn;
if($ComLen + $MaxShn > $RecursionDepth)
$lclMaxSfn = $RecursionDepth - $ComLen;
else
$lclMaxSfn = $MaxShn;
for($k = 1; $k <= $lclMaxSfn; $k++)
{
$ComLen += $k;
$com[$n] = $k;
CFS($n+1);
$ComLen -= $k;
}
}
}
}
$row = array();
$com = array();
$lpos = array();
$bshf = array();
$fh = fopen("deck.txt", "r");
if(!$fh)
echo "<p>Error: Unable to open deck.txt!</p>\n";
else
{
fscanf($fh, "%[a-zA-Z]", $flrow);
fclose($fh);
$rlen = strlen($flrow);
$hrlen = $rlen >> 1;
for($i = 0; $i < $rlen; $i++)
if($flrow[$i] >= 'a' && $flrow[$i] <= 'z')
$row[$i] = $hrlen + (ord($flrow[$i]) - ord("a"));
else
$row[$i] = ord($flrow[$i]) - ord("A");
ComputeShuffles();
$RecursionDepth = 1;
$bSuccess = false;
$BestMatchSoFar = 0;
$BestMatchCom = "";
while(($bSuccess == false) && ($RecursionDepth < 100))
{
$ComLen = 0;
CFS(0);
// echo "$RecursionDepth, ";
$RecursionDepth++;
}
}
}
if(strlen($TimeIt))
{
$time_end = getmicrotime();
$time = $time_end - $time_start;
echo "<p>Execution time: $time</p>\n";
}
?>
Back to results
|
|
