Main Menu |
|
|
 |
Forums |
|
|
|
Programming
Contest |
| |
|
Documentation
|
| |
|
Partner
Sites |
|
|
Sponsors |
|
|
|
|
Code of arvo
<?php
/*
Script By : Arvo Huru - <daredjevel@nodream.org>
About the script:
I was not able to find a good way to determin how many levels I could use
from the time a shuffle() and cut() takes.
The problem was much due to I couldn't find a good equation to use.
A problem that arises from this is that since no info about the speed of the
compuers this script would be run on I had no possibilities to test how many
levels in theory this script could use on the scoring-macines.
My computer is not too fast (PII 350) But if you run 21 levels it takes about
37 seconds, while on 22 levels it takes about 58 seconds. Another thing that
makes determing the number of levels dificult. (This is on a 52 card deck)
I could make an timechek to find out when my script was about to run out of time,
but what time to use is hard to find, eg. lets say it has run for 20 sec and hits the
50th level and I say this is max levels now. Then my sript has only checked the
first possible way to 50th level, and has ((2^1 + 2^2 + 2^3 .... 2^50) - 1) posibilities
left to try (The formula is not 100% correct due to the max number of shuffles
possible, solution found and so on. And the posibility I have missunderstood/typoed/other
the equation) something the reminding 40 sec wont be able to do.
A max of 100 levels was set on this contest (something I seriously doupt will
be possible to complete in 60 sec. But as Joe Dirt says : "You can not have 'no'
in your hart". So maby I can think out something...)
So here is what I did : I set the max levels to 22. If no solution is found I set the
solution to FSS - This becouse checking if each tried solution has more correct
"card" locations then the others takes too long time.
So all I can hope for is that my script has the luck and skill to come up amongst
the best.
One small cange made : I created an array containing max moves for each type of
deck (number of cards). These values are found out from my computers limitations.
This also include a maximum numbers of operations needed to complete deck thus
speeding up the prosess also.
The latter statement is only true for decks whit 2 cards, which isn't needed since F
will always be found as solution, could make an if statement :
if($cards == 2){
... somethig ...
$data->solution = "F";
finalOutput();
... somethig ...
}
else{
... somethig ...
// do the normal thing.
... somethig ...
}
but why care. The array function as a max levels it can do whitout timing out. I have added
a little room for faster computers as some exceeds the max-time by maximum 10 sec. I belive
this wont result in a timeout on one of the scoring machines becouse:
1. Their machines are probably faster than mine.
2. The chance a deck of that size whit a solution greater than 23 moves are small.
3. __________________________________________ ( fill in the blank )
One problem using the array is that most decks I created had a solution on up to 25 moves
regardless of "scrambeling". This resulting in the posibillity to get no answer becomes greater
on all decks.
Decks whit 4 and 6 cards I've set the max levls to 18 since this is enough to check all posible
scrablings these decks can have.
There were ofcourse decks whit more than 25 moves, and there was decks I couldn't solve, or
rather didn't care to wait 30 minutes for it to complete (the 30 min time it a number taken out of the air).
I know I could have increased the levels by atleast one whitout problems. But I don't want to gamble whit
it.
I was going to submit this the 6th but I saw the contest was extended, so I used this last time to try to improve
my script..... couldn't find any... unfortionatly..
Now when my script is submitted I can only wait and hope it does well...
Good luck to my script...
*/
$deck = "";
$solution = "";
$flip_solution = "";
$cards = 0; // Number of cards in play.
$deck_cut = 0; // $cards / 2 (cut-point)
$chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
$max_shuffle_array = array();
$max_move_array = array();
loadDeck();
runTree();
finalOutput();
function finalOutput(){
global $data;
if(!$data->solution){
echo "FS2";
}
else{
echo "$data->solution" . strlen($data->solution);
}
}
function setVariables(){
global $max_shuffle_array, $max_move_array;
// Max number of Shuffles before deck enetrs it's original state.
$max_shuffle_array[2] = 2;
$max_shuffle_array[4] = 3;
$max_shuffle_array[6] = 2;
$max_shuffle_array[8] = 5;
$max_shuffle_array[10] = 9;
$max_shuffle_array[12] = 11;
$max_shuffle_array[14] = 3;
$max_shuffle_array[16] = 7;
$max_shuffle_array[18] = 17;
$max_shuffle_array[20] = 5;
$max_shuffle_array[22] = 10;
$max_shuffle_array[24] = 19;
$max_shuffle_array[26] = 17;
$max_shuffle_array[28] = 27;
$max_shuffle_array[30] = 4;
$max_shuffle_array[32] = 9;
$max_shuffle_array[34] = 11;
$max_shuffle_array[36] = 35;
$max_shuffle_array[38] = 11;
$max_shuffle_array[40] = 19;
$max_shuffle_array[42] = 13;
$max_shuffle_array[44] = 11;
$max_shuffle_array[46] = 22;
$max_shuffle_array[48] = 20;
$max_shuffle_array[50] = 7;
$max_shuffle_array[52] = 51;
// Max number of branches to prevent timeout
$max_move_array[2] = 1;
$max_move_array[4] = 18;
$max_move_array[6] = 18;
$max_move_array[8] = 24;
$max_move_array[10] = 24;
$max_move_array[12] = 24;
$max_move_array[14] = 28;
$max_move_array[16] = 24;
$max_move_array[18] = 23;
$max_move_array[20] = 24;
$max_move_array[22] = 23;
$max_move_array[24] = 23;
$max_move_array[26] = 23;
$max_move_array[28] = 23;
$max_move_array[30] = 25;
$max_move_array[32] = 23; // Almost (62 sec)
$max_move_array[34] = 23; // Almost (66 sec)
$max_move_array[36] = 23; // Almost (70 sec)
$max_move_array[38] = 22; // 44 sec
$max_move_array[40] = 22; // 46 sec
$max_move_array[42] = 22; // 48 sec
$max_move_array[44] = 22; // 48.5 sec
$max_move_array[46] = 22; // 51 sec
$max_move_array[48] = 22; // 52.5 sec
$max_move_array[50] = 22; // 46.2 sec
$max_move_array[52] = 22; // 55.5 sec
}
// Loads the deck and sets various settings
function loadDeck(){
global $deck, $data, $deck_cut, $cards, $chars, $max_shuffle_array, $max_move_array;
$filename = "deck.txt";
$handle = fopen($filename, "rb");
$deck = fread($handle, filesize($filename));
fclose ($handle);
$deck = trim($deck);
$cards = strlen($deck);
$deck_cut = ($cards / 2);
setVariables();
generateSolutionVars();
$data->max_shuffles = $max_shuffle_array[$cards];
$data->moves = $max_move_array[$cards];
$data->solution = "";
}
function generateSolutionVars(){
global $solution, $flip_solution, $deck_cut, $chars;
$solv = substr($chars, 0, $deck_cut);
$solution = $solv . strtolower($solv);
$flip_solution = flipDeck($solution);
}
function runTree(){
global $deck, $data;
buildTree($deck);
}
function buildTree($deck_y, $move_this=0, $moves=0, $solution_y="", $same_move_count=0){
global $data, $solution, $flip_solution, $nodes;
if($moves === $data->moves){
return;
}
else if($solution === $deck_y){
$data->solution = $solution_y;
$data->moves = $moves;
return;
}
$next_moves = ($moves + 1);
// Check for flip
if($flip_solution === $deck_y){
$data->solution = "F" . $solution_y;
$data->moves = $next_moves;
}
switch($move_this){
case 0:
$next_solution = $solution_y . "S";
buildTree(shuffleDeck($deck_y), 2, $next_moves, $next_solution, $same_move_count);
$next_solution = $solution_y . "C";
buildTree(cutDeck($deck_y), 1, $next_moves, $next_solution);
break;
case 1: // CUT
$next_solution = $solution_y . "S";
buildTree(shuffleDeck($deck_y), 2, $next_moves, $next_solution, $same_move_count);
break;
case 2: // SHUFFLE
$next_solution = $solution_y . "C";
buildTree(cutDeck($deck_y), 1, $next_moves, $next_solution);
$same_move_count++;
if($same_move_count < $data->max_shuffles){
$next_solution = $solution_y . "S";
buildTree(shuffleDeck($deck_y), 2, $next_moves, $next_solution, $same_move_count);
}
break;
default:
break;
}
return;
}
function cutDeck($deck){
global $deck_cut;
return substr($deck, $deck_cut, $deck_cut) . substr($deck, 0, $deck_cut);
}
function shuffleDeck($deck){
global $deck_cut;
$temp = "";
for($i=0; $i<$deck_cut; $i++){
$temp .= $deck{($deck_cut + $i)} . $deck{$i};
}
return $temp;
}
function flipDeck($deck){
return strrev($deck);
}
?>
Back to results
|
|
|
