Page 1 of 1

[Challenge] zig-zag traversal

Posted: Fri Dec 18, 2009 7:17 am
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.

Re: [Challenge] zig-zag traversal

Posted: Fri Dec 18, 2009 1:24 pm
by daedalus__
screw. that. :D

Re: [Challenge] zig-zag traversal

Posted: Sat Dec 19, 2009 4:33 am
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);
 

Re: [Challenge] zig-zag traversal

Posted: Sat Dec 19, 2009 5:42 am
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.

Re: [Challenge] zig-zag traversal

Posted: Sat Dec 19, 2009 8:53 am
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.

Re: [Challenge] zig-zag traversal

Posted: Sun Dec 20, 2009 4:47 am
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.

Re: [Challenge] zig-zag traversal

Posted: Sun Dec 20, 2009 7:09 am
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.

Re: [Challenge] zig-zag traversal

Posted: Sun Dec 20, 2009 7:13 am
by VladSun
Yes, that's what debugData is for :)

Re: [Challenge] zig-zag traversal

Posted: Sun Dec 20, 2009 7:44 am
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.

Re: [Challenge] zig-zag traversal

Posted: Sun Dec 20, 2009 8:15 pm
by daedalus__
lol recommend a math book?

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