Talk:Spiral matrix
Explanation of Python code
See Spiral. --Paddy3118 06:30, 5 August 2008 (UTC)
- At least for the iterative solution. --Paddy3118 10:48, 5 August 2008 (UTC)
J
Unlike the concise solution to ZigZag, this J function works entirely on a list, until the very end, when it reshapes the 1D list into the 2D array.
So if SPIRAL:
SPIRAL=:spiral 5
is our spiral array, then ,SPIRAL is the rows catenated together:
,SPIRAL 0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
insight no. 1
Nothing about this list pops out at me, but if you read the original article, you'll see a smart J guy (Joey Tuttle) noticed that this list looks like the grade of another list.
aside: grading
As I said in my earlier exposition, a grade represents the permutation vector required to sort the list.
Let's say in some non-J language, you had a list of chars:
['E','C','D','F','A','B' ]
Well, if you take that list, and make it a 2D array where the chars are the first column, and the index is the second column:
[ ['E',0],
['C',1],
['D',2],
['F',3],
['A',4],
['B',5] ]
And then sort that 2D array (either by the first column, or by both, which is equivalent), you'd get this:
[ ['A',4], ['B',5], ['C',1], ['D',2], ['E',0] ]
Pulling out the second column from the matrix (the integers), you'd get this:
[4,5,1,2,0]
Which is the grade.
Well, in J, you don't use sort to get the grade, you use grade to get the sort. For example, get the grade:
/:'ECDFAB' 4 5 1 2 0 3
then use that grade to index into the array:
4 5 1 2 0 3 { 'ECDFAB'
ABCDEF
(in J indexing is a function, not part of the syntax. So, for example, x[4] in C becomes 4{x in J).
chasing Joey
Ok, back to the spiral. When we left off, Joey had begun to suspect that ,SPIRAL was actually a permutation vector. That is, that ,SPIRAL was the result of grading some other list. More formally, he suspected:
(,SPIRAL) = (/: something_else)
But how to find something_else? Well, it may not be obvious, but /: is self-inverse. That is, if you apply it twice, it "undoes" itself.
/: 4 5 1 2 0 3 4 2 3 5 0 1 /: /: 4 5 1 2 0 3 4 5 1 2 0 3 4 5 1 2 0 3 = (/: /: 4 5 1 2 0 3) 1 1 1 1 1 1
So, since we know
something_else = (/: /: something_else)
and
(,SPIRAL) = (/: something_else)
then, by substitution, we know
something_else = (/: , SPIRAL)
If you're still iffy on function inverse, don't worry, we'll return to it later, and find out a more formal way to ask J to invert a function for us.
In any case, let's see what Joey saw:
/: , SPIRAL 0 1 2 3 4 9 14 19 24 23 22 21 20 15 10 5 6 7 8 13 18 17 16 11 12
insight no. 2
I don't see obvious patterns when I look at the result of /: , SPIRAL above. But then, I'm not as smart as Joey. When he looked at it, he had a second insight: this array looks like a running-sum.
Here's what I mean by running-sum:
+/\ 1 2 3 4 NB. running sum 1 3 6 10 (1),(1+2),(1+2+3),(1+2+3+4) 1 3 6 10
Formally, Joey suspected:
(/: , SPIRAL) = (+/\ another_thing)
But obviously +/\ is not self-inverse. So how can we discover another_thing?
We ask J to do it for us.
aside: calculus of functions
J provides for a calculus of functions. What is a "calculus of functions"? Well, just like functions act on data to produce data, we can have meta-functions that operate on functions to produce functions.
Think back to math notation 1:
log x # (1) log of x log x2 # (2) log of x * x log2 x # (3) log of log of x
Read the (3) again. How is it different from (2)? In (2), x has been manipulated, but in (3) log has been manipulated!
That is, in (2), there are two instances of x (in x*x), but in (3) there are two instances of log (in log(log(x))).
Analogously in J:
log =: 10&^. NB. "^." is the log function in J x =: 100 log x NB. (1) log of x 2 log x^2 NB. (2) log of x*x 4 log^:2 x NB. (3) log of log of x 0.30103
Now let's take this one step further. You'll remember the notation
x-1 # (4)
meant 1/x, that is, the inverse of the number x. But what did
log-1 # (5)
mean? By analogy to (4), (5) meant the inverse of the log function.
Analogously in J:
x^_1 NB. (4) 0.01 log x 2 log_inverse =: log^:_1 NB. (5) log_inverse log x 100
Neat, huh?
caught him!
So what does all this have to do with our hero, Joey? Well, if you remember, he had the insight that (/: , SPIRAL) =(+/\ another_thing). But he was stumped: +/\ is not self-inverse, so how could he recover another_thing?
Well, now we know how he proceeded: +/\^:_1. Let's follow him:
+/\^:_1 /: ,SPIRAL 0 1 1 1 1 5 5 5 5 _1 _1 _1 _1 _5 _5 _5 1 1 1 5 5 _1 _1 _5 1
Eureka! This list clearly shows a pattern. We can simply replicate the pattern, then undo (invert) the operations that generated it from SPIRAL, and we'll have our SPIRAL back.
home again
Put another way: if we can generate these ones-and-fives, we can generate SPIRAL. How? Well, since we generated the ones-and-fives from SPIRAL using:
ones_and_fives =. +/\^:_1 /: , SPIRAL
Then we need to do the opposite of that to recover SPIRAL. To break this procedure down, we have:
func3 =. +/\^:_1 func2 =. /: func1 =. , ones_and_fives =. func3 func2 func1 SPIRAL
Obviously if you're doing the "opposite" of something you proceed LIFO. That is, given y = func3(func2(func1(x))), then x = func1-1(func2-1func3-1(y))) 2.
That is:
SPIRAL =. func1^:_1 func2^:_1 func3^:_1 ones_and_fives
and we know:
- The inverse of an inverse is the thing itself, so func3^:_1 is merely +/\.
- The function /: is self-inverse, so func2^:_1 is merely /: (though /:^:_1 would work as well).
- The function , (ravel) is not invertible: it loses information (it is possible that (,x)=(,y) is true but x=y is not). But that's ok, we have the information that it lost: it's the original shape of SPIRAL, which is the input to our function! So we can undo the ravel.
conclusion
Putting that all together, we conclude:
SPIRAL =. (input) reshape /: +/\ ones_and_fives
In English:
- Joey discovered a very simple pattern underlying the spiral arrays. The spiral itself is merely the grade of the running-sum of this pattern, reshaped into a matrix.
Generating the underlying pattern (ones_and_fives) is left as an exercise for the reader. But, if you get stuck, it's spelled out in the original article.
notes
- For simplicity, here log means log-base-10, or log10.
- In fact, LIFO of inverses is exactly how J inverts composite functions.
DanBron 19:40, 5 August 2008 (UTC)
original J exposition
The J solution was:
spiral =. ,~ $ [: /: }.@(2 # >:@i.@-) +/\@# <:@+: $ (, -)@(1&,)
Here are some hints that will allow you to reimplement it in your language:
counts =: }.@(2 # >:@i.@-) counts 5 5 4 4 3 3 2 2 1 1 values =: <:@:+: $ (, -)@(1&,) values 5 1 5 _1 _5 1 5 _1 _5 1 copy =: # 3 copy 9 9 9 9 (counts copy values) 5 1 1 1 1 1 5 5 5 5 _1 _1 _1 _1 _5 _5 _5 1 1 1 5 5 _1 _1 _5 1 sumscan =: +/\ NB. Cumulative sum sumscan 0 1 2 3 4 0 1 3 6 10 (counts sumscan@copy values) 5 1 2 3 4 5 10 15 20 25 24 23 22 21 16 11 6 7 8 9 14 19 18 17 12 13 grade =: /: NB. Permutation which tells us how to sort grade 5 2 3 1 0 4 4 3 1 2 5 0 (counts grade@sumscan@copy values) 5 0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8 dup =: ,~ dup 5 5 5 reshape =: $ NB. Reshape an array 3 4 reshape 'hello' hell ohel lohe (dup reshape counts grade@sumscan@copy values) 5 0 1 2 3 4 15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8
For a fuller explanation, see the original source.
- Yet another J solution that looks both interesting and impenetrable to me. at least for Zig Zag a Haskel person had reimplemented the J solution and left me the clue that it involved a sort :-)
- --Paddy3118 16:56, 5 August 2008 (UTC)
- This one includes a sort, too :) That's one of the neatest parts! Alright, let me write out the algo real quick (I'll gloss over details and may fib a bit, to get the idea across quickly).