Mainly Tech projects on Python and Electronic Design Automation.

Monday, August 04, 2008

Zig Zag

Yet another problem from Rosetta Code.
The problem statement is:
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 example:
 0  1  5  6
 2  4  7 12
 3  8 11 13
 9 10 14 15
Or take a look at this.
I read all the other answers and saw a very short  example in the J language, which looked like line noise to me, as well as a fairly short example in Haskel a programming language I don't know, but I got a hint as to how it is done by the mention of sorting indeces.

I printed a sheet of graph paper, drew a 6 by 6  grid and put in the zig-zag numbers, after a few false starts I realised that what distinguishes a diagonal is if the top left is coordinate 0,0; x increases to the right, and y increases  going down the rows, then the sum of the induces is constant for a diagonal.

If we are going to do some sorting then we need to sort first on the sum of the indeces. 

Next, you find that when the sum is odd you are 'going' down the diagonal so increasing y gives the sort order and vice versa, so secondly sort on  -y if the sum of the coordinates is even, otherwise +y.

The sort will give the order of the coordinates enumerate the order and you get what integer goes in which location et voila!.

The code:

The sort is split between the iterable which simply generates the coordinate pairs and the key function  which returns a tuple of the tho elements highlighted above for sorting the coordinates (Its equivalent to the decorate-sort-undecorate or Schwartzian sort method for any non-Pythoneers).  It is the main part of the program:

zigzag algorithm
Description from:
Code Author: Donald 'Paddy' McCarthy
def zigzag(n):
 indexorder = sorted(((x,y) for x in range(n) for y in range(n)),
   key = lambda p: (p[0]+p[1], -p[1] if (p[0]+p[1]) % 2 else p[1]) )
 return dict((index,n) for n,index in enumerate(indexorder))
def printzz(myarray):
 n = int(len(myarray)** 0.5 +0.5)
 for x in range(n):
  for y in range(n):
   print "%2i" % myarray[(x,y)],
Running the code produces:
 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

Now to add it to Rosetta Code.

1 comment:

  1. ...And if I'd read the Rosetta Code Talk page I could have read a lot more about the J. example.
    Oh well. It was good to work it out for myself.

    - Paddy.



Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!