Code of joshua
<?php
// ATTN: contest@php-editors.com
// SUBJECT: PHP Coding Contest (B1) March-April 2003
//
// copyright March 2003
// Joshua E Cook
set_time_limit(59);
main();
function main() {
global $best_ops;
register_shutdown_function('shutdown');
ob_start();
readfile('deck.txt');
$deck = trim(ob_get_contents());
ob_end_clean();
$best_ops = evaluate_deck($deck);
// echo test_deck($deck,$best_ops),"\n";
}
function shutdown() {
global $best_ops;
echo $best_ops,strlen($best_ops);
}
function test_deck($deck,$ops) {
$num_ops = strlen($ops);
for ( $i=0; $i<$num_ops; $i++ ) {
if ( $ops[$i] == 'S' ) {
$deck = shuffle_deck($deck);
} else if ( $ops[$i] == 'F' ) {
$deck = flip_deck($deck);
} else if ( $ops[$i] == 'C' ) {
$deck = cut_deck($deck);
}
}
return $deck;
}
function perfect_deck( $length=52 ) {
$middle = $length/2;
$top_half = '';
$top_card = ord('A');
$bot_half = '';
$bot_card = ord('a');
for ( $i=0; $i<$middle; $i++,$top_card++,$bot_card++ ) {
$top_half .= chr($top_card);
$bot_half .= chr($bot_card);
}
return $top_half . $bot_half;
}
function cut_deck( $deck ) {
$middle = strlen($deck)/2;
return substr($deck,$middle) . substr($deck,0,$middle);
}
function shuffle_deck( $deck ) {
$middle = strlen($deck)/2;
$top_half = substr($deck,0,$middle);
$bot_half = substr($deck,$middle);
$new_deck = '';
for ( $i=0; $i<$middle; $i++ ) {
$new_deck .= $bot_half[$i] . $top_half[$i];
}
return $new_deck;
}
function flip_deck( $deck ) {
return strrev($deck);
}
function score_deck( $deck, $perfect_deck ) {
$score = 0;
$length = strlen($deck);
for ( $i=0; $i<$length; $i++ ) {
if ( $deck[$i] == $perfect_deck[$i] ) {
$score++;
}
}
return $score;
}
function evaluate_deck( $deck ) {
$length = strlen($deck);
$shuffle_limit = modulo_order(2,$length+1);
$perfect_deck = perfect_deck($length);
global $best_ops;
$best_score = 0;
$d = array();
$d['C'] = cut_deck($deck);
$d['F'] = flip_deck($deck);
$d['S'] = shuffle_deck($deck);
$found = FALSE;
while (! $found ) {
$e = array();
// print_r($d);
// echo "\n";
foreach ( $d as $ops => $new_deck ) {
if ( preg_match('/(FC|FS)$/',$ops) ) {
continue;
}
$score = score_deck($new_deck,$perfect_deck);
if ( $score > $best_score ) {
$best_score = $score;
$best_ops = $ops;
}
if ( preg_match('/S{'.$shuffle_limit.'}/',$ops) ) {
continue;
}
$new_op = $ops.'S';
$e[$new_op] = shuffle_deck($new_deck);
if ( $e[$new_op] == $perfect_deck ) {
return $new_op;
}
if (! preg_match('/C$/',$ops) ) {
$new_op = $ops.'C';
$e[$new_op] = cut_deck($new_deck);
if ( $e[$new_op] == $perfect_deck ) {
return $new_op;
}
}
if (! preg_match('/F$/',$ops) ) {
$new_op = $ops.'F';
$e[$new_op] = flip_deck($new_deck);
if ( $e[$new_op] == $perfect_deck ) {
return $new_op;
}
}
}
$d = $e;
}
}
function modulo_order( $a, $n ) {
$pow = 1;
for ( $k=1; $k<=$n; $k++ ) {
$pow *= $a;
if ( $pow%$n == 1 ) {
return $k;
} else if ( $pow%$n == 0 ) {
return $n;
}
}
return $n;
}
?>
Back to results
|
|
