Zig-zag matrix
You are encouraged to solve this task according to the task description, using any language you may know.
Produce a zig-zag array. A zig-zag array is a square arrangement of the first N2 integers, where the numbers increase sequentially as you zig-zag along the anti-diagonals of the array. For a graphical representation, see JPG zigzag (JPG uses such arrays to encode images).
For example, given 5, produce this array:
0 1 5 6 14 2 4 7 13 15 3 8 12 16 21 9 11 17 20 22 10 18 19 23 24
Ada
<lang ada>with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Zig_Zag is
type Matrix is array (Positive range <>, Positive range <>) of Natural;
function Zig_Zag (Size : Positive) return Matrix is
Data : Matrix (1..Size, 1..Size);
I, J : Integer := 1;
begin
Data (1, 1) := 0;
for Element in 1..Size**2 - 1 loop
if (I + J) mod 2 = 0 then
-- Even stripes
if J < Size then
J := J + 1;
else
I := I + 2;
end if;
if I > 1 then
I := I - 1;
end if;
else
-- Odd stripes
if I < Size then
I := I + 1;
else
J := J + 2;
end if;
if J > 1 then
J := J - 1;
end if;
end if;
Data (I, J) := Element;
end loop;
return Data;
end Zig_Zag;
procedure Put (Data : Matrix) is
begin
for I in Data'Range (1) loop
for J in Data'Range (2) loop
Put (Integer'Image (Data (I, J)));
end loop;
New_Line;
end loop;
end Put;
begin
Put (Zig_Zag (5));
end Test_Zig_Zag;</lang> The function Zig_Zag generates a square matrix filled as requested by the task.
Sample output:
0 1 5 6 14 2 4 7 13 15 3 8 12 16 21 9 11 17 20 22 10 18 19 23 24
ALGOL 68
<lang algol68>PROC zig zag = (INT n)[,]INT: (
PROC move = (REF INT i, j)VOID: (
IF j < n THEN
i := ( i <= 1 | 1 | i-1 );
j +:= 1
ELSE
i +:= 1
FI
);
[n, n]INT a;
INT x:=LWB a, y:=LWB a;
FOR v FROM 0 TO n**2-1 DO
a[y, x] := v;
IF ODD (x + y) THEN
move(x, y)
ELSE
move(y, x)
FI
OD;
a
);
INT dim = 5;
- IF formatted transput possible THEN
FORMAT d = $z-d$;
FORMAT row = $"("n(dim-1)(f(d)",")f(d)")"$;
FORMAT block = $"("n(dim-1)(f(row)","lx)f(row)")"l$;
printf((block, zig zag(dim)))
ELSE#
[,]INT result = zig zag(dim); FOR i TO dim DO print((result[i,], new line)) OD
- FI#</lang>
Sample output:
| With formatted transput possible, e.g. ALGOL 68G | not formatted transput possible, e.g. ELLA ALGOL 68 |
(( 0, 1, 5, 6, 14), ( 2, 4, 7, 13, 15), ( 3, 8, 12, 16, 21), ( 9, 11, 17, 20, 22), ( 10, 18, 19, 23, 24)) |
+0 +1 +5 +6 +14
+2 +4 +7 +13 +15
+3 +8 +12 +16 +21
+9 +11 +17 +20 +22
+10 +18 +19 +23 +24
|
APL
<lang apl> zz ← {⍵⍴⎕IO-⍨⍋⊃,/{(2|⍴⍵):⌽⍵⋄⍵}¨(⊂w)/¨⍨w{↓⍵∘.=⍨∪⍵}+/[1]⍵⊤w←⎕IO-⍨⍳×/⍵} ⍝ General zigzag (any rectangle)
zzSq ← {zz,⍨⍵} ⍝ Square zigzag
zzSq 5
0 1 5 6 14
2 4 7 13 15
3 8 12 16 21
9 11 17 20 22
10 18 19 23 24</lang>
AutoHotkey
contributed by Laszlo on the ahk forum. <lang AutoHotkey>n = 5 ; size v := x := y := 1 ; initial values Loop % n*n { ; for every array element
a_%x%_%y% := v++ ; assign the next index
If ((x+y)&1) ; odd diagonal
If (x < n) ; while inside the square
y -= y<2 ? 0 : 1, x++ ; move right-up
Else y++ ; on the edge increment y, but not x: to even diagonal
Else ; even diagonal
If (y < n) ; while inside the square
x -= x<2 ? 0 : 1, y++ ; move left-down
Else x++ ; on the edge increment x, but not y: to odd diagonal
}
Loop %n% { ; generate printout
x := A_Index ; for each row
Loop %n% ; and for each column
t .= a_%x%_%A_Index% "`t" ; attach stored index
t .= "`n" ; row is complete
} MsgBox %t% ; show output</lang>
C
This uses some of the same functions and matrix structure as in the matrix exponentiation task. In particular NewSquareMtx and SquareMtxPrint (with modded format). For filling, it uses fundamentally the same algorithm as the Python example. <lang c>#include <stdio.h>
- include <stdlib.h>
typedef struct squareMtxStruct {
int dim; double *cells; double **m;
} *SquareMtx;
/* function for initializing row r of a new matrix */ typedef void (*FillFunc)( double *cells, int r, int dim, void *ff_data);
SquareMtx NewSquareMtx( int dim, FillFunc fillFunc, void *ff_data ) {
SquareMtx sm = (SquareMtx)malloc(sizeof(struct squareMtxStruct));
if (sm) {
int rw;
sm->dim = dim;
sm->cells = (double *)malloc(dim*dim * sizeof(double));
sm->m = (double **)malloc( dim * sizeof(double *));
if ((sm->cells != NULL) && (sm->m != NULL)) {
for (rw=0; rw<dim; rw++) {
sm->m[rw] = sm->cells + dim*rw;
fillFunc( sm->m[rw], rw, dim, ff_data );
}
}
else {
if (sm->m) free(sm->m);
if (sm->cells) free(sm->cells);
free(sm);
printf("Square Matrix allocation failure\n");
return NULL;
}
}
else {
printf("Malloc failed for square matrix\n");
}
return sm;
}
FILE *fout; void SquareMtxPrint( SquareMtx mtx, const char *mn ) {
int rw, col; int d = mtx->dim;
fprintf(fout, "%s dim:%d =\n", mn, mtx->dim);
for (rw=0; rw<d; rw++) {
fprintf(fout, " |");
for(col=0; col<d; col++)
fprintf(fout, "%3.0f ",mtx->m[rw][col] );
fprintf(fout, " |\n");
}
fprintf(fout, "\n");
}
typedef struct rcStruct { /* a row cell index */
int rw, cl;
} CellSpec;
typedef struct cellArray {
CellSpec *cells; int size;
} ZZFillData;
int CellCmpr( const CellSpec *a, const CellSpec *b) {
int rc1 = a->rw + a->cl;
int rc2 = b->rw + b->cl;
if ( rc1 == rc2 )
return (rc1 % 2)? a->rw - b->rw : b->rw - a->rw;
return rc1 - rc2;
}
void ComputeFill(ZZFillData *fillData, int dim) {
int size, ix;
CellSpec *cells;
size = fillData->size = dim*dim;
cells = fillData->cells = (CellSpec *)malloc( size*sizeof(CellSpec));
for (ix=0; ix<size; ix++) {
cells[ix].rw = ix / dim;
cells[ix].cl = ix % dim;
}
qsort( cells, size, sizeof(CellSpec), CellCmpr );
}
int CellValue( ZZFillData *fillData, int row, int col ) {
int k; CellSpec *cs = fillData->cells;
for (k=0; k<fillData->size; k++, cs++) {
if ((cs->rw == row) &&(cs->cl == col)) break;
}
return k;
}
void zigzagfill( double *cells, int row, int dim, ZZFillData *data) {
int col;
if ( NULL == data->cells) ComputeFill( data, dim );
for (col=0; col<dim; col++) {
cells[col] = CellValue( data, row, col);
}
if (row+1 == dim) { /* done - free memory*/
free(data->cells);
data->cells = 0;
data->size = 0;
}
}
int main() {
ZZFillData fillData = {NULL, 0};
SquareMtx mtx=NewSquareMtx( 6, &zigzagfill, &fillData);
fout = fopen("zigzag.out", "w");
// fout = stdout;
SquareMtxPrint( mtx, "zzag"); fclose(fout); return 0;
}</lang> Output:
zzag dim:6 = | 0 1 5 6 14 15 | | 2 4 7 13 16 25 | | 3 8 12 17 24 26 | | 9 11 18 23 27 32 | | 10 19 22 28 31 33 | | 20 21 29 30 34 35 |
C++
<lang cpp>#include <vector>
- include <memory> // for auto_ptr
- include <cmath> // for the log10 and floor functions
- include <iostream>
- include <iomanip> // for the setw function
using namespace std;
typedef vector< int > IntRow; typedef vector< IntRow > IntTable;
auto_ptr< IntTable > getZigZagArray( int dimension ) { auto_ptr< IntTable > zigZagArrayPtr( new IntTable( dimension, IntRow( dimension ) ) );
// fill along diagonal stripes (oriented as "/") int lastValue = dimension * dimension - 1; int currNum = 0; int currDiag = 0; int loopFrom; int loopTo; int i; int row; int col; do { if ( currDiag < dimension ) // if doing the upper-left triangular half { loopFrom = 0; loopTo = currDiag; } else // doing the bottom-right triangular half { loopFrom = currDiag - dimension + 1; loopTo = dimension - 1; }
for ( i = loopFrom; i <= loopTo; i++ ) { if ( currDiag % 2 == 0 ) // want to fill upwards { row = loopTo - i + loopFrom; col = i; } else // want to fill downwards { row = i; col = loopTo - i + loopFrom; }
( *zigZagArrayPtr )[ row ][ col ] = currNum++; }
currDiag++; } while ( currNum <= lastValue );
return zigZagArrayPtr; }
void printZigZagArray( const auto_ptr< IntTable >& zigZagArrayPtr ) { size_t dimension = zigZagArrayPtr->size();
int fieldWidth = static_cast< int >( floor( log10( static_cast< double >( dimension * dimension - 1 ) ) ) ) + 2;
size_t col; for ( size_t row = 0; row < dimension; row++ ) { for ( col = 0; col < dimension; col++ ) cout << setw( fieldWidth ) << ( *zigZagArrayPtr )[ row ][ col ]; cout << endl; } }
int main() { printZigZagArray( getZigZagArray( 5 ) ); }</lang>
C#
<lang csharp>public static int[,] ZigZag(int n) {
int[,] result = new int[n, n];
int i = 0, j = 0;
int d = -1; // -1 for top-right move, +1 for bottom-left move
int start = 0, end = n * n - 1;
do
{
result[i, j] = start++;
result[n - i - 1, n - j - 1] = end--;
i += d; j -= d;
if (i < 0)
{
i++; d = -d; // top reached, reverse
}
else if (j < 0)
{
j++; d = -d; // left reached, reverse
}
} while (start < end);
if (start == end)
result[i, j] = start;
return result;
}</lang>
Common Lisp
(but with zero-based indexes and combining the even and odd cases)
<lang lisp>(defun zigzag (n)
(flet ((move (i j)
(if (< j (1- n))
(values (max 0 (1- i)) (1+ j))
(values (1+ i) j))))
(loop with a = (make-array (list n n) :element-type 'integer)
with x = 0
with y = 0
for v from 0 below (* n n)
do (setf (aref a x y) v)
(if (evenp (+ x y))
(setf (values x y) (move x y))
(setf (values y x) (move y x)))
finally (return a))))</lang>
D
<lang d>int[][] zigzag(int n) {
void move(ref int i, ref int j) {
if (j < (n - 1)) {
i = (i-1) < 0 ? 0 : i-1;
j++;
} else
i++;
}
int x, y; auto a = new int[][](n, n);
for (int v; v < n*n; v++) {
a[y][x] = v;
if ((x + y) & 1)
move(x, y);
else
move(y, x);
}
return a;
}</lang>
E
First, some tools originally written for Spiral (only the array is used):
/** Missing scalar multiplication, but we don't need it. */
def makeVector2(x, y) {
return def vector {
to x() { return x }
to y() { return y }
to add(other) { return makeVector2(x + other.x(), y + other.y()) }
to clockwise() { return makeVector2(-y, x) }
}
}
/** Bugs: (1) The printing is specialized. (2) No bounds check on the column. */
def makeFlex2DArray(rows, cols) {
def storage := ([null] * (rows * cols)).diverge()
return def flex2DArray {
to __printOn(out) {
for y in 0..!rows {
for x in 0..!cols {
out.print(<import:java.lang.makeString>.format("%3d", [flex2DArray[y, x]]))
}
out.println()
}
}
to get(r, c) { return storage[r * cols + c] }
to put(r, c, v) { storage[r * cols + c] := v }
}
}Then the code.
<lang e>def zigZag(n) {
def move(&i, &j) {
if (j < (n - 1)) {
i := 0.max(i - 1)
j += 1
} else {
i += 1
}
}
def array := makeFlex2DArray(n, n) var x := 0 var y := 0
for i in 1..n**2 {
array[y, x] := i
if ((x + y) % 2 == 0) {
move(&x, &y)
} else {
move(&y, &x)
}
}
return array
}</lang>
Fan
<lang Fan>using gfx // for Point; convenient x/y wrapper
- A couple methods for generating a 'zigzag' array like
- 0 1 5 6
- 2 4 7 12
- 3 8 11 13
- 9 10 14 15
class ZigZag {
** return an n x n array of uninitialized Int
static Int[][] makeSquareArray(Int n)
{
Int[][] grid := Int[][,] {it.size=n}
n.times |i| { grid[i] = Int[,] {it.size=n} }
return grid
}
Int[][] zig(Int n)
{
grid := makeSquareArray(n)
move := |Int i, Int j->Point|
{ return j < n - 1 ? Point(i <= 0 ? 0 : i-1, j+1) : Point(i+1, j) }
pt := Point(0,0)
(n*n).times |i| {
grid[pt.y][pt.x] = i
if ((pt.x+pt.y)%2 != 0) pt = move(pt.x,pt.y)
else {tmp:= move(pt.y,pt.x); pt = Point(tmp.y, tmp.x) }
}
return grid
}
public static Int[][] zag(Int size)
{
data := makeSquareArray(size)
Int i := 1
Int j := 1
for (element:=0; element < size * size; element++)
{
data[i - 1][j - 1] = element
if((i + j) % 2 == 0) {
// Even stripes
if (j < size) {
j++
} else {
i += 2
}
if (i > 1) {
i--
}
} else {
// Odd stripes
if (i < size) {
i++;
} else {
j += 2
}
if (j > 1) {
j--
}
}
}
return data;
}
Void print(Int[][] data)
{
data.each |row|
{
buf := StrBuf()
row.each |num|
{
buf.add(num.toStr.justr(3))
}
echo(buf)
}
}
Void main()
{
echo("zig method:")
print(zig(8))
echo("\nzag method:")
print(zag(8))
}
}</lang>
Forth
<lang forth>0 value diag
- south diag abs + cell+ ;
' cell+ value zig ' south value zag
- init ( n -- )
1- cells negate to diag ['] cell+ to zig ['] south to zag ;
- swap-diag zig zag to zig to zag ;
- put ( n addr -- n+1 addr )
2dup ! swap 1+ swap ;
- turn ( addr -- addr+E/S )
zig execute swap-diag diag negate to diag ;
- zigzag ( matrix n -- )
{ n } n init
0 swap
n 1 ?do
put turn
i 0 do put diag + loop
loop
swap-diag
n 1 ?do
put turn
n i 1+ ?do put diag + loop
loop
! ;
- .matrix ( n matrix -- )
over 0 do
cr
over 0 do
dup @ 3 .r cell+
loop
loop 2drop ;
- test ( n -- ) here over zigzag here .matrix ;
5 test
0 1 5 6 14 2 4 7 13 15 3 8 12 16 21 9 11 17 20 22 10 18 19 23 24 ok</lang>
Fortran
<lang fortran>PROGRAM ZIGZAG
IMPLICIT NONE
INTEGER, PARAMETER :: size = 5
INTEGER :: zzarray(size,size), x(size*size), y(size*size), i, j
! index arrays
x = (/ ((j, i = 1, size), j = 1, size) /)
y = (/ ((i, i = 1, size), j = 1, size) /)
! Sort indices
DO i = 2, size*size
j = i - 1
DO WHILE (j>=1 .AND. (x(j)+y(j)) > (x(i)+y(i)))
j = j - 1
END DO
x(j+1:i) = cshift(x(j+1:i),-1)
y(j+1:i) = cshift(y(j+1:i),-1)
END DO
! Create zig zag array
DO i = 1, size*size
IF (MOD(x(i)+y(i), 2) == 0) THEN
zzarray(x(i),y(i)) = i - 1
ELSE
zzarray(y(i),x(i)) = i - 1
END IF
END DO
! Print zig zag array
DO j = 1, size
DO i = 1, size
WRITE(*, "(I5)", ADVANCE="NO") zzarray(i,j)
END DO
WRITE(*,*)
END DO
END PROGRAM ZIGZAG</lang>
Groovy
Edge
An odd technique that traverses the grid edges directly and calculates the transform onto the grid.
<lang groovy>def zz = { n ->
grid = new int[n][n]
i = 0
for (d in 1..n*2) {
(x, y) = [Math.max(0, d - n), Math.min(n - 1, d - 1)]
Math.min(d, n*2 - d).times {
grid[d%2?y-it:x+it][d%2?x+it:y-it] = i++;
}
}
grid
}</lang>
Output
> zz(5).each { it.each { print("${it}".padLeft(3)) }; println() }
0 1 5 6 14
2 4 7 13 15
3 8 12 16 21
9 11 17 20 22
10 18 19 23 24
Cursor
Ported from the Java example
<lang groovy>def zz = { n->
move = { i, j -> j < n - 1 ? [i <= 0 ? 0 : i-1, j+1] : [i+1, j] }
grid = new int[n][n]
(x, y) = [0, 0]
(n**2).times {
grid[y][x] = it
if ((x+y)%2) (x,y) = move(x,y)
else (y,x) = move(y,x)
}
grid
}</lang>
Output
> zz(5).each { it.each { print("${it}".padLeft(3)) }; println() }
0 1 5 6 14
2 4 7 13 15
3 8 12 16 21
9 11 17 20 22
10 18 19 23 24
Sorting
Ported from the Python example with some input from J
<lang groovy>def zz = { n ->
(0..<n*n).collect { [x:it%n,y:(int)(it/n)] }.sort { c->
[c.x+c.y, (((c.x+c.y)%2) ? c.y : -c.y)]
}.with { l -> l.inject(new int[n][n]) { a, c -> a[c.y][c.x] = l.indexOf(c); a } }
}</lang>
Output
> zz(5).each { it.each { print("${it}".padLeft(3)) }; println() }
0 1 5 6 14
2 4 7 13 15
3 8 12 16 21
9 11 17 20 22
10 18 19 23 24
Haskell
Computing the array:
<lang haskell>import Data.Array (array, bounds, range, (!)) import Data.Monoid (mappend) import Data.List (sortBy)
compZig (x,y) (x',y') = compare (x+y) (x'+y')
`mappend` if even (x+y) then compare x x'
else compare y y'
zigZag upper = array b $ zip (sortBy compZig (range b))
[0..] where b = ((0,0),upper)</lang>
compZig compares coordinates using the order of a zigzag walk: primarily, the antidiagonals; secondarily, alternating directions along them.
In zigZag, array takes the bounds and a list of indexes paired with values. We take the list of all indexes, range b, and sort it in the zigzag order, then zip that with the integers starting from 0. (This algorithm was inspired by the explanation of the J example.)
Displaying the array (not part of the task):
<lang haskell>import Text.Printf (printf)
-- format a 2d array of integers neatly show2d a = unlines [unwords [printf "%3d" (a ! (x,y) :: Integer) | x <- axis fst] | y <- axis snd]
where (l, h) = bounds a
axis f = [f l .. f h]
main = mapM_ (putStr . show2d . zigZag) [(3,3), (4,4), (10,2)]</lang>
J
A succinct way: <lang j> ($ [: /:@; [: <@|.`</. i.)@,~ 5
0 1 5 6 14 2 4 7 13 15 3 8 12 16 21 9 11 17 20 22
10 18 19 23 24</lang>
This version is longer, but more "mathematical" and less "procedural": <lang j> ($ [: /:@; [: <@(A.~_2|#)/. i.)@,~ 5
0 1 5 6 14 2 4 7 13 15 3 8 12 16 21 9 11 17 20 22
10 18 19 23 24</lang>
Leveraging a useful relationship among the indices: <lang j> ($ ([: /:@;@(+/"1 <@|.`</. ]) (#: i.@((*/)))))@,~ 5 3
0 1 5 6 14 2 4 7 13 15 3 8 12 16 21 9 11 17 20 22
10 18 19 23 24</lang>
By the way, all the edge cases are handled transparently, without any special checks. Furthermore, by simply removing the trailing @,~ from the solutions, they automatically generalize to rectangular (non-square) matrices: <lang j> ($ [: /:@; [: <@|.`</. i.) 5 3 0 1 5 2 4 6 3 7 11 8 10 12 9 13 14</lang>
Java
<lang java>public static int[][] Zig_Zag(int size){ int[][] data= new int[size][size]; int i= 1; int j= 1; for(int element= 0;element < size * size;element++){ data[i - 1][j - 1]= element; if((i + j) % 2 == 0){ // Even stripes if(j < size){ j++; }else{ i+= 2; } if(i > 1){ i--; } }else{ // Odd stripes if(i < size){ i++; }else{ j+= 2; } if(j > 1){ j--; } } } return data; }</lang>
JavaScript
for the print() function.
Subclasses the Matrix class defined at Matrix Transpose#JavaScript <lang javascript>function ZigZagMatrix(n) {
this.height = n; this.width = n;
this.mtx = [];
for (var i = 0; i < n; i++)
this.mtx[i] = [];
var i=1, j=1;
for (var e = 0; e < n*n; e++) {
this.mtx[i-1][j-1] = e;
if ((i + j) % 2 == 0) {
// Even stripes
if (j < n) j ++;
else i += 2;
if (i > 1) i --;
} else {
// Odd stripes
if (i < n) i ++;
else j += 2;
if (j > 1) j --;
}
}
} ZigZagMatrix.prototype = Matrix.prototype;
var z = new ZigZagMatrix(5); print(z); print();
z = new ZigZagMatrix(4); print(z);</lang> output
0,1,5,6,14 2,4,7,13,15 3,8,12,16,21 9,11,17,20,22 10,18,19,23,24 0,1,5,6 2,4,7,12 3,8,11,13 9,10,14,15
Lua
<lang Lua> local zigzag = {}
function zigzag.new(n)
local a = {}
local i -- cols
local j -- rows
a.n = n
a.val = {}
for j = 1, n do
a.val[j] = {}
for i = 1, n do
a.val[j][i] = 0
end
end
i = 1 j = 1
local di local dj local k = 0
while k < n * n do
a.val[j][i] = k
k = k + 1
if i == n then
j = j + 1
a.val[j][i] = k
k = k + 1
di = -1
dj = 1
end
if j == 1 then
i = i + 1
a.val[j][i] = k
k = k + 1
di = -1
dj = 1
end
if j == n then
i = i + 1
a.val[j][i] = k
k = k + 1
di = 1
dj = -1
end
if i == 1 then
j = j + 1
a.val[j][i] = k
k = k + 1
di = 1
dj = -1
end
i = i + di
j = j + dj
end
setmetatable(a, {__index = zigzag, __tostring = zigzag.__tostring})
return a
end
function zigzag:__tostring()
local s = {}
for j = 1, self.n do
local row = {}
for i = 1, self.n do
row[i] = string.format('%d', self.val[j][i])
end
s[j] = table.concat(row, ' ')
end
return table.concat(s, '\n')
end
print(zigzag.new(5)) </lang>
M4
<lang M4>divert(-1)
define(`set2d',`define(`$1[$2][$3]',`$4')') define(`get2d',`defn(`$1[$2][$3]')') define(`for',
`ifelse($#,0,``$0, `ifelse(eval($2<=$3),1, `pushdef(`$1',$2)$4`'popdef(`$1')$0(`$1',incr($2),$3,`$4')')')')
define(`show2d',
`for(`x',0,decr($2),
`for(`y',0,decr($3),`format(`%2d',get2d($1,x,y)) ')
')')
dnl <name>,<size> define(`zigzag',
`define(`j',1)`'define(`k',1)`'for(`e',0,eval($2*$2-1),
`set2d($1,decr(j),decr(k),e)`'ifelse(eval((j+k)%2),0,
`ifelse(eval(k<$2),1,
`define(`k',incr(k))',
`define(`j',eval(j+2))')`'ifelse(eval(j>1),1,
`define(`j',decr(j))')',
`ifelse(eval(j<$2),1,
`define(`j',incr(j))',
`define(`k',eval(k+2))')`'ifelse(eval(k>1),1,
`define(`k',decr(k))')')')')
divert
zigzag(`a',5) show2d(`a',5,5)</lang>
Output:
0 1 5 6 14 2 4 7 13 15 3 8 12 16 21 9 11 17 20 22 10 18 19 23 24
Mathematica
Rule-based implementation, the upper-left half is correctly calculated using a direct formula. The lower-right half is then 'mirrored' from the upper-left half. <lang Mathematica>ZigZag[size_Integer/;size>0]:=Module[{empty=ConstantArray[0,{size,size}]},
empty=ReplacePart[empty,{i_,j_}:>1/2 (i+j)^2-(i+j)/2-i (1-Mod[i+j,2])-j Mod[i+j,2]];
ReplacePart[empty,{i_,j_}/;i+j>size+1:> size^2-tmpsize-i+1,size-j+1-1]
]</lang> Ported from the java-example: <lang Mathematica>ZigZag2[size_] := Module[{data, i, j, elem},
data = ConstantArray[0, {size, size}];
i = j = 1;
For[elem = 0, elem < size^2, elem++,
datai, j = elem;
If[Mod[i + j, 2] == 0,
If[j < size, j++, i += 2];
If[i > 1, i--]
,
If[i < size, i++, j += 2];
If[j > 1, j--];
];
];
data
]</lang>
Examples: <lang Mathematica>ZigZag[5] // MatrixForm ZigZag2[6] // MatrixForm</lang> gives back:
Modula-3
<lang modula3>MODULE ZigZag EXPORTS Main;
IMPORT IO, Fmt;
TYPE Matrix = REF ARRAY OF ARRAY OF CARDINAL;
PROCEDURE Create(size: CARDINAL): Matrix =
PROCEDURE move(VAR i, j: INTEGER) =
BEGIN
IF j < (size - 1) THEN
IF (i - 1) < 0 THEN
i := 0;
ELSE
i := i - 1;
END;
INC(j);
ELSE
INC(i);
END;
END move;
VAR data := NEW(Matrix, size, size);
x, y: INTEGER := 0;
BEGIN
FOR v := 0 TO size * size - 1 DO
data[y, x] := v;
IF (x + y) MOD 2 = 0 THEN
move(y, x);
ELSE
move(x, y);
END;
END;
RETURN data;
END Create;
PROCEDURE Print(data: Matrix) =
BEGIN
FOR i := FIRST(data^) TO LAST(data^) DO
FOR j := FIRST(data[0]) TO LAST(data[0]) DO
IO.Put(Fmt.F("%3s", Fmt.Int(data[i, j])));
END;
IO.Put("\n");
END;
END Print;
BEGIN
Print(Create(5));
END ZigZag.</lang> Output:
0 1 5 6 14 2 4 7 13 15 3 8 12 16 21 9 11 17 20 22 10 18 19 23 24
OCaml
<lang ocaml>let zigzag n =
(* move takes references and modifies them directly *)
let move i j =
if !j < n - 1 then begin
i := max 0 (!i - 1);
incr j
end else
incr i
in
let a = Array.make_matrix n n 0
and x = ref 0 and y = ref 0 in
for v = 0 to n * n - 1 do
a.(!x).(!y) <- v;
if (!x + !y) mod 2 = 0 then
move x y
else
move y x
done;
a</lang>
Perl
<lang perl>sub lCombine
- A watered-down list comprehension: given a list of array references,
- returns every combination of each of their elements. For example,
- lCombine [0, 1], ['a', 'b', 'c']
- returns
- [0, 'a'], [0, 'b'], [0, 'c'], [1, 'a'], [1, 'b'], [1, 'c']
{@_ or return [];
my $l = shift;
my @rest = lCombine(@_);
map
{my $e = $_;
map
{[$e, @$_]}
@rest;}
@$l;}
sub compZig
{my ($x1, $y1) = @$a;
my ($x2, $y2) = @$b;
$x1 + $y1 <=> $x2 + $y2
or ($x1 + $y1) % 2
? $y1 <=> $y2
: $x1 <=> $x2;}
sub zigZag
- Creates a zig-zag array with the given width and height.
{my ($w, $h) = @_;
my $n = 0;
my @a;
$a[ $_->[1] ][ $_->[0] ] = $n++
foreach sort compZig lCombine [0 .. $h - 1], [0 .. $w - 1];
return @a;}</lang>
PostScript
This implementation is far from being elegant or smart, but it builds the zigzag how a human being could do, and also draws lines to show the path.
<lang postscript>%!PS %%BoundingBox: 0 0 300 200 /size 9 def % defines row * column (9*9 -> 81 numbers,
% from 0 to 80)
/itoa { 2 string cvs } bind def % visual bounding box... % 0 0 moveto 300 0 lineto 300 200 lineto 0 200 lineto % closepath stroke 20 150 translate % it can be easily enhanced to support more columns and % rows. This limit is put here just to avoid more than 2 % digits, mainly because of formatting size size mul 99 le {
/Helvetica findfont 14 scalefont setfont
/ulimit size size mul def
/sizem1 size 1 sub def
% prepare the number list
0 ulimit 1 sub { dup 1 add } repeat
ulimit array astore
/di -1 def /dj 1 def
/ri 1 def /rj 0 def /pus true def
0 0 moveto
/i 0 def /j 0 def
{ % can be rewritten a lot better :)
0.8 setgray i 30 mul j 15 mul neg lineto stroke
0 setgray i 30 mul j 15 mul neg moveto itoa show
i 30 mul j 15 mul neg moveto
pus {
i ri add size ge {
/ri 0 def /rj 1 def
} if
j rj add size ge {
/ri 1 def /rj 0 def
} if
/pus false def
/i i ri add def
/j j rj add def
/ri rj /rj ri def def
} {
i di add dup 0 le
exch sizem1 ge or
j dj add dup 0 le
exch sizem1 ge or
or {
/pus true def
/i i di add def /j j dj add def
/di di neg def /dj dj neg def
} {
/i i di add def /j j dj add def
} ifelse
} ifelse
} forall
stroke showpage
} if %%EOF</lang>
Python
There is a full explanation of the algorithm used here. <lang python>import math def zigzag(n):
indexorder = sorted(((x,y) for x in range(n) for y in range(n)),
key = lambda (x,y): (x+y, -y if (x+y) % 2 else y) )
return dict((index,n) for n,index in enumerate(indexorder))
# or, in Python 3: return {index: n for n,index in enumerate(indexorder)}
def printzz(myarray):
n = math.round(math.sqrt(len(myarray)))
for x in range(n):
for y in range(n):
print "%2i" % myarray[(x,y)],
print
printzz(zigzag(6))</lang> Program output:
0 1 5 6 14 15
2 4 7 13 16 25
3 8 12 17 24 26
9 11 18 23 27 32
10 19 22 28 31 33
20 21 29 30 34 35Alternative version,
.
<lang python>def zigzag(n):
def move(i, j):
if j < (n - 1):
return max(0, i-1), j+1
else:
return i+1, j
a = [[0] * n for _ in xrange(n)]
x, y = 0, 0
for v in xrange(n * n):
a[y][x] = v
if (x + y) & 1:
x, y = move(x, y)
else:
y, x = move(y, x)
return a
from pprint import pprint pprint(zigzag(5))</lang> Output: <lang python>[[0, 1, 5, 6, 14],
[2, 4, 7, 13, 15], [3, 8, 12, 16, 21], [9, 11, 17, 20, 22], [10, 18, 19, 23, 24]]</lang>
Scala
Uses the array indices sort solution used by others here.
<lang scala>def zigzag(n:int) = {
var l = List[Tuple2[int,int]]()
(0 until n*n) foreach {i=>l = l + (i%n,i/n)}
l = l.sort{case ((x,y),(u,v)) => if (x+y == u+v)
if ((x+y) % 2 == 0) x<u else y<v
else (x+y) < (u+v) }
var a = new Array[Array[int]](n,n)
l.zipWithIndex foreach {case ((x,y),i) => a(y)(x) = i}
a
}</lang>
Or, compressed into just one statement
<lang scala>def zigzag(n:int) = {
var indices = List[Tuple2[Int,Int]]() var array = new Array[Array[Int]](n,n)
(0 until n*n).foldLeft(indices)((l,i) => l + (i%n,i/n)).
sort{case ((x,y),(u,v)) => if (x+y == u+v)
if ((x+y) % 2 == 0) x<u else y<v
else (x+y) < (u+v) }.
zipWithIndex.foldLeft(array) {case (a,((x,y),i)) => a(y)(x) = i; a}
} </lang>
R
<lang R>zigzag <- function(size) {
digits <- seq_len(size^2) - 1
mat <- matrix(0, nrow = size, ncol=size)
i <- 1
j <- 1
for(element in digits)
{
mat[i,j] <- element
if((i + j) %% 2 == 0)
{
# Even stripes
if(j < size) j <- j + 1 else i <- i + 2
if(i > 1) i <- i - 1
} else
{
# Odd stripes
if(i < size) i <- i + 1 else j <- j + 2
if(j > 1) j <- j - 1
}
}
mat
}
zigzag(5)</lang>
Ruby
Using the print_matrix method from Reduced row echelon form#Ruby
<lang ruby>def zigzag(n)
indices = []
n.times {|x| n.times {|y| indices << [x,y] }}
zigzag = Array.new(n) {Array.new(n, nil)} # n x n array of nils
indices.sort_by {|x,y| [x+y, ((x+y)%2).zero? ? y : -y]} \
.each_with_index {|a,i| x,y = a; zigzag[x][y] = i}
zigzag
end print_matrix zigzag(5)</lang>
0 1 5 6 14 2 4 7 13 15 3 8 12 16 21 9 11 17 20 22 10 18 19 23 24
Tcl
Using print_matrix from Matrix Transpose…
<lang tcl>proc zigzag {size} {
set m [lrepeat $size [lrepeat $size .]]
set x 0; set dx -1
set y 0; set dy 1
for {set i 0} {$i < $size ** 2} {incr i} {
if {$x >= $size} {
incr x -1
incr y 2
negate dx dy
} elseif {$y >= $size} {
incr x 2
incr y -1
negate dx dy
} elseif {$x < 0 && $y >= 0} {
incr x
negate dx dy
} elseif {$x >= 0 && $y < 0} {
incr y
negate dx dy
}
lset m $x $y $i
incr x $dx
incr y $dy
}
return $m
}
proc negate {args} {
foreach varname $args {
upvar 1 $varname var
set var [expr {-1 * $var}]
}
}
print_matrix [zigzag 5]</lang>
0 1 5 6 14 2 4 7 13 15 3 8 12 16 21 9 11 17 20 22 10 18 19 23 24
Ursala
adapted from the J solution <lang Ursala>#import std
- import nat
zigzag = ~&mlPK2xnSS+ num+ ==+sum~~|=xK9xSL@iiK0+ iota</lang> test program (three examples): <lang Ursala>#cast %nLLL
tests = zigzag* <4,5,6></lang> output:
<
<
<0,1,5,6>,
<2,4,7,12>,
<3,8,11,13>,
<9,10,14,15>>,
<
<0,1,5,6,14>,
<2,4,7,13,15>,
<3,8,12,16,21>,
<9,11,17,20,22>,
<10,18,19,23,24>>,
<
<0,1,5,6,14,15>,
<2,4,7,13,16,25>,
<3,8,12,17,24,26>,
<9,11,18,23,27,32>,
<10,19,22,28,31,33>,
<20,21,29,30,34,35>>>