Main Menu |
|
|
 |
Forums |
|
|
|
Programming
Contest |
| |
|
Documentation
|
| |
|
Partner
Sites |
|
|
Sponsors |
|
|
|
|
Code of kerry
<?php
// Cobbled together by Kerry Torchia
// www.ImaginaryWorld.co.uk
//set_time_limit(0);
//
// FUNCTION DEFINITIONS
//
// functions to create a deck
function create_upper($num) {
$chr=65;
for($i=0; $i<$num; $i++){
$arr[$i] = chr($chr);
$chr++;
}
return $arr;
}
function create_lower($num) {
$chr=97;
for($i=0; $i<$num; $i++){
$arr[$i] = chr($chr);
$chr++;
}
return $arr;
}
function cut($ar) {
$count = count($ar);
$half = $count/2;
for($i=0; $i<$half; $i++) {
$arr1[$i] = $ar[$i];
}
$j=0;
for($i=$half; $i<$count; $i++){
$arr2[$j] = $ar[$i];
$j++;
}
return array_merge($arr2, $arr1);
}
function flip($ar){
$arr1 = array_reverse($ar);
return $arr1;
}
function shuff($ar){
$count = count($ar);
$half = $count/2;
$mc = 0;
for($i=0; $i<$half; $i++) {
$arr1[$mc] = $ar[$half + $i];
$mc++;
$arr1[$mc] = $ar[$i];
$mc++;
}
return $arr1;
}
// function to display a deck
function displayDeck($deck){
$count = count($deck);
$resTXT = "";
For ($i = 0; $i < $count; $i++){
$resTXT .= $deck[$i];
}
return $resTXT;
}
function getmicrotime(){
list($usec, $sec) = explode(" ",microtime());
return ((float)$usec + (float)$sec);
}
function inTree($current, $tree){
$found = false;
$count = count($tree);
for ($i=0;$i<$count;$i++){
if ($current == $tree[$i]){
$found = true;
break;
}
}
return $found;
}
function bestNode($target, $tree){
// target is the node we are searching for
// tree is all the nodes we have found so far
$count = count($tree);
$num_chars = count($target);
$score = 0;
$hiscore = 0;
$best_node = 0;
for ($nodeid=0; $nodeid < $count; $nodeid++){
for ($charid=0; $charid < $num_chars; $charid++){
If ($tree[$nodeid][$charid] == $target[$charid]){
$score++;
}
}
If ($score > $hiscore){
$hiscore = $score;
$best_node = $nodeid;
}
$score = 0;
}
return $best_node;
}
function opsToPerform($str){
// Determines which operations to perform on this node based on its history
// e.g. If the last move was a CUT then no need to apply another CUT
$stringLength = strlen($str);
// cs-1, fs-2. fsc-3
If ($stringLength > 0){
$temp = $stringLength - 1;
switch(substr($str, $temp)){
case 'F':
return 1;
break;
case 'C':
return 2;
break;
}
}
If ($stringLength > 2){
$temp = $stringLength - 3;
switch(substr($str, $temp))
{
case 'FCF':
return 2;
break;
case 'CFC':
return 1;
break;
}
}
return 3;
}
function sortDeck($treeData, $opsData, $completedDeck){
$time_start = getmicrotime();
$totalBranches = count($treeData);
$searching = true;
$index = 0;
$found = 0;
while (($searching) AND ($index < $totalBranches) AND ((getmicrotime() - $time_start) < 54.0)){
//$elapsed = getmicrotime() - $time_start;
$code = opsToPerform($opsData[$index]);
//print $index . displayDeck($treeData[$index]) . " " . $opsData[$index] . " time: $elapsed \n";
switch($code){
case 1:
$tempNode = shuff($treeData[$index]);
if (!inTree($tempNode, $treeData)){
// Add node to the tree
$treeData[$totalBranches] = $tempNode;
$opsData[$totalBranches] = $opsData[$index] . 'S';
// Update the total num of nodes
$totalBranches++;
if ($tempNode == $completedDeck){
$searching = false;
$found = $totalBranches;
break;
}
}
$tempNode = cut($treeData[$index]);
if (!inTree($tempNode, $treeData)){
// Add node to the tree
$treeData[$totalBranches] = $tempNode;
$opsData[$totalBranches] = $opsData[$index] . 'C';
// Update the total num of nodes
$totalBranches++;
if ($tempNode == $completedDeck){
$searching = false;
$found = $totalBranches;
break;
}
}
break;
case 2:
$tempNode = shuff($treeData[$index]);
if (!inTree($tempNode, $treeData)){
// Add node to the tree
$treeData[$totalBranches] = $tempNode;
$opsData[$totalBranches] = $opsData[$index] . 'S';
// Update the total num of nodes
$totalBranches++;
if ($tempNode == $completedDeck){
$searching = false;
$found = $totalBranches;
break;
}
}
$tempNode = flip($treeData[$index]);
if (!inTree($tempNode, $treeData)){
// Add node to the tree
$treeData[$totalBranches] = $tempNode;
$opsData[$totalBranches] = $opsData[$index] . 'F';
// Update the total num of nodes
$totalBranches++;
if ($tempNode == $completedDeck){
$searching = false;
$found = $totalBranches;
break;
}
}
break;
case 3:
$tempNode = shuff($treeData[$index]);
if (!inTree($tempNode, $treeData)){
// Add node to the tree
$treeData[$totalBranches] = $tempNode;
$opsData[$totalBranches] = $opsData[$index] . 'S';
// Update the total num of nodes
$totalBranches++;
if ($tempNode == $completedDeck){
$searching = false;
$found = $totalBranches;
break;
}
}
$tempNode = cut($treeData[$index]);
if (!inTree($tempNode, $treeData)){
// Add node to the tree
$treeData[$totalBranches] = $tempNode;
$opsData[$totalBranches] = $opsData[$index] . 'C';
// Update the total num of nodes
$totalBranches++;
if ($tempNode == $completedDeck){
$searching = false;
$found = $totalBranches;
break;
}
}
$tempNode = flip($treeData[$index]);
if (!inTree($tempNode, $treeData)){
// Add node to the tree
$treeData[$totalBranches] = $tempNode;
$opsData[$totalBranches] = $opsData[$index] . 'F';
// Update the total num of nodes
$totalBranches++;
if ($tempNode == $completedDeck){
$searching = false;
$found = $totalBranches;
break;
}
}
break;
}
if ($searching){
$index++;
}
}
$time_end = getmicrotime();
$time = $time_end - $time_start;
$timePassed = round ($time, 5);
if ($found == 0){
$found = bestNode($completedDeck, $treeData);
} else {
$found--;
}
print $opsData[$found] . strlen($opsData[$found]);
//print "\n $timePassed";
//print "\nDeck = " . displayDeck($treeData[$found]);
}
//
// MAIN PROGRAM
//
// Load data from deck.txt
$fp = fopen("deck.txt", "r");
$content = fgets($fp, 4096);
$num_of_kars = strlen($content);
$initialDeck = array();
for ($t=0; $t<$num_of_kars; $t++){
$initialDeck[$t] = substr($content,$t,1);
}
fclose ($fp);
// create the array structure for a sorted deck
$num_of_chars = count($initialDeck);
$num_of_elements = $num_of_chars/2;
$targetDeck = array_merge(create_upper($num_of_elements), create_lower($num_of_elements));
// Array of strings to store the "FF", "FC", "SSC" history for each node\branch
$operations = array("");
// 2D Array of Array of Chars for the results of each opration...er, i think?
$results = array($initialDeck);
// pass all this info to my sortDeck
sortDeck($results, $operations, $targetDeck);
?>
Back to results
|
|
|
