Zig-zag scan an N x N array

Question

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

Basile

Almost certainly easier to build the array in the correct order in the first place, than to achieve this via any kind of sort – Winged

I wish everyone took the time to present their questions as well as you did. – Clarenceclarenceux

Thats a nice question. +1 – Plummet

Also assume that you mean square of an integer, rather than square root.... and that 14 should be 16 – Winged

New mission for me! bookmarked I'll do it when I get home. :) – Cavein

You sorted output array should be like that: 1 6 2 3 7 11 16 12 17 13 14 18 24 25 – Warden

I believe he wanted to automate that task. – Cavein

MarkBaker - of course it would be easier, but all I have is the number of how many elements there are on each side. 5, 6, 7 etc.. There is no limit, it can go up to 1000 or more, so it would take me forever to generate the endless possibilities by hand :) IvanIvković - yes, I'm trying to automate this.. But with no luck yet. – Basile

you can write an algorithm to do it, but i don't think there is a sort of that kind. – Beanstalk

I'm sorry if I'm using the wrong terms, English is not my first language. Yes - an algorithm, not a sort. – Basile

Would you like to calculate the sort with javascript (jquery element processing) or PHP? – Cavein

I guess PHP would fit my needs better, but if it's easier in JavaScript/jQuery then that will be fine as well :) – Basile

Well I guess these guys already answered. :) Use setTimeout for each table cell fade. You get the javascript part? :) – Cavein

Yes, it was the easy bit :) – Basile

This could be an excellent question for Code Golf – Ursal

Answer 1

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)
}

Rhiamon

Works really good!:) It struggles with large arrays, but it still works :) Thanks! – Basile

Yeah, it is a brute-force approach. Seems to me there's a more analytical solution to it, that would only traverse the original array once. Some optimization could be implemented too, like removing already processed diagonals from $tempArray to reduce number of elements to examine in each loop – Rhiamon

Actually.. It doesn't work properly. When I do a grid of 10x10 - it messes everything up :/ – Basile

Right, I hordcoded the array dimension here $tempArray[] = array_slice($array,$i*5,$dimension); - fixed – Rhiamon

Also added optimization that should cut the processing time in roughly 50% – Rhiamon

@Matt: Updated code with new faster (~12 times) and hopefully bug free version :) – Rhiamon

Answer 2

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:

1. Initialize an n x n array, where n is the square root of the input size.
2. 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.
3. 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.
4. Calculate the indexes for the bottom-right portion by simple subtraction from n * n + 1 as 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].
5. 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.

Attending

We've got a candidate for 'Populist' badge here ;) +1 – Rhiamon

Answer 3

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.

Absolutism

Answer 4

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));

Banerjee

Answer 5

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;
        }
    }
}

Collaborationist

Answer 6

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]

Cantonese

Answer 7

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);

Here it is in action

Inspan

I tested it for 16, 25 and 36 elements, it outputs exactly like on your picture – Inspan

Answer 8

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;
}

Noodle

Answer 9

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

Baty

Answer 10

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]

Allegraallegretto

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Quinones