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
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;
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)))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))
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
Common Lisp
(but with zero-based indexes and combining the even and odd cases)
(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))))
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>
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
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>
Haskell
Computing the array:
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)
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):
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)]
J
A succinct way:
($ [: /:@; [: <@|.`</. 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
This version is longer, but more "mathematical" and less "procedural":
($ [: /:@; [: <@(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
Leveraging a useful relationship among the indices:
($ ([: /:@;@(+/"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
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:
($ [: /:@; [: <@|.`</. i.) 5 3 0 1 5 2 4 6 3 7 11 8 10 12 9 13 14
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>
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.
%!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
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>