Main Menu |
|
|
 |
Forums |
|
|
|
Programming
Contest |
| |
|
Documentation
|
| |
|
Partner
Sites |
|
|
Sponsors |
|
|
|
|
Code of cagret
<?php
/*
* cards.php
* php-editors.com contest - 7th April 2003
* +-----------------------------------+
* | Author: cagrET (Cezary Tomczak) |
* | Email: cagret@yahoo.com |
* | Homepage: http://cagret.prv.pl |
* | Country: Poland |
* +-----------------------------------+
*/
error_reporting(E_ALL);
//set_time_limit(60);
//set_error_handler('my_error_handler');
new Cards;
class Cards
{
var $filename = 'deck.txt';
var $cards; // min: 2 , max: 52 , even number: 2,4,6 ... 50,52
var $perfect; // cards in perfect position
var $cards_op = array(); //operations (CSF)
var $cards_op_id; //current id
var $cards_op_tmp = array(); //temporary
var $cards_tmp; //last shuffle done
var $decks = array(); //combinations of decks
var $len; // length
var $half; // 1/2 length
var $maxshuffle;
var $CutFlip; //cut flip combinations
var $Shuffle; //shuffle combinations
var $time;
function Cards()
{
//init
$this->cards = $this->read($this->filename);
$this->len = strlen($this->cards);
$this->half = $this->len / 2;
$this->perfect = $this->getPerfect($this->half);
$this->maxshuffle = $this->getMaxShuffle($this->half);
//starting
//$this->time_start();
$this->init();
}
function __construct()
{
this->Cards();
}
function init()
{
//print $this->operate_undo('12C23FC1C', 1);
//return;
//print $this->operate('F1C1C1C1C1C', 1);
//return;
//cutflip and shuffle arrays
$this->CutFlip = $this->getCutFlip();
$this->Shuffle = $this->getShuffle();
$this->decks = $this->CutFlip; //creating deck of combinations
$this->try1st(); //try 1st combinations of C , F , CF
$this->CutFlip = $this->getCutFlip2();
$even = false;
while (true) {
if ($even) {
$this->tryCutFlip();
$even = false;
} else {
$this->tryShuffle();
$even = true;
}
}
}
//1st operate
function try1st()
{
foreach($this->decks as $val) {
$this->operate($val);
}
}
//joins deck with parts of CutFlip array
function tryCutFlip()
{
$tmp_decks = $this->decks;
$this->decks = array();
$this->cards_op_tmp = $this->cards_op;
$this->cards_op = array();
foreach($tmp_decks as $key => $val) {
foreach ($this->CutFlip as $val2) {
$this->cards_op_id = $key;
$this->operate_fast($val2, $val);
$this->decks[] = $val . $val2;
}
}
}
//joins deck with parts of Shuffle array
function tryShuffle()
{
$tmp_decks = $this->decks;
$this->decks = array();
$this->cards_op_tmp = $this->cards_op;
$this->cards_op = array();
foreach($tmp_decks as $key => $val) {
foreach($this->Shuffle as $val2) {
$this->cards_op_id = $key;
$this->operate_fast($val2, $val);
$this->decks[] = $val . $val2;
}
}
}
function getCutFlip()
{
return array('', 'F', 'C', 'CF');
}
//there is no sense in repeating 'F' or 'CF'
function getCutFlip2()
{
return array('C');
}
function getShuffle()
{
$len = $this->maxshuffle;
$Shuffle = array();
for($i = 1; $i <= $len; ++$i) {
$Shuffle[] = $i;
}
return $Shuffle;
}
//this is faster cause it adds 1 operation instead of doing all ... (in table is string from similar operation)
//$s - last operation, $s_start - all prevoious ; F1C3C4 ($s_start) 3($s)
function operate_fast($s, $s_start)
{
$tmp = $this->cards_op_tmp[$this->cards_op_id];
switch ($s) {
case 'C':
//CUT
$tmp = substr($tmp, -$this->half) . substr($tmp, 0, $this->half);
break;
case 'F':
//FLIP
$tmp = strrev($tmp);
break;
default:
//SHUFFLE
if ($s == 1) {
$tmp = $this->shuffle($tmp);
$this->cards_tmp = $tmp;
} else {
$tmp = $this->cards_tmp = $this->shuffle($this->cards_tmp);
}
break;
}
//caching results - average 12x times faster with caching
$this->cards_op[] = $tmp;
if ($tmp == $this->perfect) {
$this->finish($s_start . $s);
}
}
//operates on $s = FSS etc.
function operate($s, $return = false)
{
$tmp = $this->cards;
$len = strlen($s);
for($i = 0; $i < $len; ++$i) {
$index = $s{$i};
if (is_numeric($index) && $i < $len-1 && is_numeric($s{$i + 1})) {
$index .= $s{++$i};
}
switch ($index) {
case 'C':
//CUT
$tmp = substr($tmp, -$this->half) . substr($tmp, 0, $this->half);
break;
case 'F':
//FLIP
$tmp = strrev($tmp);
break;
default:
//SHUFFLE x times
//if ($this->count == 12) trigger_error('', E_USER_ERROR);
$tmp = $this->shuffle_x($tmp, $index);
break;
}
}
if ($return) {
return $tmp;
} else {
//operate_fast compatible
$this->cards_op[] = $tmp;
if ($tmp == $this->perfect) {
$this->finish($s);
}
}
}
//FOUND
function finish($s)
{
$s = $this->undo_deck($s);
print $s . strlen($s);
//print '<br /><br />' . $this->time_end();
exit;
}
//translate from our system - change F4C3 to FSSSSCSSS etc.
function undo_deck($s)
{
$len = strlen($s);
$tmp = '';
for ($i = 0; $i < $len; ++$i) {
if (is_numeric($index = $s{$i})) {
if ($i < $len-1 && is_numeric($s{$i + 1})) {
$index .= $s{++$i};
}
$tmp .= str_repeat('S', $index);
} else {
$tmp .= $s{$i};
}
}
return $tmp;
}
// CUT == undo cut x1
function cut($s)
{
return substr($s, -$this->half) . substr($s, 0, $this->half);
}
// SHUFFLE single string (SLOW)
function shuffle($s)
{
$tmp = '';
$b = $this->half;
for ($i = 0; $i < $this->half; ++$i) {
$tmp .= $s{$b++} . $s{$i};
}
return $tmp;
}
// SHUFFLE x times (SLOW)
function shuffle_x($s, $x)
{
$tmp2 = $s;
for ($i = 1; $i <= $x; ++$i) {
$tmp = '';
$a = 0;
$b = $this->half;
for ($ii = 0; $ii < $this->half; ++$ii) {
$tmp .= $tmp2{$b++} . $tmp2{$a++};
}
$tmp2 = $tmp;
}
return $tmp2;
}
// SHUFFLE UNDO (SLOW)
function shuffle_undo($s)
{
$a = '';
$b = '';
for ($x = 0; $x < $this->len; $x += 2) {
$b .= $s{$x};
$a .= $s{$x + 1};
}
return $a . $b;
}
// FLIP == undo flip x1
function flip($s)
{
return strrev($s);
}
// GET PERFECT string ; $deck = $this->half
function getPerfect($deck)
{
$upper = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
$lower = 'abcdefghijklmnopqrstuvwxyz';
return substr($upper, 0, $deck) . substr($lower, 0, $deck);
}
// number of shuffles after which string repeats OR is reversed (flip)
function getMaxShuffle($deck)
{
switch ($deck) {
case 1: return 1;//should 0 but must 1 :-)
case 2: return 1;//3
case 3: return 2;
case 4: return 2;//5
case 5: return 4;//9
case 6: return 5;//11
case 7: return 3;
case 8: return 3;//7
case 9: return 8;//17
case 10: return 5;
case 11: return 10;
case 12: return 9;//19
case 13: return 8;//17
case 14: return 13;//27
case 15: return 4;
case 16: return 4;//9
case 17: return 11;
case 18: return 17;//35
case 19: return 11;
case 20: return 9;//19
case 21: return 6;//13
case 22: return 11;
case 23: return 22;
case 24: return 20;
case 25: return 7;
case 26: return 25;//51
}
}
// READ string from file (and trim)
function read($filename)
{
$fp = fopen($filename, 'r', 0) or exit('couldnt open file');
$data = trim(fread($fp, filesize($filename)));
fclose($fp);
return $data;
}
//FOR TESTING - undo operations
//this is used to create decks that have a solution 100%
function operate_undo($s)
{
$tmp = $this->cards;
//reverse cause undo
$s = strrev($s);
$len = strlen($s);
for ($i = 0; $i < $len; $i++) {
$index = $s{$i};
if (is_numeric($index) && $i < $len-1 && is_numeric($s{$i + 1})) {
$index .= $s{++$i};
}
switch ($s{$i}) {
case 'C':
//CUT (cut = undo cut)
$tmp = $this->cut($tmp);
break;
case 'F':
//FLIP (flip = undo flip)
$tmp = $this->flip($tmp);
break;
default:
//UNDO SHUFFLE x times
for($ii = 1; $ii <= $index; ++$ii) {
$tmp = $this->shuffle_undo($tmp);
}
break;
}
}
return $tmp;
}
// initializing TIME
function time_start()
{
$this->time = $this->get_microtime();
}
// return elapsed TIME - must call time_start() before
function time_end()
{
return ($this->get_microtime() - $this->time);
}
// get microtime
function get_microtime()
{
$mtime = explode(" ", microtime());
return (double)($mtime[1]) + (double)($mtime[0]);
}
// human readable variable
function print_r($var)
{
echo '<pre>';
print_r($var);
echo '</pre>';
exit();
}
}
// ERROR HANDLER - give additional informations about variables
// in actual SCOPE
function my_error_handler($errno, $errmsg, $file, $line, $vars)
{
//limit of 5 errors
static $count;
if (!isset($count)) {
$count = 0;
}
$count++;
if ($count > 5) {
exit;
}
echo '<pre>';
echo "<b>Error:</b> $errmsg \n";
echo "<b>Line:</b> $line\n\n";
print_r($vars);
echo '</pre>';
//when called like this => trigger_error('my error', E_USER_ERROR);
if ($errno == E_USER_ERROR) {
exit();
}
}
?>
Back to results
|
|
|
