Talk:Zig-zag matrix
reading the J examples
I noticed this in the Haskell example:
Computing the array: ... -- (The author of this example thinks the algorithm could be better, but can't read the J examples.)
I can spell out the J examples in more detail. I'm not sure that it will help much, because J has a rich set of primitives (built in operations), so recreating the example in another language will entail recreating the primitives, too. So you might not save much work.
exposition
None the less, let's start with the solution which is probably easiest to rewrite in another language.
zz4 =: $ [: /:@:; ] (+/@#: <@(A.~_2|#)/. ]) [: i. */
list of integers
To break this down, the first major construct is:
integers =: [: i. */
This simply produces the first N non-negative integers, where N is the product of its argument. For example, if we want a 3x3 matrix, then:
integers 3 3 0 1 2 3 4 5 6 7 8
So integers is basically the input vector we want to rearrange into the zigzag matrix.
anti-diagonals
The next major part of the function is
antid =: +/@#: <@(A.~_2|#)/. ]
which generates the anti-diagonals (and reverses them if appropriate). This itself is composed of 3 parts, +/@#:, <@(A.~_2|#)/., and ]. The first of these, +/@#: gives the sum of the coordinates of each element of the matrix. Let's ignore the details of why for now, and just look at an example.
If we have a 3 by 3 matrix, like this:
i. 3 3 0 1 2 3 4 5 6 7 8
Then these are the coordinates of each number in that matrix:
3 3 <@#: i. 3 3 +---+---+---+ |0 0|0 1|0 2| +---+---+---+ |1 0|1 1|1 2| +---+---+---+ |2 0|2 1|2 2| +---+---+---+
And these are the sums of those coordinates:
3 3 +/@#: i. 3 3 0 1 2 1 2 3 2 3 4
Notice a regularity there? Look at the antidiagonals:
</. 3 3 +/@#: i. 3 3 +-+---+-----+---+-+ |0|1 1|2 2 2|3 3|4| +-+---+-----+---+-+
Along each antidiagonal, the sum of the coordinates is constant (this isn't surprising, but it may not be obvious). We will use this observation in a moment.
classification
For now, let's get back to antid. The second component of that function is <@(A.~_2|#)/. . The most important feature of that component is that it classifies its input. That is, it breaks it into buckets. Given a list of buckets on the left, and data on the right, for each item of the data (on the right), it will look at the corresponding bucket number (on the left) and put the data-item into that bucket. An example:
NB. Classify by even and odd
0 1 0 1 0 1 </. 0 1 2 3 4 5
+-----+-----+
|0 2 4|1 3 5|
+-----+-----+
NB. Classify by vowel and consonant
0 1 0 0 1 0 0 1 0 0 0 </. 'hello world'
+--------+---+
|hll wrld|eoo|
+--------+---+
NB. Classify by sign (positive, negative, or zero)
2 1 0 1 1 2 0 0 2 2 1 0 2 2 </. 1 _2 0 _3 _4 5 0 0 6 7 _8 0 9 10
+------------+-----------+-------+
|1 5 6 7 9 10|_2 _3 _4 _8|0 0 0 0|
+------------+-----------+-------+
In this case, we're going to classify integers by the sum-of-the-coordinates, calculated earlier. As we observed, that sum is constant along the antidiagonals of the matrix, so we're effectively putting each antidiagonal into its own bucket.
input_list =. integers 3 3 sum_of_coordinates =. 3 3 +/@#: input_list sum_of_coordinates </. input_list +-+---+-----+---+-+ |0|1 3|2 4 6|5 7|8| +-+---+-----+---+-+
conditional reversal
The final transformation antid applies is that it reverses each antidiagonal as appropriate. Basically the primitive A. gets an integer on the left, and a list on the right. The integer is an index into the table of all possible permutations of the data. For example, there are only 6 ways to permute a list of 3 items:
(A.~ i.@:!@:#) 'ABC' ABC ACB BAC BCA CAB CBA
Whereas there are 24 ways to permute a list of 4 items, 120 for a list of 5, etc. Another thing to notice is that the table of permutations is in lexographic order. That is, it's sorted. In particular, the identity permutation is always first, and the permutation that reverses the data is always last (see the first and last rows of the example output, above). So given the index -1, A. will reverse the data, and given the index 0, it will leave the data alone. Example:
_1 A. 'ABC'
CBA
0 A. 'ABC'
ABC
We can use this fact to reverse a list based on a condition. We want to reverse every other antidiagonal, which is the same as saying we want to reverse the odd antidiagonals. We observe that odd antidiagonals have odd lengths, and even antidiagonals have even lengths. Which is to say, the length of the antidiagonal, mod 2, tells us whether we want to reverse that antidiagonal or not. Combining this observation with the property of A. highlighted above, we simply take the negation of its length, mod 2 as the index into its permutation table. If the antidiagonal is odd (every other antidiagonal), it is reversed, otherwise left alone (it is worth noting that J treats negative arguments to modulous consistently, so that we can say _2 | x to get 0 or _1, rather than having negate-the-mod in two steps).
Therefore antid classifies the input into its antidiagonals, reversed appropriately. OK, almost home.
reordering
So now we have:
zz4 =: ($ [: /:@:; ] antid integers)
The ] antid integers generates the input list and uses that to calculate the antidiagonals, as we have seen:
(] antid integers) 3 3 +-+---+-----+---+-+ |0|1 3|6 4 2|5 7|8| +-+---+-----+---+-+
The penultimate part,
reorder =: /:@:;
returns the antidiagonals to a list of integers, and reorders it. Example:
; (] antid integers) 3 3 0 1 3 6 4 2 5 7 8
Turning a list-of-lists into a flat list isn't interesting, but the reordering is. We now have a list of integers in the order they'd appear if you walked along the antidiagonals. But no one walks along a matrix's antidiagonals -- we walk along the rows, left-to-right, top-to-bottom. Here's how the list would look if you tried to walk that way along them, without reordering first:
3 3 $ 0 1 3 6 4 2 5 7 8 0 1 3 6 4 2 5 7 8
Which doesn't make sense, because we've ordered them one way, but we're trying to read them another way. What we want to do is read them in order. We want to visit 0 first, 1 second, 2 third, etc. That is, we want to know what we'd have to do to sort the array. More precisely, we want to know how to permute the array to make it sorted.
Many languages have built-in sort functions, and J is no different in that regard. It is, however, different in how far it generalizes the concept. In J, more than just sorting an array, you can (must) grade it. That is, "this comes first, this comes second, this comes third". That is the function of the primitive /: (read "grade down", and its counterpart, \: "grade up").
For example, if we grade a list, it is like grading a school class; it tells us who's first, who's second, etc:
/: 'ECDFAB' 4 5 1 2 0 3
Then, if we use those numbers to index into the list:
4 5 1 2 0 3 { 'ECDFAB'
ABCDEF
Voila, the list is sorted (we could've done this in one step, with /:~'ECDFAB'). So, taking our anti-diagonals:
AD =: (] antid integers) 3 3 AD +-+---+-----+---+-+ |0|1 3|6 4 2|5 7|8| +-+---+-----+---+-+
We want to know what we'd have to do to walk along them in row order (that is: "first go to 0 (in the first position), then step to one (in the second position), then jump all the way to 2 (which is in the sixth position), then jump BACK to 3 (which is in the third position), then to 4 (in the fifth position), ...":
reorder AD 0 1 5 2 4 6 3 7 8
So now, if we read these in row-order we see:
3 3 $ reorder AD 0 1 5 2 4 6 3 7 8
Which is exactly what we wanted.
reshaping
Incidentally, the $ in the expression above serves exactly the same purpose as it does in the original expression: it reshapes the list into a matrix.
reshape =: $
succinctness is power
Putting all the above together, we can read the original expression as:
zz4 =: reshape [: reorder ] antid integers
Which is exactly what it does.
So now you can see why "J has no words". It took me over 2000 words to describe what the J expression did in less than 40 characters, and I left out much detail (both logical and technical; for example, all the edge cases are handled transparently). That is a very good compression ratio; we get a lot for a little. If you were as fluent in J as you are in English, you could've read and understood the J in maybe a tenth the time it took you to read this exposition.
Didn't Paul Graham say "succinctness is power"?
epilogue
Incidentally, I chose the expression zz4 not because it is the best, but because I thought it would be most easily translated to another language (given an exposition). In fact, you'll notice that except for the last transformation (reshape) the entire function works on a list of numbers.
But there is no reason this should be so; J is a master of multidimensional arrays, and there is no reason would should constrain the function by making it work on a one-dimensional list. For example, there is no need for the defined function integers; the built in primitve i. will more than suffice:
i. 3 3 0 1 2 3 4 5 6 7 8
And there is no reason to calculate the sum-of-the-coordinates; we can access the anti-diagonals directly:
</. i. 3 3 +-+---+-----+---+-+ |0|1 3|2 4 6|5 7|8| +-+---+-----+---+-+
And there's no reason to muck about with permutation tables or modulous, J can loop over a list of functions just as easily as other languages can loop over lists of data:
<@|.`</. i. 3 3 NB. Reverse or don't, cyclically. +-+---+-----+---+-+ |0|1 3|6 4 2|5 7|8| +-+---+-----+---+-+
(I did say J has a rich set of primitives.)
So, in fact, if we stop working against the grain of J and start out with a multi-dimensional array in the first place, the expression becomes much shorter and sweeter:
zz4 =: $ [: /:@:; ] (+/@#: <@(A.~_2|#)/. ]) [: i. */ zz0 =: $ [: /:@; [: <@|.`</. i. zz4 3 3 0 1 5 2 4 6 3 7 8 zz0 3 3 0 1 5 2 4 6 3 7 8
And that's why I like J.
further J exposition
One thing that may not be clear about the J code, and therefore might render it confusing, is that is has no variables. It is completely functional, and the arguments are implicit (the arragement of the expression determines how and where inputs and results are passed).
A verbose version of this functional expression might be written:
zigZag =: rearrange (antidiagonals integerList)
rearrange =: reshape reorder
reshape =: $
reorder =: grade@flatten
grade =: /:
flatten =: ;
antidiagonals =: sumOfCoords rClass identity
sumOfCoords =: sum@antibase
sum =: +/
antibase =: #:
rClass =: <@maybeRevers classify
maybeRevers =: permute~ evenOrOdd
permute =: A.
evenOrOdd =: _2 mod len
mod =: |
len =: #
classify =: /.
identity =: ] NB. Copy of argument
integerList =: zeroToN_1@product
zeroToN_1 =: i.
product =: */ NB. Note resemblance to sum ('/' is zipWith)
To explicitly recreate the function calls that occur when the function is invoked (with assignments being what the interpreter actually does, and everything else just to show you what's going on):
INPUT =: 3 3
PRODUCT =: product INPUT
PRODUCT
9
INTEGERLIST =: zeroToN_1 PRODUCT
INTEGERLIST
0 1 2 3 4 5 6 7 8
INPUT <@antibase INTEGERLIST
+---+---+---+---+---+---+---+---+---+
|0 0|0 1|0 2|1 0|1 1|1 2|2 0|2 1|2 2|
+---+---+---+---+---+---+---+---+---+
INPUT sum@antibase INTEGERLIST
0 1 2 1 2 3 2 3 4
SUMOFCOORDS=:INPUT sumOfCoords INTEGERLIST
SUMOFCOORDS
0 1 2 1 2 3 2 3 4
SUMOFCOORDS <classify INTEGERLIST NB. Anti-diagonals
+-+---+-----+---+-+
|0|1 3|2 4 6|5 7|8|
+-+---+-----+---+-+
SUMOFCOORDS evenOrOdd classify INTEGERLIST NB. Anti-diagonal lengths alternate, even and odd
_1 0 _1 0 _1
0 permute 1 2 3 NB. 0 permute X is just X
1 2 3
_1 permute 1 2 3 NB. _1 permute X is X reversed
3 2 1
maybeRevers 1 2 3 NB. Odd lengths reversed
3 2 1
maybeRevers 1 2 3 4 NB. Even lengths left alone
1 2 3 4
ANTID =: SUMOFCOORDS rClass INTEGERLIST
ANTID NB. Anti-diagonals, appropriately reversed
+-+---+-----+---+-+
|0|1 3|6 4 2|5 7|8|
+-+---+-----+---+-+
flatten ANTID NB. Not exciting
0 1 3 6 4 2 5 7 8
grade FLAT_ANTID NB. How to permute, in order to sort
0 1 5 2 4 6 3 7 8
REORDERED=:reorder ANTID
REORDERED
0 1 5 2 4 6 3 7 8
INPUT reshape REORDERED NB. Make it a matrix
0 1 5
2 4 6
3 7 8
ZIGZAG=:INPUT reshape REORDERED NB. Done
ZIGZAG
0 1 5
2 4 6
3 7 8
So, to transliterate this to another (inconsistent) pseudo-language:
function zigZag(int-list INPUT) as matrix
{
return rearrange(INPUT, antidiagonals(INPUT,integerList(INPUT))
}
function rearrange(int-list SHAPE, int-list-list ANTIDIAGONALS) as matrix
{
return reshape(SHAPE,reorder(ANTIDIAGONALS))
}
function reorder(int-list-list ANTIDIAGONALS) as int-list
{
RESULTS = []
for each ANTIDIAGONAL in ANTIDIAGONALS
{
RESULTS.append(ANTIDIAGONAL) // Flatten the list-list to a list
}
return grade(RESULTS)
}
function antidiagonals(int-list INPUT, int-list INTEGERS) as int-list-list
{
// Note classify has a function-argument
CLASSES = classify(sumOfCoords(INPUT, INTEGERS), INTEGERS)
RESULTS = []
for each CLASS in CLASSES
{
RESULTS.append(maybeReverse(CLASS))
}
return RESULTS
}
function sumOfCoords(int-list INPUT, int-list INTEGERS) as int-list
{
COORDINATES = antibase(INPUT, INTEGERS)
RESULTS = []
for each COORDINATE in COORDINATES
{
RESULTS.append(sum(COORDINATE))
}
return RESULTS
}
function maybeReverse(int-list LIST) as int-list
{
if ( len(LIST) mod 2 )
{
return reverse(LIST) // FIXME: Fully implement A. (permutation table)
}
else
{
return LIST
}
}
function integerList(int-list INPUT) as int-list
{
PROD = product(INPUT)
return [0 .. (PROD-1)]
}
The uninmplemented functions (e.g. antibase) are primitives, or simple combinations of primitives, in J. You can get the formal specifications at The J Vocabulary. For example, see the definition of antibase.
Reply
Thanks for the info! I've updated the Haskell example with a better algorithm based on your techniques. (By the way, I think this explanation is worth keeping around; perhaps it should be moved to something like Zig Zag/J explanation and linked from the example?) --Kevin Reid 17:49, 4 August 2008 (UTC)
- I took the fact that you sorted in the Haskell example and worked it out for myself for the Python example, before thinking of reading this talk page. So I have my own explanation. --Paddy3118 04:12, 5 August 2008 (UTC)
Even though J looks so strange and hard to me, this algo so explained and encoded gave me the idea that J deserves a look and more:) --ShinTakezou 01:00, 16 December 2008 (UTC)
Error in Pascal example
Pascal example works only for odd matrix dimensions.
Now fixed --Tigerofdarkness (talk) 10:11, 2 September 2016 (UTC)
The first N squared integers
Integers start at minus a very big number. So this is not what the task description means. Positive integers start at 1, this would be my preferred requirement, but many already start at zero which is neither positive nor negative. The task description needs correction.--Nigel Galloway (talk) 13:55, 24 January 2020 (UTC)
- I agree wholeheartedly. Or, as one often votes on Rosetta Code, +1. I also have brought up more than a few similar arguments before, as in a positive integer > 0, or a positive integer, and then use a 0 (zero) in the example input for the task. It's an uphill battle, not the least of which is when a number is used when an integer is meant. I have since stopped pointing out the obvious, ya can't win when ya argue with people who buy ink by the barrel. -- Gerard Schildberger (talk) 20:46, 24 January 2020 (UTC)
- It is an old task with many solutions; maybe rewording to include a start of zero or one would be better as the main idea of the task is the zig-zaggedness and starting from one or zero would still allow implementations to be compared? --Paddy3118 (talk) 21:21, 24 January 2020 (UTC)
- I addressed this problem when I entered the REXX language solution, the computer program allowed the invoker to specify a starting number, but any integer could be used. It doesn't fix the problem with the task's requirements, but it allows the user to choose which integer to start the zig-zag matrix with. -- Gerard Schildberger (talk) 21:39, 24 January 2020 (UTC)
- The problem with using phrases like natural numbers and/or counting numbers is that there isn't a clear and agreed-upon definition(s), some include zero, others do not. The same problem exists with whole numbers. Note that Wikipedia says that in computer science, natural numbers always includes zero. -- Gerard Schildberger (talk) 21:42, 24 January 2020 (UTC)
what is the first natural number?
So the question is now, what is the first natural number? -- Gerard Schildberger (talk) 21:52, 24 January 2020 (UTC)
- If we allow zero or one to both be allowed then it could mean minimal rework of examples whilst hopefully retaining the spirit of the old task?
- (I am a little biased, as this is one of the existing tasks that first attracted me to RC - I based the second task I started, "Spiral matrix", on this one and have fond memories).
- --Paddy3118 (talk) 09:20, 25 January 2020 (UTC)
Pattern of memory addresses
If we assume that each entry is stored consecutively in memory like so (using size 5 as an example), and assuming an 8-bit computer where each memory address holds a byte and each address is 16-bit
;these are memory locations, the values within are as in the example. $1200 $1201 $1202 $1203 $1204 $1205 $1206 $1207 $1208 $1209 $120A $120B $120C $120D $120E $120F $1210 $1211 $1212 $1213 $1214 $1215 $1216 $1217 $1218
Then to get to the next memory address, we add the following numbers to the one we're at. Let N = the size of the array and K = N-1. Then:
$1200 + 1 = $1201 $1201 + K = $1205 $1205 + N = $120A $120A - K = $1206 $1206 - K = $1202 $1202 + 1 = $1203 $1203 + K = $1207 $1207 + K = $120B $120B + K = $120F $120F + N = $1214 $1214 - K = $1210 $1210 - K = $120C $120C - K = $1208 $1208 - K = $1204 $1204 + N = $1209 $1209 + K = $120D $120D + K = $1211 $1211 + K = $1215 $1215 + 1 = $1216 $1216 - K = $1212 $1212 - K = $120E $120E + N = $1213 $1217 + 1 = $1218
It seems to follow this pattern:
+1, +K, +N, -2K, +1, +3K, +N, -(K^2), +1, +N, +3K, +1, -2K, +N, +K, +1
I tried it again with a N=4 and got this sequence:
+1, +K, +N, -2K, +1, +(K^2), +1, -2K, +N, +K, +1
If you remove the and +1 after it, the sequence is symmetric.
Might be helpful for establishing a pattern. I'll work on it more later. This logic should extend to 32-bit CPUs if you multiply N and K by 4.--Puppydrum64 (talk) 17:06, 15 September 2021 (UTC)
- Hi Puppydrum64; at the top of the talk page the author of the J example talks about his solution that exploits patterns in indices. I just noticed that sort was involved and worked out something for the Python entry and explained it in my blog: paddy3118 blog explanation.