Zig Zag

From Rosetta Code

Jump to: navigation, search

Programming Task
This is a programming task. It lays out a problem which Rosetta Code users are encouraged to solve, using languages they know.

Code examples should be formatted along the lines of one of the existing prototypes.

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

Contents

[edit] 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;
 

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

[edit] APL

Works with: Dyalog APL Translation of: J 

      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

[edit] Common Lisp

Translation of: Java (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))))

[edit] D

Translation of: Common Lisp 

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

[edit] 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)]

[edit] 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

[edit] Java

Translation of: Ada 

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

[edit] OCaml

Translation of: Common Lisp 

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

[edit] Perl

Translation of: Haskell 

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

[edit] Python

There is a full explanation of the algorithm used here. 

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))
def printzz(myarray):
    n = int(math.sqrt(len(myarray)) +0.5)
    for x in range(n):
        for y in range(n):
                print "%2i" % myarray[(x,y)],
        print
 
printzz(zigzag(6))

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, Translation of: Common Lisp. 

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

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]]
Retrieved from "http://rosettacode.org/wiki/Zig_Zag"
Personal tools