[Challenge] zig-zag traversal

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

[Challenge] zig-zag traversal

Post by VladSun »

Another zig-zag scan :)
Implement the following traversal:
http://en.wikipedia.org/wiki/File:JPEG_ZigZag.svg
Input data:

Code: Select all

1  2  3  4  5  6  7  8
9  10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
The output should be a 1D array.

Fastest code needed!
Though it must be data size (8x8 in this particular case) and values independent, the execution time will be measured for processing an 8x8 matrix.
There are 10 types of people in this world, those who understand binary and those who don't
User avatar
daedalus__
DevNet Resident
Posts: 1925
Joined: Thu Feb 09, 2006 4:52 pm

Re: [Challenge] zig-zag traversal

Post by daedalus__ »

screw. that. :D
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

Re: [Challenge] zig-zag traversal

Post by VladSun »

Input data generator.

Code: Select all

<?php
 
define(SIZE, 8 );
 
$data = array();
 
for ($i = 0; $i < SIZE; $i++)
{
    $data[$i] = array();
    for ($j = 0; $j < SIZE; $j++)
    {
        $data[$i][$j] = $i*SIZE + $j + 1;
    }
}
 
print_r($data);
 
There are 10 types of people in this world, those who understand binary and those who don't
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

Re: [Challenge] zig-zag traversal

Post by VladSun »

Code: Select all

<?php
 
header('Content-type: text/plain');
 
class ZigZagScanner
{
    public $data        = null;
    public $debugData   = null;
    public $output      = array();
    public $size        = 8;
 
    public function  __construct()
    {
        $this->generateData();
    }
 
    public function generateData()
    {
        $this->data = array();
        $this->debugData = array();
 
        for ($i = 0; $i < $this->size; $i++)
        {
            $this->data[$i] = array();
            $this->debugData[$i] = array();
            for ($j = 0; $j < $this->size; $j++)
            {
                $this->data[$i][$j] = $i*$this->size + $j + 1;
                $this->debugData[$i][$j] = '';
            }
        }
    }
 
    public function addValue($x, $y)
    {
        array_push($this->output, $this->data[$x][$y]);
        $this->debugData[$x][$y] = count($this->output);
    }
 
    public function traversal()
    {
        $this->addValue(0, 0);
        $this->subtraversal(0, 0);
    }
 
    protected function subtraversal($x, $y)
    {
        $cx = 0;
        $cy = 0;
        
        if ($y == 0 && $x < $this->size - 1)
        {
            $x++;
            for($cx = $x, $cy = $y; $cx >= 0; $cx--, $cy++)
                $this->addValue($cy, $cx);
            $this->subtraversal($cx+1, $cy-1);
        }
        else if ($x == 0 && $y < $this->size - 1)
        {
            $y++;
            for($cx = $x, $cy = $y; $cy >= 0; $cy--, $cx++)
                $this->addValue($cy, $cx);
            $this->subtraversal($cx-1, $cy+1);
        }
        else if ($y == $this->size - 1 && $x < $this->size - 1)
        {
            $x++;
            for($cx = $x, $cy = $y; $cx < $this->size; $cy--, $cx++)
                $this->addValue($cy, $cx);
            $this->subtraversal($cx-1, $cy+1);
        }
        else if ($x == $this->size - 1 && $y < $this->size - 1)
        {
            $y++;
            for($cx = $x, $cy = $y; $cy < $this->size; $cx--, $cy++)
                $this->addValue($cy, $cx);
            $this->subtraversal($cx+1, $cy-1);
        }
    }
 
    public function printDebugData()
    {
        for ($i =0; $i < $this->size; $i++)
        {
            for ($j =0; $j < $this->size; $j++)
                echo $this->debugData[$i][$j] < 10 ? $this->debugData[$i][$j].'   ' : $this->debugData[$i][$j].' ';
            echo "\n";
        }
    }
 
    public function printOutputData()
    {
        echo implode(" ", $this->output)."\n\n";
    }
}
 
 
$scanner = new ZigZagScanner();
 
$scanner->traversal();
 
$scanner->printOutputData();
$scanner->printDebugData();

Code: Select all

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
 
1  2  6  7  15 16 28 29 
3  5  8  14 17 27 30 43 
4  9  13 18 26 31 42 44 
10 12 19 25 32 41 45 54 
11 20 24 33 40 46 53 55 
21 23 34 39 47 52 56 61 
22 35 38 48 51 57 60 62 
36 37 49 50 58 59 63 64
My solution - your turn :)

PS: My solution is not optimized for speed - it's just an example solution.
There are 10 types of people in this world, those who understand binary and those who don't
josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Re: [Challenge] zig-zag traversal

Post by josh »

I don't get it, why wouldn't the solution start with "1,2,3" if I were to follow a "zig zag"? If I copy pasted your code and removed the "test code" from production would that count as a valid submission? lol

Shouldn't it hit 3,1 before 2,2 then 1,3?

In your example it jumps entire rows which I don't get.
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

Re: [Challenge] zig-zag traversal

Post by VladSun »

I don't get it :)
The $debugData (2D array) contains the way I traversal the 2D input array (that is the $data). Every (x,y) value is an index to the $output 1D array.

The $output (1D) array is the expected output from the zig-zag scan as shown in the wiki figure.
There are 10 types of people in this world, those who understand binary and those who don't
josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Re: [Challenge] zig-zag traversal

Post by josh »

See screenshot.

Expected output
1,2,3,4,5,6,7,8...

Actual output
1, 2, 9, 17, 10....

why is that not a bug? Or did you just make a confusing post

Edit: yeah oh I see why now. I thought your debug "grid" was the "input" grid because nothing was labeled.
Attachments
aobfpfbr.gif
aobfpfbr.gif (113.95 KiB) Viewed 9682 times
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

Re: [Challenge] zig-zag traversal

Post by VladSun »

Yes, that's what debugData is for :)
There are 10 types of people in this world, those who understand binary and those who don't
josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Re: [Challenge] zig-zag traversal

Post by josh »

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.
User avatar
daedalus__
DevNet Resident
Posts: 1925
Joined: Thu Feb 09, 2006 4:52 pm

Re: [Challenge] zig-zag traversal

Post by daedalus__ »

lol recommend a math book?

yeah im laughing but it aint funny and im not kidding.
Post Reply