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], ['F',3] ]
Pulling out the second column from the matrix (the integers), you'd get this:
[4,5,1,2,0,3]
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).
Python array initialisation edit problem
Hi Spoon, your edit to Spiral of substituting <python>array = [[None]*n]*n</python> for <python>array = [[None]*n for j in range(n)]</python> [here] doesn't work because of: <lang python>>>> n=2 >>> a = [[None]*n]*n >>> a [[None, None], [None, None]] >>> a[0][0] = 1 >>> a [[1, None], [1, None]] >>></lang> You are referencing the inner list multiple times instead of creating new copies. --Paddy3118 06:17, 14 August 2008 (UTC)
- Oh yeah, sorry. You're right. --Spoon! 18:58, 14 August 2008 (UTC)
Lua spiralling error?
Task says:
"where the numbers increase sequentially as you go around the edges of the array spiralling inwards"
Lua says:
"returns the value at (x, y) in a spiral that starts at 1 and goes outwards"
I haven't run the program to see its output, but could someone check that the spiral is as in the task description? Thanks. --Paddy3118 08:24, 29 January 2010 (UTC)
- Lua output is
14 15 16 17 18 19 20 21 13 38 39 40 41 42 43 22 12 37 54 55 56 57 44 23 11 36 53 62 63 58 45 24 10 35 52 61 60 59 46 25 9 34 51 50 49 48 47 26 8 33 32 31 30 29 28 27 7 6 5 4 3 2 1 0
- which seems correct (even though starting from lower-rightmost corner). — ShinTakezou 10:35, 21 May 2010 (UTC)
Spiral Matrix implementation in VBA
hii i came across this page during a search for a mechanism to implement the spiral matrix in VBA bt unfortunately it was not listed here. But afrterwards by translating the java code i manage to obtain the result. I beleive a lot f peopla have manage to do this but didnt come across anyone who has shared it so here it goes....
- Howdy, and welcome to RC (if appropriate). Might I suggest creating an account?
- Having said that, code submissions really should go on the task's page, and not its talk page. I've moved it for you: Spiral matrix#VBA. I made some changes so that it is more generalized; your use of
Init(which I assume sets up certain starting conditions) doesn't help anyone without access to your code. - (As a minor aside, I have to wonder at your use of cells way down in the 400+ range. For something like this, I'd think that just starting at A1 would be acceptable.)
- Not trying to be a jerk, just trying to help. -- Erik Siers 18:28, 21 September 2010 (UTC)
Really long line in C#
It doesn't look like best coding practice to have that really long line. Wouldn't it be better with some newlines and spacing to better show its structure and cut the line length? --Paddy3118 (talk) 06:58, 30 September 2015 (UTC)