Zig-zag scan an N x N array
PhpArraysAlgorithmZigzagPhp Problem Overview
I have a simple array. The array length always has a square root of an integer. So 16, 25, 36 etc.
$array = array('1', '2', '3', '4' ... '25');
What I do, is arrange the array with HTML so that it looks like a block with even sides.
What I want to do, is sort the elements, so that when I pass the JSON encoded array to jQuery, it will iterate the array, fade in the current block, and so I'd get a sort of wave animation. So I'd like to sort the array kind of like this
So my sorted array would look like
$sorted = array('1', '6', '2', '3', '7', '11', '16, '12' .. '25');
Is there way to do so?.. Thanks
Php Solutions
Solution 1 - Php
Very cool question. Here's an analysis and an algorithm.
A key advantage to using this algorithm is that it's all done using simple integer calculations; it has no "if" statements and therefore no branches, which means if it were compiled, it would execute very quickly even for very large values of n. This also means it can be easily parallelized to divide the work across multiple processors for very large values of n.
Consider an 8x8 grid (here, the input is technically n = 64, but for simplicity in the formulas below I'll be using n = 8) following this zigzag pattern, like so (with 0-indexed row and column axis):
[ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7]
[ 0] 1 3 4 10 11 21 22 36
[ 1] 2 5 9 12 20 23 35 37
[ 2] 6 8 13 19 24 34 38 49
[ 3] 7 14 18 25 33 39 48 50
[ 4] 15 17 26 32 40 47 51 58
[ 5] 16 27 31 41 46 52 57 59
[ 6] 28 30 42 45 53 56 60 63
[ 7] 29 43 44 54 55 61 62 64
First notice that the diagonal from the lower left (0,7) to upper right (7,0) divides the grid into two nearly-mirrored components:
[ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7]
[ 0] 1 3 4 10 11 21 22 36
[ 1] 2 5 9 12 20 23 35
[ 2] 6 8 13 19 24 34
[ 3] 7 14 18 25 33
[ 4] 15 17 26 32
[ 5] 16 27 31
[ 6] 28 30
[ 7] 29
and
[ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7]
[ 0] 36
[ 1] 35 37
[ 2] 34 38 49
[ 3] 33 39 48 50
[ 4] 32 40 47 51 58
[ 5] 31 41 46 52 57 59
[ 6] 30 42 45 53 56 60 63
[ 7] 29 43 44 54 55 61 62 64
You can see that the bottom-right is just the top-left mirrored and subtracted from the square plus 1 (65 in this case).
If we can calculate the top-left portion, then the bottom-right portion can easily be calculated by just taking the square plus 1 (n * n + 1) and subtracting the value at the inverse coordinates (value(n - x - 1, n - y - 1)).
As an example, consider an arbitrary pair of coordinates in the bottom-right portion, say (6,3), with a value of 48. Following this formula that would work out to (8 * 8 + 1) - value(8 - 6 - 1, 8 - 3 - 1), simplified to 65 - value(1, 4). Looking at the top-left portion, the value at (1,4) is 17. And 65 - 17 == 48.
But we still need to calculate the top-left portion. Note that this can also be further sub-divided into two overlapping components, one component with the numbers increasing as you head up-right:
[ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7]
[ 0] 3 10 21 36
[ 1] 2 9 20 35
[ 2] 8 19 34
[ 3] 7 18 33
[ 4] 17 32
[ 5] 16 31
[ 6] 30
[ 7] 29
And one component with the numbers increasing as you head down-left:
[ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7]
[ 0] 1 4 11 22
[ 1] 5 12 23
[ 2] 6 13 24
[ 3] 14 25
[ 4] 15 26
[ 5] 27
[ 6] 28
[ 7]
The former can also be defined as the numbers where the sum of the coordinates (x + y) is odd, and the latter defined as the numbers where the sum of the coordinates is even.
Now, the key insight here is that we are drawing triangles here, so, not suprisingly, the Triangular Numbers play a prominent role here. The triangle number sequence is: 1, 3, 6, 10, 15, 21, 28, 36, ...
As you can see, in the odd-sum component, every other triangular number starting with 3 appears in the first row (3, 10, 21, 36), and in the even-sum component, every other triangular number starting with 1 appears in the first column (1, 6, 15, 28).
Specifically, for a given coordinate pair (x,0) or (0,y) the corresponding triangle number is triangle(x + 1) or triangle(y + 1).
And the rest of the graph can be computed by incrementally subtracting from these triangular numbers up or down the diagonals, which is equivalent to subtracting the given row or column number.
Note that a diagonal can be formally defined as the set of all cells with a given sum of coordinates. For example, the diagonal with coordinate sum 3 has coordinates (0,3), (1,2), (2,1), and (3,0). So a single number defines each diagonal, and that number is also used to determine the starting triangular number.
So from simple inspection, the formula to calculate the the odd-sum component is simply:
triangle(x + y + 1) - y
And the formula to calculate the even-sum component is simply:
triangle(x + y + 1) - x
And the well-known formula for triangle numbers is also simple:
triangle(n) = (n * (n + 1)) / 2
So, the algorithm is:
- Initialize an n x n array, where n is the square root of the input size.
- Calculate the indexes for the even-summed coordinates of
the top-left portion. This can be accomplished by nesting two loops, an
outer loop "y going from 0 to n - 1" and an inner loop "x going from y % 2 to y in steps of 2" (by bounding x on the the current y, we only look at the top-left portion, as desired, and by starting at y % 2 and going in steps of 2 we only get the even-summed coordinates). The loop indexes can be plugged into the formula above to get the results.
value[x, y] = triangle(x + y + 1) - x. - Calculate the indexes for the odd-summed
coordinates of the top-left portion. This can be accomplished with
similar loops except the inner loop would be "x going from y % 2 + 1 to y in steps of 2", to only get the odd-summed coordinates.
value[x, y] = triangle(x + y + 1) - y. - Calculate the
indexes for the bottom-right portion by simple subtraction from
n * n + 1as described in the first part of this post. This can be done with two nested loops counting backwards (and bounding the inner one on the outer one to only get the bottom-right portion).value[x, y] = (n * n + 1) - value[n - x - 1, n - y - 1]. - Flatten the grid out into an array (lining up all the rows) and then transform the given input (of size n * n) to output by using the numbers generated in the grid as new indices.
Solution 2 - Php
Here's mine.
function waveSort(array $array) {
$dimension = pow(count($array),0.5);
if((int)$dimension != $dimension) {
throw new InvalidArgumentException();
}
$tempArray = array();
for($i = 0; $i < $dimension; $i++) {
$tempArray[] = array_slice($array,$i*$dimension,$dimension);
}
$returnArray = array();
for($i = 0; $i < $dimension * 2 -1; $i++) {
$diagonal = array();
foreach($tempArray as $x => $innerArray) {
if($i - $x >= 0 && $i - $x < $dimension) {
$diagonal[] = $innerArray[$i - $x];
}
}
if($i % 2 == 1) {
krsort($diagonal);
}
$returnArray = array_merge($returnArray,$diagonal);
}
return $returnArray;
}
Usage:
<?php
$a = range(1,25);
var_dump(waveSort($a));
Output
array(25) {
[0]=>
int(1)
[1]=>
int(6)
[2]=>
int(2)
[3]=>
int(3)
[4]=>
int(7)
[5]=>
int(11)
[6]=>
int(16)
[7]=>
int(12)
[8]=>
int(8)
[9]=>
int(4)
[10]=>
int(5)
[11]=>
int(9)
[12]=>
int(13)
[13]=>
int(17)
[14]=>
int(21)
[15]=>
int(22)
[16]=>
int(18)
[17]=>
int(14)
[18]=>
int(10)
[19]=>
int(15)
[20]=>
int(19)
[21]=>
int(23)
[22]=>
int(24)
[23]=>
int(20)
[24]=>
int(25)
}
Solution 3 - Php
Although there are already many solutions to this question, this is mine:
The main feature that differentiates it from the other solutions:
- Only a single loop of complexity O(n)
- Only primitive (integer) temporary variables
The source:
<?php
function zigzag($input)
{
$output = array();
$inc = -1;
$i = $j = 0;
$steps = 0;
$bounds = sqrt(sizeof($input));
if(fmod($bounds, 1) != 0)
{
die('Matrix must be square');
}
while($steps < sizeof($input))
{
if($i >= $bounds) // bottom edge
{
$i--;
$j++;
$j++;
$inc = 1;
}
if($j >= $bounds) // right edge
{
$i++;
$i++;
$j--;
$inc = -1;
}
if($j < 0) // left edge
{
$j++;
$inc = 1;
}
if($i < 0) // top edge
{
$i++;
$inc = -1;
}
$output[] = $input[$bounds * $i + $j];
$i = $i - $inc;
$j = $j + $inc;
$steps++;
}
return $output;
}
$a = range(1,25);
var_dump(zigzag($a));
By the way, this sort of algorithm is called "zig zag scan" and is being used heavily for JPEG and MPEG coding.
Solution 4 - Php
With a single loop and taking advantage of the simetry and with no sorts:
function waveSort(array $array) {
$n2=count($array);
$n=sqrt($n2);
if((int)$n != $n) throw new InvalidArgumentException();
$x=0; $y=0; $dir = -1;
$Result = array_fill(0, $n2, null);
for ($i=0; $i < $n2/2; $i++) {
$p=$y * $n +$x;
$Result[$i]=$array[$p];
$Result[$n2-1-$i]=$array[$n2-1-$p];
if (($dir==1)&&($y==0)) {
$x++;
$dir *= -1;
} else if (($dir==-1)&&($x==0)) {
$y++;
$dir *= -1;
} else {
$x += $dir;
$y -= $dir;
}
}
return $Result;
}
$a = range(1,25);
var_dump(waveSort($a));
Solution 5 - Php
I wrote it in C# so didn't compile/parse it in PHP but this logic should work:
List<long> newList = new List<long>();
double i = 1;
double root = Math.Sqrt(oldList.Count);
bool direction = true;
while (newList.Count < oldList.Count)
{
newList.Add(oldList[(int)i - 1]);
if (direction)
{
if (i + root > root * root)
{
i++;
direction = false;
}
else if (i % root == 1)
{
i += 5;
direction = false;
}
else
{
i += root - 1;
}
}
else
{
if (i - root <= 0)
{
direction = true;
if (i % root == 0)
{
i += root;
}
else
{
i++;
}
direction = true;
}
else if (i % root == 0)
{
direction = true;
i += root;
}
else
{
i += 1 - root;
}
}
}
the PHP version would look something like this:
$oldList = ...
$newList = [];
$i = 1;
$root = sqrt(Count($oldList);
$direction = true;
while (count($newList) < count($oldList)
{
$newList[] = $oldList[$i - 1];
if ($direction)
{
if ($i + $root > $root * $root)
{
$i++;
$direction = false;
}
else if ($i % $root == 1)
{
$i += 5;
$direction = false;
}
else
{
$i += $root - 1;
}
}
else
{
if ($i - $root <= 0)
{
$direction = true;
if ($i % $root == 0)
{
$i += $root;
}
else
{
i++;
}
direction = true;
}
else if ($i % $root == 0)
{
$direction = true;
$i += $root;
}
else
{
$i += 1 - $root;
}
}
}
Solution 6 - Php
Example Python implementation:
def wave(size):
curX = 0
curY = 0
direction = "down"
positions = []
positions.append((curX, curY))
while not (curX == size-1 and curY == size-1):
if direction == "down":
if curY == size-1: #can't move down any more; move right instead
curX += 1
else:
curY += 1
positions.append((curX, curY))
#move diagonally up and right
while curX < size-1 and curY > 0:
curX += 1
curY -= 1
positions.append((curX, curY))
direction = "right"
continue
else: #direction == "right"
if curX == size-1: #can't move right any more; move down instead
curY += 1
else:
curX += 1
positions.append((curX, curY))
#move diagonally down and left
while curY < size-1 and curX > 0:
curX -= 1
curY += 1
positions.append((curX, curY))
direction = "down"
continue
return positions
size = 5
for x, y in wave(size):
index = 1 + x + (y*size)
print index, x, y
Output:
1 0 0
6 0 1
2 1 0
3 2 0
7 1 1
11 0 2
16 0 3
12 1 2
8 2 1
4 3 0
5 4 0
9 3 1
13 2 2
17 1 3
21 0 4
22 1 4
18 2 3
14 3 2
10 4 1
15 4 2
19 3 3
23 2 4
24 3 4
20 4 3
25 4 4
Comedy one line implementation:
def wave(size):
return [1+x+size*y for x,y in filter(lambda (x,y): x >=0 and x < size and y >= 0 and y < size, reduce(lambda x, y: x+y, [r if i==0 else list(reversed(r)) for i, r in enumerate([(x-delta, delta) for delta in range(size)] for x in range(size*2))], []))]
print wave(5)
output:
[1, 6, 2, 11, 7, 3, 16, 12, 8, 4, 21, 17, 13, 9, 5, 22, 18, 14, 10, 23, 19, 15, 24, 20, 25]
Solution 7 - Php
One more PHP solution, using just for and if, traverses array only once
function waveSort(array $array) {
$elem = sqrt(count($array));
for($i = 0; $i < $elem; $i++) {
$multi[] = array_slice($array, $i*$elem , $elem);
}
$new = array();
$rotation = false;
for($i = 0; $i <= $elem-1; $i++) {
$k = $i;
for($j = 0; $j <= $i; $j++) {
if($rotation)
$new[] = $multi[$k][$j];
else
$new[] = $multi[$j][$k];
$k--;
}
$rotation = !$rotation;
}
for($i = $elem-1; $i > 0; $i--) {
$k = $elem - $i;
for($j = $elem-1; $j >= $elem - $i; $j--) {
if(!$rotation)
$new[] = $multi[$k][$j];
else
$new[] = $multi[$j][$k];
$k++;
}
$rotation = !$rotation;
}
return $new;
}
$array = range(1, 25);
$result = waveSort($array);
print_r($result);
$array = range(1, 36);
$result = waveSort($array);
print_r($result);
Solution 8 - Php
This is my take on it. Its similiar to qiuntus's response but more concise.
function wave($base) {
$i = 1;
$a = $base;
$square = $base*$base;
$out = array(1);
while ($i < $square) {
if ($i > ($square - $base)) { // hit the bottom
$i++;
$out[] = $i;
$a = 1 - $base;
} elseif ($i % $base == 0) { // hit the right
$i += $base;
$out[] = $i;
$a = $base - 1;
} elseif (($i - 1) % $base == 0) { // hit the left
$i += $base;
$out[] = $i;
$a = 1 - $base;
} elseif ($i <= $base) { // hit the top
$i++;
$out[] = $i;
$a = $base - 1;
}
if ($i < $square) {
$i += $a;
$out[] = $i;
}
}
return $out;
}
Solution 9 - Php
This is a code I wrote for one of my assignments while implementing JPEG.
The code below reads the following sample matrix in this fashion:
[[1, 2, 3],
[4, 5, 6], -> [1, 2, 4, 7, 5, 3, 6, 8, 9]
[7, 8, 9]]
The question posted wants to read it in another zigzag fashion, but that can be done with a few tweaks to my code below. Hope this helps :)
def read_zigzag_n(patch, N):
output = []
s = 1 # max number of entries in diagonal of that iteration
i = 0
j = 0
# flip = 0 -> row++ col-- ; flip = 1 -> row-- col++
flip = 1 # initially setting would be this because from 0,0 need to go to 0,1
# reading left upper triangle
while s < N+1:
count = 0 # counts the number of entries added from current diagonal
if flip == 0:
while(count<s-1): # s-1 because after last entry only one of row or col incremented
output.append(patch[i,j])
count += 1
i += 1
j -= 1
output.append(patch[i,j])
i += 1
flip = 1
else:
while(count<s-1):
output.append(patch[i,j])
count += 1
j += 1
i -= 1
output.append(patch[i,j])
j+=1
flip = 0
s += 1
# at this point s = N+1,
# and one of i or j is N and 0 respectively, depending on if N even or odd
if N % 2 == 0:
i -= 1
j += 1
flip = 1
else:
i += 1
j -= 1
flip = 0
s -= 2 # because now diagonal contains N-1 entries
# reading right lower triangle
while s > 0:
count = 0
if flip == 0:
while(count<s-1):
output.append(patch[i,j])
count += 1
i += 1
j -= 1
output.append(patch[i,j])
j += 1 # now its j += 1 instead of i += 1
flip = 1
else:
while(count<s-1):
output.append(patch[i,j])
count += 1
j += 1
i -= 1
output.append(patch[i,j])
i+=1 # now its i += 1 instead of j += 1
flip = 0
s -= 1
return output
Solution 10 - Php
This is a python implementation
def zigZagEncoding(M):
r, c = M.shape
zigZag = [[] for i in range(r+c-1)]
for i in range(r):
for j in range(c):
Sum = i+j
if (Sum %2 != 0):
zigZag[Sum].insert(0, M[i,j])
else:
zigZag[Sum].append(M[i,j])
arranged = []
for i in zigZag:
for j in i:
arranged.append(j)
return arranged
Input:
M = np.array([[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]])
zigZagEncoding(M)
Output:
[1, 6, 2, 3, 7, 11, 16, 12, 8, 4, 5, 9, 13, 17, 21, 22, 18,
14, 10, 15, 19, 23, 24, 20, 25]