Creating a circular matrix with one input

[omnisierra]

Hi everyone, I have a homework and couldn't solve the following question:

Out an n×n table filled with numbers from 1 to n^2 in a spiral starting from the upper left corner and twisted clockwise, as shown in the example (here n=5):

Sample Input:
5
Sample Output:
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

I am a beginner in Python and I can even barely work with the lists. I have found some similar solutions on the internet but I was not sure what I am looking at since I don't know the advanced methods yet. I know only loops, lists, strings etc. Could anyone help me to solve the question without advanced methods which wouldn't be very complicated for me?

[Gribouillis]

You could create a list of lists filled with zeroes, of size n x n. Then you could start at a position i, j = 0, 0 and for each number in 1,...,n**2, you would store this number at the current position, then move to the next position.

[deanhystad]

This is a pencil and paper exercise and has almost nothing to do with Python lists other than knowing how to make and index a 2D list.

With pencil and paper draw an empty 2D list. The list below is for n=4

__ __ __ __
__ __ __ __
__ __ __ __
__ __ __ __

Start from the upper left corner begin filling out the list and write down the Python code to do the equivalent.

_1 _2 _3 _4     s[0][0] = 1, s[0][1] = 2, s[0][2] = 3, s[0][3] = 4
__ __ __ __
__ __ __ __
__ __ __ __

Can this be generalized to some equation or rule?

Continue filling down along the right side of the square.

_1 _2 _3 _4     s[0][0] = 1, s[0][1] = 2, s[0][2] = 3, s[0][3] = 4
__ __ __ _5     s[1][3] = 5, s[2][3] = 6, s[3][3] = 7
__ __ __ _6
__ __ __ _7

Is there a pattern or rule for why we are filling downward? What caused the change from filling to the right to filling down?

Fill across the bottom.

_1 _2 _3 _4     s[0][0] = 1, s[0][1] = 2, s[0][2] = 3, s[0][3] = 4
__ __ __ _5     s[1][3] = 5, s[2][3] = 6, s[3][3] = 7
__ __ __ _6     s[3][2] = 8, s[3][1] = 9, s[3][0] = 10
10 _9 _8 _7

Any pattern or rule here? How long do we fill to the left? Why did we stop filling down?

How about fill in the rest of the square.

_1 _2 _3 _4     s[0][0] = 1,  s[0][1] = 2,  s[0][2] = 3, s[0][3] = 4
12 13 14 _5     s[1][3] = 5,  s[2][3] = 6,  s[3][3] = 7
11 16 15 _6     s[3][2] = 8,  s[3][1] = 9,  s[3][0] = 10
10 _9 _8 _7     s[2][0] = 11, s[1][0] = 12
                s[1][1] = 13, s[1][2] = 14
                s[2][2] = 15
                s[2][1] = 16

Repeat the exercise for a 5x5 square. Look for patterns or rules. Maybe there will be a pattern for even sized squares and a different pattern for odd sized squares. Maybe a size 4 square is a "skin" wrapped around a size 2 square. Maybe there is a simple set of rules that describe how to fill the next cell.

Once you have the rules figured out for making any sized square, you will convert your rules into Python. This is the easy part of this assignment.

[DeaD_EyE]

Do you know the game Snake?
I have no working code, but the idea to create the number spiral with the same logic.

Your snake has a position (y,x) and a direction. Depending on the direction 1 is added/subtracted to y-index or x-index.
The snake starts in the left corner (0,0) and goes to right direction (x + 1) till the boundary. Then the direction is down.

Maybe I come later back with some example code or someone else gives more hints.
It's not so easy to it right.

[deanhystad]

I like the snake reference.

>>>>>
    v
    v
    v
<<<<v

Start in the upper left corner and fill to the right until you can go no further. When you can go no further make a 90 degree left turn and fill until you can go no further.

That makes a really simple rule:
Go straight if you can, else turn left.

Of course the "if you can" and "turn left" are a bit more complicated.

[perfringo]

Interesting little problem . I think that implementing technique suggested by deanhystad can quite easily deliver expected results.

Just additional suggestion: you can try to solve this only for outer line/circle and if you got it then it should be relatively easy to apply the same logic to inner lines/circles as well. Just another hint for finding solution (indices of outer line values of 5 x 5 matrix):

[0, 0], [0, 1], [0, 2], [0, 3], [0, 4]
[1, 0]                          [1, 4]
[2, 0]                          [2, 4]
[3, 0]                          [3, 4]
[4, 0], [4, 1], [4, 2], [4, 3], [4, 4]

If you use 2D list (matrix) for solution then you should built one with dummy values before you assign values using indices. Otherwise you will get index error.

[Gribouillis]

There is a recursive implementation

# snail.py

LEFT, DOWN, RIGHT, UP = range(4)

def snail(start, n, m, dir):
    nd = (dir + 1) % 4 # next dir
    if not n:
        return []
    elif not m:
        return [list() for i in range(n)]
    if dir == LEFT:
        s = snail(start + m, n-1, m, nd)
        s.insert(0, list(range(start, start + m)))
    elif dir == DOWN:
        s = snail(start + n, n, m-1, nd)
        for i, row in enumerate(s):
            row.append(start+i)
    elif dir == RIGHT:
        s = snail(start + m, n-1, m, nd)
        s.append(list(range(start + m - 1, start - 1, -1)))
    elif dir == UP:
        s = snail(start + n, n, m-1, nd)
        for i, row in enumerate(s):
            row.insert(0, start + n - 1 - i)
    return s

if __name__ == '__main__':
    for row in snail(1, 5, 5, LEFT):
        print(row)

Output:
[1, 2, 3, 4, 5]
[16, 17, 18, 19, 6]
[15, 24, 25, 20, 7]
[14, 23, 22, 21, 8]
[13, 12, 11, 10, 9]

I also have another MUCH shorter recursive implementation.

[deanhystad]

Homework section?

[Gribouillis]

@deanhystad
I don't think the OP can use recursion as it is a beginner's homework.

[DPaul]

After Gribouillis' awesome solution that works for odd and uneven numbers,
i tried to make something that the TS might be able to do, without recursion.
For the time being it works only for 3 and 5, perhaps with some work it will do all odd numbers.

As this is homework, no code, but the idea is:
- Start from the middle, and work you way around that, like a spider. (first 25, then 24, etc)
-Each square around the middle has 4 sides, getting longer for each leayer.

These useless exercises are sometimes great fun and instructive.
Paul

Output:
[1, 2, 3]
[8, 9, 4]
[7, 6, 5]

[1, 2, 3, 4, 5]
[16, 17, 18, 19, 6]
[15, 24, 25, 20, 7]
[14, 23, 22, 21, 8]
[13, 12, 11, 10, 9]

Paul