Zig-zag matrix: Difference between revisions
m (→{{header|Fortran}}: +lang tag) |
|||
Line 497: | Line 497: | ||
key = lambda (x,y): (x+y, -y if (x+y) % 2 else y) ) |
key = lambda (x,y): (x+y, -y if (x+y) % 2 else y) ) |
||
return dict((index,n) for n,index in enumerate(indexorder)) |
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): |
def printzz(myarray): |
||
n = |
n = math.round(math.sqrt(len(myarray))) |
||
for x in range(n): |
for x in range(n): |
||
for y in range(n): |
for y in range(n): |
Revision as of 11:00, 27 February 2009
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 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>