Code of agastiya
<?php
/**
* Flip Shuffles Programming Contest
* (see http://php-editors.com/contest_b_1.htm)
* Solve this samples:
* CAcaDBdb --> SCF3 0s- 3
* dbDBcaCA --> CSF3 0s- 3
* AcCeJgbidEfGBIDaFhHj --> SSSCFSCSS9 0s- 9 heuNumSteps()
* DeEfFgaGAbBcCd --> CFSSSCFSSSCFSSSCFSSSFCSSSFCSSSFCSSS35 0s-11 heuWrongOrder()
* aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ
* --> CSCSCSCSCSCSCSC15 5s-15 heuNumSteps()
*
* @author Agastiya S. Mohammad (agastiyasm@hotmail.com)
* @version $Id: php.xml,v 1.0 2003-01-02 20:23:56+01 Exp administrateur $
* @copyright 2003
**/
define('MAX_RUNNING_TIME', 55);
define('PROBLEM_FILE', 'deck.txt');
// --- data structure ---
$node_exist = array();
$open_list = array();
$openKey_lst = array();
$openWgh_lst = array();
$operators = array('C'=>'opCut', 'S'=>'opShuffle', 'Z'=>'opFlip');
// --- problem set ---
$str = 'aA';
$goal = 'Aa';
$end = 2;
$mid = 1;
// --- operators ---
function &opCut (&$str) {
return ( substr($str, $GLOBALS['mid']) . substr($str, 0, $GLOBALS['mid']) );
}
function &opShuffle (&$str) {
$k = '';
for ($i=0; $i<$GLOBALS['mid']; $i++) {
$k .= $str{$GLOBALS['mid']+$i} . $str{$i};
}
return $k;
}
function &opFlip (&$str) {
return strrev($str);
}
// --- solution search ---
function heuPathCost (&$key) {
return strlen($key);
}
function heuWrongOrder (&$str) { // value: 0 s/d end
$j=0;
$a = ord( $str{0} );
for ($i=1; $i<$GLOBALS['end']; $i++) {
$b = ord( $str{$i} );
if (abs($a-$b)>26) $j++;
$a = $b;
}
return $j;
}
function heuNumSteps (&$str) { // rata2 operasi yang harus ditempuh
$j=0;
for ($i=0; $i<$GLOBALS['mid']; $i++) {
$c = abs(strpos($str, chr(65+$i))-$i) +
abs(strpos($str, chr(97+$i))-$GLOBALS['mid']-$i);
$j+= $c%$GLOBALS['mid'] + ceil($c/$GLOBALS['mid']);
}
return ceil($j/$GLOBALS['end']);
}
function AStarWeight (&$key, &$str) {
return heuPathCost($key) + min(heuNumSteps($str), heuWrongOrder($str));
}
function Score (&$str) {
return strlen($str)-levenshtein($str, $GLOBALS['goal']);
}
function OpenListPut (&$str, $key ='') {
if (!isset($GLOBALS['node_exist'][$str])) {
$GLOBALS['node_exist'][$str] = TRUE;
array_push($GLOBALS['openKey_lst'], $key);
array_push($GLOBALS['open_list'], $str);
array_push($GLOBALS['openWgh_lst'], AStarWeight($key, $str));
array_multisort(
$GLOBALS['openWgh_lst'], SORT_NUMERIC, SORT_ASC,
$GLOBALS['openKey_lst'], SORT_STRING, SORT_ASC,
$GLOBALS['open_list'] );
}
}
function &OpenListGet () {
$key = array_shift($GLOBALS['openKey_lst']);
$str = array_shift($GLOBALS['open_list']);
$wgh = array_shift($GLOBALS['openWgh_lst']);
return array(&$key,&$str,&$wgh);
}
function OpenListCount() {
return count($GLOBALS['open_list']);
}
function BestFirst () {
$bestKey = '';
$bestScr = 0;
$start = time();
OpenListPut( $GLOBALS['str'] );
while(($t=time()-$start)<MAX_RUNNING_TIME && OpenListCount()) {
list($key,$str,$wgh) = OpenListGet();
if (($scr=Score($str))>$bestScr) {
$bestKey = $key; // best steps towards best state
$bestScr = $scr; // best score
}
if ($str==$GLOBALS['goal']) // goal found!!!
break;
foreach ($GLOBALS['operators'] as $idx=>$op)
OpenListPut( $op($str), $key.$idx );
}
return str_replace('Z', 'F', $bestKey) . heuPathCost($bestKey);
}
// --- others ---
function makeGoal () {
for ($i=0; $i<$GLOBALS['mid']; $i++) {
$big .= chr(65+$i);
$small .= chr(97+$i);
}
$GLOBALS['goal'] = $big . $small;
}
function readProblem () {
$GLOBALS['str'] = trim(implode('', @file(PROBLEM_FILE)));
$GLOBALS['end'] = strlen($GLOBALS['str']);
$GLOBALS['mid'] = $GLOBALS['end']/2;
makeGoal();
}
// --- main ---
readProblem();
echo BestFirst();
?>
Back to results
|
|
