Main Menu |
|
|
 |
Forums |
|
|
|
Programming
Contest |
| |
|
Documentation
|
| |
|
Partner
Sites |
|
|
Sponsors |
|
|
|
|
Code of robert
<?PHP
/********************************************************/
/* */
/* Cardsorter */
/* */
/* Code for the Contest of www.php-editors.com */
/* */
/* The programm solves the problem with an iterativ */
/* backtracking method. Cyclic checks are prevented */
/* by saving allready tried solutions. */
/* Running time is controlled by an internal check. */
/* */
/* Version: 1.0 19.3.2003 */
/* Author: Robert Schmelzer */
/* Contact: robert@schmelzer.cc */
/* www.schmelzer.cc */
/* Address: [ removed for contest ] */
/* [ removed for contest ] */
/* Austria */
/* */
/* The deck must be in the file deck.txt and has to */
/* be in the same directory. */
/* */
/********************************************************/
/* Define execution time !! */
define("MAX_EXECUTION_TIME", 60);
/* Build correct solution */
function solution($len) {
$sol = "";
for($i=0; $i<$len/2; $i++) { $sol .= chr(65+$i); }
for($i=0; $i<$len/2; $i++) { $sol .= chr(97+$i); }
return $sol;
}
/* Calculate the score of a try */
function score($str) {
global $solution, $length;
$score = 0;
for($i=0; $i<$length; $i++) {
if ($str{$i} == $solution{$i}) { $score ++; }
}
return $score;
}
/* The backtracking algorithm itself */
function solve($input) {
global $length, $half, $solution;
if ($input == $solution) { $finished=true; }
$trys = array();
$current = array();
$trys[$input] = false;
$actions = 0;
$bestSc = 0;
$bestSol = 0;
$startTime = time();
$abortTime = floor(MAX_EXECUTION_TIME * 0.85);
$stack = array();
array_unshift($stack, array($input, 0));
$timeCheck = 0;
while(true) {
$timeCheck ++;
list($try, $sol) = array_pop($stack);
$op = $sol % 3;
$opNew = $sol *3;
// flip
if ( $op != 0) {
$newtry = (strrev($try));
if ($newtry == $solution) { $actions = $opNew; break; }
if (!array_key_exists($newtry, $trys)) {
array_unshift($stack, array($newtry, $opNew));
if (($sc=score($newtry)) > $bestSc) {
$bestSc = $sc;
$bestSol = $opNew;
}
$trys[$newtry] = false;
}
}
// shuffle
$newtry = "";
for($i=0; $i < $half; $i++) {
$newtry .= $try{$half+$i}.$try{$i};
}
if ($newtry == $solution) { $actions = $opNew+1; break; }
if (!array_key_exists($newtry, $trys)) {
array_unshift($stack, array($newtry, $opNew + 1));
if (($sc=score($newtry)) > $bestSc) {
$bestSc = $sc;
$bestSol = $opNew+1;
}
$trys[$newtry] = false;
}
// cut
if ( $op != 2) {
$newtry = (substr($try, $half).substr($try, 0, $half));
if ($newtry == $solution) { $actions = $opNew+2; $finished=true; break; }
if (!array_key_exists($newtry, $trys)) {
array_unshift($stack, array($newtry, $opNew + 2));
if (($sc=score($newtry)) > $bestSc) {
$bestSc = $sc;
$bestSol = $opNew+2;
}
$trys[$newtry] = false;
}
}
if ($timeCheck > 200) {
if ( (time() - $startTime) > $abortTime ) {
$actions = $bestSol;
break;
}
$timeCheck = 0;
}
}
return $actions;
}
// START MAIN PROGRAM
// read from file
$file = file("deck.txt");
$input = trim($file[0]);
$length = strlen($input);
$half = $length / 2;
$solution = solution($length);
// solve the problem
$actions = solve($input);
// output
$i = $actions;
$actstr="";
$i = $i *3;
while($i>=3) {
$i = floor($i / 3);
$j = $i % 3;
if ($j == 0) { $actstr = "F".$actstr ; }
if ($j == 1) { $actstr = "S".$actstr ; }
if ($j == 2) { $actstr = "C".$actstr ; }
}
print($actstr.strlen($actstr));
?>
Back to results
|
|
|
