Main Menu |
|
|
 |
Forums |
|
|
|
Programming
Contest |
| |
|
Documentation
|
| |
|
Partner
Sites |
|
|
Sponsors |
|
|
|
|
Code of victor
<?PHP
/**
* Victor Farazdagi/Kuulest
* farazdagi@linuxmail.org
*/
//Checking time
$start_time = time();
//read file
$deck = file('./deck.txt') or die('Deck is not present');
//Upper case letters
$lU = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
//Lower case letters
$lL = 'abcdefghijklmnopqrstuvwxyz';
//number of cards
$c_no = strlen($deck[0]);
//unmixed deck
$deck[] = substr($lU,0,$c_no/2).substr($lL,0,$c_no/2);
$moves = array(array(),array());
$best_move = array(0,'');
//create empty matrix
$m_empty = array();
for($i=0; $i<$c_no; $i++) {
for($j=0; $j<$c_no; $j++) {
$m_empty[$j][$i] = 0;
}
}
//create mixed deck matrix
$m_mdeck = $m_empty;
for($i=0; $i<$c_no; $i++) {
for($j=0; $j<strlen($deck[1]); $j++) {
if($deck[0][$i]==$deck[1][$j]) {
$m_mdeck[$j][$i] = 1;
}
}
}
//create identity matrix
$m_identity = $m_empty;
for($i=0; $i<$c_no; $i++) {
for($j=0; $j<$c_no; $j++) {
if($i==$j) {
$m_identity[$j][$i] = 1;
}
}
}
//create flip matrix
$m_flip = $m_empty;
for($i=0; $i<$c_no; $i++) {
for($j=0; $j<$c_no; $j++) {
if($i==$c_no-$j-1) {
$m_flip[$j][$i] = 1;
}
}
}
//create cut matrix
$m_cut = $m_empty;
for($i=0; $i<$c_no; $i++) {
for($j=0; $j<$c_no; $j++) {
if($i==$j) {
$m_cut[$i][(($i<$c_no/2)?$j+$c_no/2:$j-$c_no/2)] = 1;
}
}
}
//create shuffle matrix
$m_shuffle = $m_empty;
for($i=0; $i<$c_no; $i++) {
for($j=0; $j<$c_no; $j++) {
if($i==$j) {
$m_shuffle[$i][(($i<$c_no/2)?(2*$j + 1):(2*$j - $c_no))] = 1;
}
}
}
$moves[0][] = $m_mdeck;
$moves[1][] = 'mixed';
get_moves($m_mdeck,'');
echo $best_move[1].strlen($best_move[1]);
function get_moves($p_move,$p_ext_move) {
global $moves, $m_flip, $m_cut, $m_shuffle,$m_identity, $c_no, $best_move,$start_time;
//find possible moves from current position
$m_moves = array(
array('cut'=>$m_cut,'flip'=>$m_flip,'shuffle'=>$m_shuffle), //matrices
array('cut'=>'','flip'=>'','shuffle'=>''), //operations
array('cut'=>0,'flip'=>0,'shuffle'=>0)); //points
//Flip
$m_tmp = mX($p_move,$m_flip);
if(!is_unique($m_tmp)) {
unset($m_moves[0]['flip']);
unset($m_moves[1]['flip']);
} else {
$m_moves[0]['flip'] = $m_tmp;
$m_moves[1]['flip'] = $p_ext_move.'F';
$m_moves[2]['flip'] = get_points($m_tmp);
if($m_moves[2]['flip']>$best_move[0]) {
$best_move[0] = $m_moves[2]['flip'];
$best_move[1] = $m_moves[1]['flip'];
}
$moves[0][] = $m_moves[0]['flip'];
$moves[1][] = $m_moves[1]['flip'];
}
//Cut
$m_tmp = mX($p_move,$m_cut);
if(!is_unique($m_tmp)) {
unset($m_moves[0]['cut']);
unset($m_moves[1]['cut']);
} else {
$m_moves[0]['cut'] = $m_tmp;
$m_moves[1]['cut'] = $p_ext_move.'C';
$m_moves[2]['cut'] = get_points($m_tmp);
if($m_moves[2]['cut']>$best_move[0]) {
$best_move[0] = $m_moves[2]['cut'];
$best_move[1] = $m_moves[1]['cut'];
}
$moves[0][] = $m_moves[0]['cut'];
$moves[1][] = $m_moves[1]['cut'];
}
//Shuffle
$m_tmp = mX($p_move,$m_shuffle);
if(!is_unique($m_tmp)) {
unset($m_moves[0]['shuffle']);
unset($m_moves[1]['shuffle']);
} else {
$m_moves[0]['shuffle'] = $m_tmp;
$m_moves[1]['shuffle'] = $p_ext_move.'S';
$m_moves[2]['shuffle'] = get_points($m_tmp);
if($m_moves[2]['shuffle']>$best_move[0]) {
$best_move[0] = $m_moves[2]['shuffle'];
$best_move[1] = $m_moves[1]['shuffle'];
}
$moves[0][] = $m_moves[0]['shuffle'];
$moves[1][] = $m_moves[1]['shuffle'];
}
$scores = array(array(),array());
if(isset($m_moves[0]['cut'])) {
$scores[0][] = $m_moves[2]['cut'];
$scores[1][] = 'cut';
}
if(isset($m_moves[0]['shuffle'])) {
$scores[0][] = $m_moves[2]['shuffle'];
$scores[1][] = 'shuffle';
}
if(isset($m_moves[0]['flip'])) {
$scores[0][] = $m_moves[2]['flip'];
$scores[1][] = 'flip';
}
for($i=count($scores[0])-1; $i>=0; $i--) {
for($j=$i-1; $j>=0; $j--) {
if($scores[0][$i]>$scores[0][$j]) {
$t = $scores[0][$i];
$scores[0][$i] = $scores[0][$j];
$scores[0][$j] = $t;
$t = $scores[1][$i];
$scores[1][$i] = $scores[1][$j];
$scores[1][$j] = $t;
}
}
}
$m_moves_new = array(array(),array(),array());
foreach($scores[1] as $key) {
$m_moves_new[0][$key] = $m_moves[0][$key];
$m_moves_new[1][$key] = $m_moves[1][$key];
$m_moves_new[2][$key] = $m_moves[2][$key];
}
foreach($m_moves_new[0] as $key=>$move) {
if((time()-$start_time)>57) {
echo $best_move[1].strlen($best_move[1]);
exit;
}
if(is_solved($move)) {
echo $m_moves_new[1][$key].strlen($m_moves_new[1][$key]);
exit;
}
if(!(strlen($m_moves_new[1][$key])>11)) {
get_moves($move,$m_moves_new[1][$key]);
}
}
}
function get_points($i_move) {
global $m_identity,$c_no;
$o_pts = 0;
for($i=0; $i<$c_no; $i++) {
$o_pts += $i_move[$i][$i];
}
return $o_pts;
}
function is_unique($i_move) {
global $moves;
foreach($moves[0] as $move) {
if($move == $i_move) {
return FALSE;
}
}
return TRUE;
}
function is_solved($i_move) {
global $m_identity;
if($i_move==$m_identity) {
return TRUE;
} else {
return FALSE;
}
}
function mX($iA,$iB) {
$oM = array();
$oM = array_pad($oM,count($iA),array_pad(array(),count($iA),0));
$c_x = sizeof($iA);
for($i=0; $i<$c_x; $i++) {
for($j=0; $j<$c_x; $j++) {
$oM[$i][$j] = 0;
for($k=0; $k<$c_x; $k++) {
$oM[$i][$j] += $iA[$i][$k]*$iB[$k][$j];
}
}
}
return $oM;
}
?>
Back to results
|
|
|
