Here's my entry. I wrote a test to cover your existing code and refactored it. I fixed a few issues like your x & y values being backwards. It should be a little faster, as well as hopefully a little easier to read. Your class was pretty solid though, it was hard to find anything that I could improve upon, but I still had a few nit-picks
Code: Select all
class ZigZagScanner
{
public $data = array();
public $output = array();
public $size = 8;
public function __construct( $data )
{
$this->data = $data;
}
public function getOutputData()
{
return implode(" ", $this->output);
}
public function traversal()
{
$this->appendResult(0, 0);
$this->recursivetraversal(0, 0);
}
protected function recursivetraversal($row, $column)
{
$x = 0;
$y = 0;
$secondToLast = $this->size - 1;
$rowIsBeforeSecondToLast = $row < $secondToLast;
$columnIsBeforeSecondToLast = $column < $secondToLast;
if ($column == 0 && $rowIsBeforeSecondToLast )
{
$row++;
for($x = $row, $y = $column; $x >= 0; $x--, $y++)
{
$this->appendResult($x, $y);
}
$this->recursivetraversal($x+1, $y-1);
}
else if ($row == 0 && $columnIsBeforeSecondToLast )
{
$column++;
for($x = $row, $y = $column; $y >= 0; $y--, $x++)
{
$this->appendResult($x, $y);
}
$this->recursivetraversal($x-1, $y+1);
}
else if ($column == $secondToLast && $rowIsBeforeSecondToLast )
{
$row++;
for($x = $row, $y = $column; $x < $this->size; $y--, $x++)
{
$this->appendResult($x, $y);
}
$this->recursivetraversal($x-1, $y+1);
}
else if ($row == $secondToLast && $columnIsBeforeSecondToLast )
{
$column++;
for($x = $row, $y = $column; $y < $this->size; $x--, $y++)
{
$this->appendResult($x, $y);
}
$this->recursivetraversal($x+1, $y-1);
}
}
protected function appendResult($x, $y)
{
array_push($this->output, $this->data[$y][$x]);
}
}
The test
Code: Select all
function testGrid()
{
$input = array(
array(1, 2, 3, 4, 5, 6, 7, <!-- s8) --><img src=\"{SMILIES_PATH}/icon_cool.gif\" alt=\"8)\" title=\"Cool\" /><!-- s8) -->,
array(9, 10, 11, 12, 13, 14, 15, 16),
array(17, 18, 19, 20, 21, 22, 23, 24),
array(25, 26, 27, 28, 29, 30, 31, 32),
array(33, 34, 35, 36, 37, 38, 39, 40),
array(41, 42, 43, 44, 45, 46, 47, 48),
array(49, 50, 51, 52, 53, 54, 55, 56),
array(57, 58, 59, 60, 61, 62, 63, 64)
);
$grid = new ZigZagScanner( $input );
$grid->traversal();
$output = '1 2 9 17 10 3 4 11 18 25 33 26 19 12 5 6 13 20 27 34 41 49 42 35 28 21 14 7 8 15 22 29 36 43 50 57 58 51 44 37 30 23 16 24 31 38 45 52 59 60 53 46 39 32 40 47 54 61 62 55 48 56 63 64';
var_dump( $output == $grid->getOutputData() );
//var_dump( $grid->getOutputData() );
}
testGrid();
I worked in small incremental steps. A few times the tests failed and I had to back up. After a few times backing out I finally started to understand the code and was able to arrive at this.