# 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.

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:

1. The inverse of an inverse is the thing itself, so func3^:_1 is merely +/\.
2. The function /: is self-inverse, so func2^:_1 is merely /: (though /:^:_1 would work as well).
3. 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

1. For simplicity, here log means log-base-10, or log10.
2. 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 =. ,~ \$ [: /: }[email protected](2 # >:@[email protected]) +/\@# <:@+: \$ (, -)@(1&,)
```

Here are some hints that will allow you to reimplement it in your language:

```   counts   =:  }[email protected](2 # >:@[email protected])
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 [email protected] 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 [email protected]@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 [email protected]@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:

`>>> n=2>>> a = [[None]*n]*n>>> a[[None, None], [None, None]]>>> a[0][0] = 1>>> a[[1, None], [1, None]]>>>`

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?

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

I wrapped it. Hopefully that makes it ok... --Rdm (talk) 12:28, 30 September 2015 (UTC)
It's a lot better, thanks. --Paddy3118 (talk) 12:46, 30 September 2015 (UTC)