Zig-zag matrix: Difference between revisions
(→{{header|Qi}}: simplify somewhat) |
|||
Line 1,444: | Line 1,444: | ||
=={{header|NetRexx}}== |
=={{header|NetRexx}}== |
||
{{trans|REXX}} |
|||
Reimplementation of [[#REXX|Rexx]] |
|||
<lang NetRexx>/* NetRexx */ |
<lang NetRexx>/* NetRexx */ |
||
options replace format comments java crossref savelog symbols binary |
options replace format comments java crossref savelog symbols binary |
Revision as of 01:06, 18 September 2011
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
ActionScript
<lang as> package {
public class ZigZagMatrix extends Array { private var height:uint; private var width:uint; public var mtx:Array = []; public function ZigZagMatrix(size:uint) { this.height = size; this.width = size; this.mtx = []; for (var i:uint = 0; i < size; i++) { this.mtx[i] = []; } i = 1; var j:uint = 1; for (var e:uint = 0; e < size*size; e++) { this.mtx[i-1][j-1] = e; 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 --; } } } }
} </lang>
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>
AppleScript
Here's a vector & matrix boundary detection approach to the Zig-zap matrix: <lang AppleScript>set n to 5 -- Size of zig-zag matrix (n^2 cells).
-- Create an empty matrix. set m to {} repeat with i from 1 to n set R to {} repeat with j from 1 to n set end of R to 0 end repeat set end of m to R end repeat
-- Populate the matrix in a zig-zag manner. set {x, y, v, d} to {1, 1, 0, 1} repeat while v < (n ^ 2) if 1 ≤ x and x ≤ n and 1 ≤ y and y ≤ n then set {m's item y's item x, x, y, v} to {v, x + d, y - d, v + 1} else if x > n then set {x, y, d} to {n, y + 2, -d} else if y > n then set {x, y, d} to {x + 2, n, -d} else if x < 1 then set {x, y, d} to {1, y, -d} else if y < 1 then set {x, y, d} to {x, 1, -d} end if end repeat --> R = {{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}}
-- Reformat the matrix into a table for viewing. repeat with i in m repeat with j in i set j's contents to (characters -(length of (n ^ 2 as string)) thru -1 of (" " & j)) as string end repeat set end of i to return end repeat return return & m as string</lang> But this can be improved upon by building the matrix by populating empty AppleScript lists (it's about 50% faster when n=50):<lang AppleScript>set n to 5
set m to {} repeat with i from 1 to n set end of m to {} -- Built a foundation for the matrix out of n empty lists. end repeat
set {v, d, i} to {0, -1, 1} repeat while v < n ^ 2 if length of m's item i < n then set {end of m's item i, i, v} to {f(v, n), i + d, v + 1} if i < 1 then set {i, d} to {1, -d} else if i > n then set {i, d} to {n, -d} else if i > 1 and (count of m's item (i - 1)) = 1 then set d to -d end if else set {i, d} to {i + 1, 1} end if end repeat
-- Handler/function to format the cells on the fly. on f(v, n) return (characters -(length of (n ^ 2 as string)) thru -1 of (" " & v)) as string end f
-- Reformat the matrix into a table for viewing. set text item delimiters to "" repeat with i in m set i's contents to (i as string) & return end repeat return return & m as string </lang>Output for both scripts is:<lang AppleScript>"
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
<lang c>#include <stdio.h>
- include <stdlib.h>
int main(int c, char **v) { int i, j, m, n, *s;
/* default size: 5 */ if (c < 2 || ((m = atoi(v[1]))) <= 0) m = 5;
/* alloc array*/ s = malloc(sizeof(int) * m * m);
for (i = n = 0; i < m * 2; i++) for (j = (i < m) ? 0 : i-m+1; j <= i && j < m; j++) s[(i&1)? j*(m-1)+i : (i-j)*m+j ] = n++;
for (i = 0; i < m * m; putchar((++i % m) ? ' ':'\n')) printf("%3d", s[i]);
/* free(s) */ return 0; }</lang>output<lang>% ./a.out 7
0 1 5 6 14 15 27 2 4 7 13 16 26 28 3 8 12 17 25 29 38 9 11 18 24 30 37 39 10 19 23 31 36 40 45 20 22 32 35 41 44 46 21 33 34 42 43 47 48</lang>
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>
Clojure
Purely functional approach. <lang Clojure>(defn partitions [sizes coll]
(lazy-seq (when-let [n (first sizes)] (when-let [s (seq coll)] (cons (take n coll)
(partitions (next sizes) (drop n coll)))))))
(defn take-from [n colls]
(lazy-seq (when-let [s (seq colls)] (let [[first-n rest-n] (split-at n s)] (cons (map first first-n)
(take-from n (concat (filter seq (map rest first-n)) rest-n)))))))
(defn zig-zag [n]
(->> (partitions (concat (range 1 (inc n)) (range (dec n) 0 -1)) (range (* n n))) (map #(%1 %2) (cycle [reverse identity]) ,) (take-from n ,)))
user> (zig-zag 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))
user> (zig-zag 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))</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>import std.stdio;
pure nothrow int[][] zigzag(in int n) {
pure nothrow void move(in int n, ref int i, ref int j) { if (j < n - 1) { if (i > 0) i--; j++; } else i++; }
int x, y; auto a = new int[][](n, n); foreach (v; 0 .. n * n) { a[y][x] = v; (x + y) % 2 ? move(n, x, y) : move(n, y, x); } return a;
}
void main() {
foreach (row; zigzag(5)) { foreach (n; row) writef("%3d", n); writeln(); }
}</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
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>
Euphoria
<lang Euphoria>function zigzag(integer size)
sequence s integer i, j, d, max s = repeat(repeat(0,size),size) i = 1 j = 1 d = -1 max = size*size for n = 1 to floor(max/2)+1 do s[i][j] = n s[size-i+1][size-j+1] = max-n+1 i += d j-= d if i < 1 then i += 1 d = -d elsif j < 1 then j += 1 d = -d end if end for return s
end function
? zigzag(5)</lang>
Output:
{ {1,2,6,7,15}, {3,5,8,14,16}, {4,9,13,17,22}, {10,12,18,21,23}, {11,19,20,24,25} }
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>
GAP
<lang gap>ZigZag := function(n)
local a, i, j, k; a := NullMat(n, n); i := 1; j := 1; for k in [0 .. n*n - 1] do a[i][j] := k; if (i + j) mod 2 = 0 then if j < n then j := j + 1; else i := i + 2; fi; if i > 1 then i := i - 1; fi; else if i < n then i := i + 1; else j := j + 2; fi; if j > 1 then j := j - 1; fi; fi; od; return a;
end;
PrintArray(ZigZag(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>
Go
Edge direct algorithm
<lang go>package main
import (
"fmt" "strconv"
)
func zz(n int) []int {
r := make([]int, n*n) i := 0 n2 := n * 2 for d := 1; d <= n2; d++ { x := d - n if x < 0 { x = 0 } y := d - 1 if y > n-1 { y = n - 1 } j := n2 - d if j > d { j = d } for k := 0; k < j; k++ { if d&1 == 0 { r[(x+k)*n+y-k] = i } else { r[(y-k)*n+x+k] = i } i++ } }
return r
}
func main() {
const n = 5 w := len(strconv.Itoa(n*n - 1)) for i, e := range zz(n) { fmt.Printf("%*d ", w, e) if i%n == n-1 { fmt.Println("") } }
}</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
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>
Icon and Unicon
This solution works for both Icon and Unicon.
<lang icon>procedure main(args)
n := integer(!args) | 5 every !(A := list(n)) := list(n) A := zigzag(A) show(A)
end
procedure show(A)
every writes(right(!A,5) | "\n")
end
procedure zigzag(A)
x := [0,0] every i := 0 to (*A^2 -1) do { x := nextIndices(*A, x) A[x[1]][x[2]] := i } return A
end
procedure nextIndices(n, x)
return if (x[1]+x[2])%2 = 0 then if x[2] = n then [x[1]+1, x[2]] else [max(1, x[1]-1), x[2]+1] else if x[1] = n then [x[1], x[2]+1] else [x[1]+1, max(1, x[2]-1)]
end</lang>
Output:
->zz 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 ->
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
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(final 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:
MATLAB
This isn't the best way to solve this task and the algorithm is completely unintuitive without some major exploration of the code. But! It is pretty fast for n < 10000.
<lang MATLAB>function matrix = zigZag(n)
%This is very unintiutive. This algorithm parameterizes the %zig-zagging movement along the matrix indicies. The easiest way to see %what this algorithm does is to go through line-by-line and write out %what the algorithm does on a peace of paper.
matrix = zeros(n); counter = 1; flipCol = true; flipRow = false; %This for loop does the top-diagonal of the matrix for i = (2:n) row = (1:i); column = (1:i); %Causes the zig-zagging. Without these conditionals, you would end %up with a diagonal matrix. To see what happens comment these conditionals out. if flipCol column = fliplr(column); flipRow = true; flipCol = false; elseif flipRow row = fliplr(row); flipRow = false; flipCol = true; end %Selects a diagonal of the zig-zag matrix and places the correct %integer value in each index along that diagonal for j = (1:numel(row)) matrix(row(j),column(j)) = counter; counter = counter + 1; end end
%This for loop does the bottom-diagonal of the matrix for i = (2:n) row = (i:n); column = (i:n); %Causes the zig-zagging. Without these conditionals, you would end %up with a diagonal matrix. To see what happens comment these conditionals out. if flipCol column = fliplr(column); flipRow = true; flipCol = false; elseif flipRow row = fliplr(row); flipRow = false; flipCol = true; end %Selects a diagonal of the zig-zag matrix and places the correct %integer value in each index along that diagonal for j = (1:numel(row)) matrix(row(j),column(j)) = counter; counter = counter + 1; end end
end</lang>
Sample Output: <lang MATLAB>>> zigZag(5)
ans =
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>
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
NetRexx
<lang NetRexx>/* NetRexx */ options replace format comments java crossref savelog symbols binary
zigzag(5)
return
method zigzag(msize) public static
row = 1 col = 1
ziggy = Rexx(0) loop j_ = 0 for msize * msize ziggy[row, col] = j_ if (row + col) // 2 == 0 then do if col < msize then - col = col + 1 else row = row + 2 if row \== 1 then - row = row - 1 end else do if row < msize then - row = row + 1 else col = col + 2 if col \== 1 then - col = col - 1 end end j_
L = (msize * msize - 1).length /*for a constant element width. */ loop row = 1 for msize /*show all the matrix's rows. */ rowOut = loop col = 1 for msize rowOut = rowOut ziggy[row, col].right(L) end col say rowOut end row
return
</lang>
Objeck
<lang ocaml> function : native : ZigZag(size : Int) ~ Int[,] {
data := Int->New[size, size]; i := 1; j := 1; max := size * size; for(element := 0; element < max ; element += 1;) { data[i - 1, j - 1] := element; if((i + j) % 2 = 0) { # even stripes if(j < size){ j += 1; } else{ i+= 2; }; if(i > 1) { i -= 1; }; } else{ # ddd stripes if(i < size){ i += 1; } else{ j+= 2; }; if(j > 1){ j -= 1; }; }; }; 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>
Octave
See the MATLAB solution, which works perfectly in Octave too.
Oz
Implemented as a state machine: <lang oz>declare
%% state move success failure States = unit(right: [ 1# 0 downLeft downInstead] downInstead: [ 0# 1 downLeft terminate] downLeft: [~1# 1 downLeft down] down: [ 0# 1 topRight rightInstead] rightInstead: [ 1# 0 topRight terminate] topRight: [ 1#~1 topRight right])
fun {CreateZigZag N} ZZ = {Create2DTuple N N}
%% recursively walk through 2D tuple and set values proc {Walk Pos=X#Y Count State} [Dir Success Failure] = States.State NextPos = {Record.zip Pos Dir Number.'+'} Valid = {Record.all NextPos fun {$ C} C > 0 andthen C =< N end} NewPos = if Valid then NextPos else Pos end NewCount = if Valid then Count + 1 else Count end NewState = if Valid then Success else Failure end in ZZ.Y.X = Count if NewState \= terminate then {Walk NewPos NewCount NewState} end end in {Walk 1#1 0 right} ZZ end
fun {Create2DTuple W H} T = {MakeTuple unit H} in {Record.forAll T fun {$} {MakeTuple unit W} end} T end
in
{Inspect {CreateZigZag 5}}</lang>
Perl
<lang perl>sub zig_zag {
my ($w, $h, @r, $n) = @_;
$r[ $_->[1] ][ $_->[0] ] = $n++ for sort { $a->[0] + $a->[1] <=> $b->[0] + $b->[1] or
($a->[0] + $a->[1]) % 2 ? $a->[1] <=> $b->[1] : $a->[0] <=> $b->[0] } map { my $e = $_; map{ [$e, $_] } 0 .. $w-1 } 0 .. $h - 1;
@r
}
print map{ "@$_\n" } zig_zag(3, 5);</lang>
Perl 6
Assuming the same Turtle class that is used in Spiral_matrix: <lang perl6>sub MAIN($size as Int) {
my $t = Turtle.new(dir => northeast); my $counter = 0; for 1 ..^ $size -> $run {
for ^$run { $t.lay-egg($counter++); $t.forward; } my $yaw = $run %% 2 ?? -1 !! 1; $t.turn-right($yaw * 135); $t.forward; $t.turn-right($yaw * 45);
} for $size ... 1 -> $run {
for ^$run -> $ { $t.lay-egg($counter++); $t.forward; } $t.turn-left(180); $t.forward; my $yaw = $run %% 2 ?? 1 !! -1; $t.turn-right($yaw * 45); $t.forward; $t.turn-left($yaw * 45);
} $t.showmap;
}</lang>
PHP
<lang php>function ZigZagMatrix($num) {
$matrix = array(); for ($i = 0; $i < $num; $i++){
$matrix[$i] = array(); }
$i=1;
$j=1;
for ($e = 0; $e < $num*$num; $e++) { $matrix[$i-1][$j-1] = $e; if (($i + $j) % 2 == 0) { if ($j < $num){
$j++; }else{ $i += 2; }
if ($i > 1){
$i --; }
} else { if ($i < $num){
$i++; }else{ $j += 2; }
if ($j > 1){
$j --; }
} }
return $matrix; }</lang>
PL/I
<lang PL/I> /* Fill a square matrix with the values 0 to N**2-1, */ /* in a zig-zag fashion. */ /* N is the length of one side of the square. */ /* Written 22 February 2010. */
declare n fixed binary;
put skip list ('Please type the size of the matrix:'); get list (n);
begin;
declare A(n,n) fixed binary; declare (i, j, inc, q) fixed binary;
on subrg snap begin; declare i fixed binary; do i = 1 to n; put skip edit (a(i,*)) (f(4)); end; stop; end;
A = -1; inc = -1; i, j = 1;
loop:
do q = 0 to n**2-1; a(i,j) = q; if q = n**2-1 then leave; if i = 1 & j = n then if iand(j,1) = 1 then /* odd-sided matrix */ do; i = i + 1; inc = -inc; iterate loop; end; else /* an even-sided matrix */ do; i = i + inc; j = j - inc; iterate loop; end; if inc = -1 then if i+inc < 1 then do; inc = -inc; j = j + 1; a(i,j) = q; iterate loop; end; if inc = 1 then if i+inc > n then do; inc = -inc; j = j + 1; a(i,j) = q; iterate loop; end; if inc = 1 then if j-inc < 1 then do; inc = -inc; i = i + 1; a(i,j) = q; iterate loop; end; if inc = -1 then if j - inc > n then do; inc = -inc; i = i + 1; a(i,j) = q; iterate loop; end; i = i + inc; j = j - inc; end;
/* Display the square. */ do i = 1 to n; put skip edit (a(i,*)) (f(4)); end;
end; </lang>
PicoLisp
This example uses 'grid' from "lib/simul.l", which maintains a two-dimensional structure and is normally used for simulations and board games. <lang PicoLisp>(load "@lib/simul.l")
(de zigzag (N)
(prog1 (grid N N) (let (D '(north west south east .) E '(north east .) This 'a1) (for Val (* N N) (=: val Val) (setq This (or ((cadr D) ((car D) This)) (prog (setq D (cddr D)) ((pop 'E) This) ) ((pop 'E) This) ) ) ) ) ) )
(mapc
'((L) (for This L (prin (align 3 (: val)))) (prinl) ) (zigzag 5) )</lang>
Output:
1 2 6 7 15 3 5 8 14 16 4 9 13 17 22 10 12 18 21 23 11 19 20 24 25
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>
PowerShell
<lang PowerShell>function zigzag( [int] $n ) {
$zigzag=New-Object 'Object[,]' $n,$n $nodd = $n -band 1 $nm1 = $n - 1 $i=0; $j=0; foreach( $k in 0..( $n * $n - 1 ) ) { $zigzag[$i,$j] = $k $iodd = $i -band 1 $jodd = $j -band 1 if( ( $j -eq $nm1 ) -and ( $iodd -ne $nodd ) ) { $i++ } elseif( ( $i -eq $nm1 ) -and ( $jodd -eq $nodd ) ) { $j++ } elseif( ( $i -eq 0 ) -and ( -not $jodd ) ) { $j++ } elseif( ( $j -eq 0 ) -and $iodd ) { $i++ } elseif( $iodd -eq $jodd ) { $i-- $j++ } else { $i++ $j-- } } ,$zigzag
}
function displayZigZag( [int] $n ) {
$a = zigzag $n 0..$n | ForEach-Object { $b=$_ $pad=($n*$n-1).ToString().Length "$(0..$n | ForEach-Object { "{0,$pad}" -f $a[$b,$_] } )" }
}</lang>
Prolog
Works with SWi-Prolog. <lang Prolog>zig_zag(N) :- zig_zag(N, N).
% compute zig_zag for a matrix of Lig lines of Col columns zig_zag(Lig, Col) :- length(M, Lig), maplist(init(Col), M), fill(M, 0, 0, 0, Lig, Col, up), % display the matrix maplist(print_line, M).
fill(M, Cur, L, C, NL, NC, _) :-
L is NL - 1,
C is NC - 1,
nth0(L, M, Line),
nth0(C, Line, Cur).
fill(M, Cur, L, C, NL, NC, Sens) :- nth0(L, M, Line), nth0(C, Line, Cur), Cur1 is Cur + 1, compute_next(NL, NC, L, C, Sens, L1, C1, Sens1), fill(M, Cur1, L1, C1, NL, NC, Sens1).
init(N, L) :-
length(L, N).
% compute_next % arg1 : Number of lnes of the matrix % arg2 : number of columns of the matrix % arg3 : current line % arg4 : current column % arg5 : current direction of movement % arg6 : nect line % arg7 : next column % arg8 : next direction of movement compute_next(_NL, NC, 0, Col, up, 0, Col1, down) :- Col < NC - 1, Col1 is Col+1.
compute_next(_NL, NC, 0, Col, up, 1, Col, down) :- Col is NC - 1.
compute_next(NL, _NC, Lig, 0, down, Lig1, 0, up) :- Lig < NL - 1, Lig1 is Lig+1.
compute_next(NL, _NC, Lig, 0, down, Lig, 1, up) :- Lig is NL - 1.
compute_next(NL, _NC, Lig, Col, down, Lig1, Col1, down) :- Lig < NL - 1, Lig1 is Lig + 1, Col1 is Col-1.
compute_next(NL, _NC, Lig, Col, down, Lig, Col1, up) :- Lig is NL - 1, Col1 is Col+1.
compute_next(_NL, NC, Lig, Col, up, Lig1, Col1, up) :- Col < NC - 1, Lig1 is Lig - 1, Col1 is Col+1.
compute_next(_NL, NC, Lig, Col, up, Lig1, Col, down) :- Col is NC - 1, Lig1 is Lig + 1.
print_line(L) :-
maplist(print_val, L),
nl.
print_val(V) :- writef('%3r ', [V]). </lang> Output :
?- zig_zag(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 true . ?- zig_zag(5, 7). 0 1 5 6 14 15 24 2 4 7 13 16 23 25 3 8 12 17 22 26 31 9 11 18 21 27 30 32 10 19 20 28 29 33 34 true . ?- zig_zag(7,5). 0 1 5 6 14 2 4 7 13 15 3 8 12 16 24 9 11 17 23 25 10 18 22 26 31 19 21 27 30 32 20 28 29 33 34 true .
PureBasic
<lang PureBasic>Procedure zigZag(size)
Protected i, v, x, y Dim a(size - 1, size - 1) x = 1 y = 1 For i = 1 To size * size ;loop once for each element a(x - 1, y - 1) = v ;assign the next index If (x + y) & 1 = 0 ;even diagonal (zero based count) If x < size ;while inside the square If y > 1 ;move right-up y - 1 EndIf x + 1 Else y + 1 ;on the edge increment y, but not x until diagonal is odd EndIf Else ;odd diagonal (zero based count) If y < size ;while inside the square If x > 1 ;move left-down x - 1 EndIf y + 1 Else x + 1 ;on the edge increment x, but not y until diagonal is even EndIf EndIf v + 1 Next ;generate and show printout PrintN("Zig-zag matrix of size " + Str(size) + #CRLF$) maxDigitCount = Len(Str(size * size)) + 1 For y = 0 To size - 1 For x = 0 To size - 1 Print(RSet(Str(a(x, y)), maxDigitCount, " ")) Next PrintN("") Next PrintN("")
EndProcedure
If OpenConsole()
zigZag(5) zigZag(6) Print(#CRLF$ + #CRLF$ + "Press ENTER to exit") Input() CloseConsole()
EndIf</lang> Sample output:
Zig-zag matrix of size 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 Zig-zag matrix of size 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
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 35
Alternative 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>
Qi
This is a purely functional, very inefficient, and straight forward solution. The code can probably be simplified somewhat.
<lang qi> (define odd? A -> (= 1 (MOD A 2))) (define even? A -> (= 0 (MOD A 2)))
(define zigzag-val
0 0 N -> 0
X 0 N -> (1+ (zigzag-val (1- X) 0 N)) where (odd? X) X 0 N -> (1+ (zigzag-val (1- X) 1 N))
0 Y N -> (1+ (zigzag-val 1 (1- Y) N)) where (odd? Y) 0 Y N -> (1+ (zigzag-val 0 (1- Y) N))
X Y N -> (1+ (zigzag-val (MAX 0 (1- X)) (MIN (1- N) (1+ Y)) N)) where (even? (+ X Y)) X Y N -> (1+ (zigzag-val (MIN (1- N) (1+ X)) (MAX 0 (1- Y)) N)))
(define range
E E -> [] S E -> [S|(range (1+ S) E)])
(define zigzag
N -> (map (/. Y (map (/. X (zigzag-val X Y N)) (range 0 N))) (range 0 N)))
</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>
REXX
<lang rexx> /*REXX program to produce a zig-zag matrix (array) and display it. */ row=1; col=1; parse arg n .; if n== then n=5 /*assume the default.*/
do j=0 for n*n @.row.col=j if (row+col)//2==0 then do if col<n then col=col+1; else row=row+2 if row\==1 then row=row-1 end else do if row<n then row=row+1; else col=col+2 if col\==1 then col=col-1 end end
L=length(n*n-1) /*for a constant element width. */
do row=1 for n /*show all the matrix's rows. */ _= do col=1 for n; _=_ right(@.row.col,L); end say _ end
</lang> Output when using the default of 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
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
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>
Seed7
<lang seed7>$ include "seed7_05.s7i";
const type: matrix is array array integer;
const func matrix: zigzag (in integer: size) is func
result var matrix: s is matrix.value; local var integer: i is 1; var integer: j is 1; var integer: d is -1; var integer: max is 0; var integer: n is 0; begin s := size times size times 0; max := size ** 2; for n range 1 to max div 2 + 1 do s[i][j] := n; s[size - i + 1][size - j + 1] := max - n + 1; i +:= d; j -:= d; if i < 1 then incr(i); d := -d; elsif j < 1 then incr(j); d := -d; end if; end for; end func;
const proc: main is func
local var matrix: s is matrix.value; var integer: i is 0; var integer: num is 0; begin s := zigzag(7); for i range 1 to length(s) do for num range s[i] do write(num lpad 4); end for; writeln; end for; end func;</lang>
Output:
1 2 6 7 15 16 28 3 5 8 14 17 27 29 4 9 13 18 26 30 39 10 12 19 25 31 38 40 11 20 24 32 37 41 46 21 23 33 36 42 45 47 22 34 35 43 44 48 49
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>>>
- Programming Tasks
- Matrices
- ActionScript
- Ada
- ALGOL 68
- APL
- AppleScript
- AutoHotkey
- C
- C++
- C sharp
- Clojure
- Common Lisp
- D
- E
- Euphoria
- Fan
- Forth
- Fortran
- GAP
- Go
- Groovy
- Haskell
- Icon
- Unicon
- J
- Java
- JavaScript
- Lua
- M4
- Mathematica
- MATLAB
- Modula-3
- NetRexx
- Objeck
- OCaml
- Octave
- Oz
- Perl
- Perl 6
- PHP
- PL/I
- PicoLisp
- PostScript
- PowerShell
- Prolog
- PureBasic
- Python
- Qi
- R
- REXX
- Ruby
- Scala
- Seed7
- Tcl
- Ursala