Code of andrei
<?
/*
PHP-Editors.com programming contest
Contest B1 (Flipping Shuflles)
Author: Andrei Gapeyev
E-mail: dp@hot.ee
*/
//(S, C, F) ==> (0, 1, 2).
class Deck
{
var $op_shifts = array();
var $op_shifts_rev = array();
var $op_names = array('S', 'F', 'C');
var $deck;
var $deck_to;
var $length;
var $time = 0;
var $has_flip = false;
function Deck($deck)
{
$this->length = strlen($deck);
$this->deck_to = $this->getDeck($this->length);
$this->deck = $deck;
//create op_shifts array, which reflects, how card will change its place depending on operation made (S, C, F) - (0, 1, 2).
$this->op_shifts = array();
for ($i=0; $i<$this->length ; $i++)
{
$this->op_shifts[$this->cardShuffle($i)][0] = $i;
$this->op_shifts[$this->cardCut($i)][1] = $i;
$this->op_shifts[$this->cardFlip($i)][2] = $i;
$this->op_shifts_rev[$i][0] = $this->cardShuffle($i);
$this->op_shifts_rev[$i][1] = $this->cardCut($i);
$this->op_shifts_rev[$i][2] = $this->cardFlip($i);
}
}
function __construct($deck)
{
$this->Deck($deck);
}
function getDeck($n)
{
$l = '';
$r = '';
for ($i=0; $i<$n/2; $i++)
{
$l = $l.chr(ord('A')+$i);
$r = $r.chr(ord('a')+$i);
}
return $l.$r;
}
function cardShuffle($i)
{
$n = $this->length;
if ($i<$n/2)
{
return $i*2+1;
}
else
{
return ($i-$n/2)*2;
}
}
function deckShuffle($deck)
{
$t = '';
for ($i=0; $i<$this->length; $i++)
$t.= substr($deck, $this->op_shifts[$i][0], 1);
return $t;
}
function deckFlip($deck)
{
$t = '';
for ($i=0; $i<$this->length; $i++)
$t.= substr($deck, $this->op_shifts[$i][2], 1);
return $t;
}
function deckCut($deck)
{
$t = '';
for ($i=0; $i<$this->length; $i++)
$t.= substr($deck, $this->op_shifts[$i][1], 1);
return $t;
}
function cardFlip($i)
{
$n = $this->length;
return $n-$i-1;
}
function cardCut($i)
{
$n = $this->length;
if ($i<$n/2)
{
return $i+$n/2;
}
else
{
return $i-$n/2;
}
}
function applyOperation($deck, $i)
{
$out = '';
for ($j=0; $j<$this->length; $j++)
$out.=substr($deck, $this->op_shifts[$j][$i], 1);
return $out;
}
function shuffleCount()
{
$deck = $this->deckShuffle($this->deck);
$deck_1 = $this->deck;
$deck_2 = $this->deckFlip($this->deck);
$i = 1;
while (
($deck!=$deck_1)
//&& ($deck!=$deck_2)
)
{
if ($deck==$deck_2) {
$this->has_flip = true;
//return $i;
}
$i++;
$deck = $this->deckShuffle($deck);
}
return $i;
}
function start()
{
$timer = $this->startTimer();
$shuffle_circle = $this->shuffleCount();
$level = 0;
$level_size = 1;
$level_start = 0;
$shifts = array(0=>array(
'deck'=>$this->deck,
'path'=>'',
'shuffles'=>0, //to 0 after cut
'cuts'=>0,
'flips'=>0, // to 0 after cut
'last'=>''
));
while (count($shifts))
{
//echo $level.' '.$level_start.' '.$level_size.' '.count($shifts)."\n";
$new_shifts = array();
$i=0;
while (isset($shifts[$i]))
{
$path = $shifts[$i]['path'];
$shuffles = $shifts[$i]['shuffles'];
$cuts = $shifts[$i]['cuts'];
$flips = $shifts[$i]['flips'];
$last = $shifts[$i]['last'];
if ($shifts[$i]['deck'] == $this->deck_to)
{
$time = $this->stopTimer($timer);
//die('FOUND! :'.$shifts[$i]['path'].' Time : '. $time);
die($shifts[$i]['path'].strlen($shifts[$i]['path'])."\n");
}
if (
true
&& ($shuffles<$shuffle_circle-1)
&& (($shuffles<$shuffle_circle/2-1) || (!$this->has_flip))
)
$new_shifts[] = array (
'deck'=>$this->deckShuffle($shifts[$i]['deck']),
'path'=>$shifts[$i]['path'].'S',
'shuffles'=>$shuffles+1,
'cuts'=>0,
'flips'=>$flips,
'last'=>'S'
);
if (
true
&& ($cuts==0)
//&& ($flips>0)
//&& ($last!='C')
/*
&& (
($last=='') ||
($last=='S')
)*/
)
$new_shifts[] = array (
'deck'=>$this->deckCut($shifts[$i]['deck']),
'path'=>$shifts[$i]['path'].'C',
'shuffles'=>0,
'cuts'=>$cuts+1,
'flips'=>$flips,
'last'=>'C'
);
if (
true
//&& !$this->has_flip
&& ($flips==0)
&& (
($last=='') ||
($last=='C')
)
)
$new_shifts[] = array (
'deck'=>$this->deckFlip($shifts[$i]['deck']),
'path'=>$shifts[$i]['path'].'F',
'shuffles'=>$shuffles,
'cuts'=>0,
'flips'=>$flips+1,
'last'=>'F'
);
$i++;
}
$shifts = $new_shifts;
//next level
$level_size = 3*$level_size;
$level_start += $level_size;
$level++;
}
}
function startTimer()
{
return microtime();
}
function stopTimer($timer)
{
list($usec, $sec) = explode(" ",microtime());
$end = ((float)$usec + (float)$sec);
list($usec, $sec) = explode(" ",$timer);
$start = ((float)$usec + (float)$sec);
return $end-$start;
}
}
$fp = fopen('deck.txt', 'r');
$s = fgets($fp, 4096);
fclose($fp);
$s =preg_replace('/\s+.*/', '', $s);
$deck = new Deck($s);
$deck->start();
?>
Back to results
|
|
