Creating a spiral array in python?

Question

My assistant and I tried to create a fun python game where elements inserted into an array are accessed in a spiral. I tried several methods as shown below ( source ).

def spiral(X, Y): x = y = 0 dx = 0 dy = -1 for i in range(max(X, Y)**2): if (-X/2 < x <= X/2) and (-Y/2 < y <= Y/2): print (x, y) # DO STUFF... if x == y or (x < 0 and x == -y) or (x > 0 and x == 1-y): dx, dy = -dy, dx x, y = x+dx, y+dy 

The above statement accesses elements in a spiral loop and prints them for a specific AE array. I would like to know how I can convert a given AE array to spiral

Answer 1

You can build a spiral, starting from the center of the matrix and always turning right if the element has not already been visited:

 #!/usr/bin/env python NORTH, S, W, E = (0, -1), (0, 1), (-1, 0), (1, 0) # directions turn_right = {NORTH: E, E: S, S: W, W: NORTH} # old -> new direction def spiral(width, height): if width < 1 or height < 1: raise ValueError x, y = width // 2, height // 2 # start near the center dx, dy = NORTH # initial direction matrix = [[None] * width for _ in range(height)] count = 0 while True: count += 1 matrix[y][x] = count # visit # try to turn right new_dx, new_dy = turn_right[dx,dy] new_x, new_y = x + new_dx, y + new_dy if (0 <= new_x < width and 0 <= new_y < height and matrix[new_y][new_x] is None): # can turn right x, y = new_x, new_y dx, dy = new_dx, new_dy else: # try to move straight x, y = x + dx, y + dy if not (0 <= x < width and 0 <= y < height): return matrix # nowhere to go def print_matrix(matrix): width = len(str(max(el for row in matrix for el in row if el is not None))) fmt = "{:0%dd}" % width for row in matrix: print(" ".join("_"*width if el is None else fmt.format(el) for el in row)) 

Example:

 >>> print_matrix(spiral(5, 5)) 21 22 23 24 25 20 07 08 09 10 19 06 01 02 11 18 05 04 03 12 17 16 15 14 13 

Answer 2

Introductory remarks

The issue is closely related to the problem of printing an array in a spiral manner. In fact, if we already have a function that does this, then the problem in question is relatively simple.

There are many resources on how to create a spiral matrix or how to loop or print an array in a spiral order. However, I decided to write my own version using numpy arrays. The idea is not original, but using numpy makes the code more concise.

Another reason is that most of the spiral matrix creation examples that I found (including the code in the question and other answers) deal only with nxn square matrices for odd n. Finding the start (or end) point in matrices of other sizes can be difficult. For example, for a 3x5 matrix, it cannot be a middle cell. The code below is general, and the position of the start (end) point depends on the choice of spiral_xxx function.

the code

The first function spins the array in a clockwise direction:

 import numpy as np def spiral_cw(A): A = np.array(A) out = [] while(A.size): out.append(A[0]) # take first row A = A[1:].T[::-1] # cut off first row and rotate counterclockwise return np.concatenate(out) 

We can write this function in eight different ways, depending on where we start and how we rotate the matrix. I will give another one that will be consistent (this will be obvious later) with matrix transformation in the image in question. So, in the future, I will use this version:

 def spiral_ccw(A): A = np.array(A) out = [] while(A.size): out.append(A[0][::-1]) # first row reversed A = A[1:][::-1].T # cut off first row and rotate clockwise return np.concatenate(out) 

How it works:

 A = np.arange(15).reshape(3,5) print(A) [[ 0 1 2 3 4] [ 5 6 7 8 9] [10 11 12 13 14]] print(spiral_ccw(A)) [ 4 3 2 1 0 5 10 11 12 13 14 9 8 7 6] 

Note that the end (or start) point is not the middle cell. This function works for all types of matrices, but we need an auxiliary function that generates spiral indices:

 def base_spiral(nrow, ncol): return spiral_ccw(np.arange(nrow*ncol).reshape(nrow,ncol))[::-1] 

For example:

 print(base_spiral(3,5)) [ 6 7 8 9 14 13 12 11 10 5 0 1 2 3 4] 

Now let's move on to the two main functions . One transforms the matrix into a spiral shape of the same size, and the other returns the transformation:

 def to_spiral(A): A = np.array(A) B = np.empty_like(A) B.flat[base_spiral(*A.shape)] = A.flat return B def from_spiral(A): A = np.array(A) return A.flat[base_spiral(*A.shape)].reshape(A.shape) 

Examples

3 x 5 Matrix:

 A = np.arange(15).reshape(3,5) print(A) [[ 0 1 2 3 4] [ 5 6 7 8 9] [10 11 12 13 14]] print(to_spiral(A)) [[10 11 12 13 14] [ 9 0 1 2 3] [ 8 7 6 5 4]] print(from_spiral(to_spiral(A))) [[ 0 1 2 3 4] [ 5 6 7 8 9] [10 11 12 13 14]] 

Question Matrix:

 B = np.arange(1,26).reshape(5,5) print(B) [[ 1 2 3 4 5] [ 6 7 8 9 10] [11 12 13 14 15] [16 17 18 19 20] [21 22 23 24 25]] print(to_spiral(B)) [[21 22 23 24 25] [20 7 8 9 10] [19 6 1 2 11] [18 5 4 3 12] [17 16 15 14 13]] print(from_spiral(to_spiral(B))) [[ 1 2 3 4 5] [ 6 7 8 9 10] [11 12 13 14 15] [16 17 18 19 20] [21 22 23 24 25]] 

Note

If you are going to work only with fixed-size matrices, for example 5x5, then it is worth replacing base_spiral(*A.shape) with function definitions with a fixed matrix of indices, for example Ind (where Ind = base_spiral(5,5) ).

Answer 3

Below is the python3 code that converts:

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

to

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

You can easily change the implementation in the way you want ...

  def spiral(X, Y): x = y = 0 dx = 0 dy = -1 for i in range(max(X, Y) ** 2): if (-X / 2 < x <= X / 2) and (-Y / 2 < y <= Y / 2): yield x, y # print(x, y) # DO STUFF... if x == y or (x < 0 and x == -y) or (x > 0 and x == 1 - y): dx, dy = -dy, dx x, y = x + dx, y + dy spiral_matrix_size = 5 my_list = list(range(spiral_matrix_size**2)) my_list = [my_list[x:x + spiral_matrix_size] for x in range(0, len(my_list), spiral_matrix_size)] print(my_list) for i, (x, y) in enumerate(spiral(spiral_matrix_size, spiral_matrix_size)): diff = int(spiral_matrix_size / 2) my_list[x + diff][y + diff] = i print(my_list) 

Answer 4

Here's a solution using itertools and with little or no math, just observing what the spiral looks like. I think it is elegant and quite easy to understand.

 from math import ceil, sqrt from itertools import cycle, count, izip def spiral_distances(): """ Yields 1, 1, 2, 2, 3, 3, ... """ for distance in count(1): for _ in (0, 1): yield distance def clockwise_directions(): """ Yields right, down, left, up, right, down, left, up, right, ... """ left = (-1, 0) right = (1, 0) up = (0, -1) down = (0, 1) return cycle((right, down, left, up)) def spiral_movements(): """ Yields each individual movement to make a spiral: right, down, left, left, up, up, right, right, right, down, down, down, ... """ for distance, direction in izip(spiral_distances(), clockwise_directions()): for _ in range(distance): yield direction def square(width): """ Returns a width x width 2D list filled with Nones """ return [[None] * width for _ in range(width)] def spiral(inp): width = int(ceil(sqrt(len(inp)))) result = square(width) x = width // 2 y = width // 2 for value, movement in izip(inp, spiral_movements()): result[y][x] = value dx, dy = movement x += dx y += dy return result 

Using:

 from pprint import pprint pprint(spiral(range(1, 26))) 

Output:

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

Here the same solution is abridged:

 def stretch(items, counts): for item, count in izip(items, counts): for _ in range(count): yield item def spiral(inp): width = int(ceil(sqrt(len(inp)))) result = [[None] * width for _ in range(width)] x = width // 2 y = width // 2 for value, (dx, dy) in izip(inp, stretch(cycle([(1, 0), (0, 1), (-1, 0), (0, -1)]), stretch(count(1), repeat(2)))): result[y][x] = value x += dx y += dy return result 

I ignored the fact that you want the input to be a 2D array, since it makes more sense to use any 1D fighter for it. You can easily smooth the input 2D array if you want. I also suggested that the exit should be a square, since I cannot think about what you would be wise to want otherwise. It can move around the edge and raise an error if the square has an even length and the input is too long: again, I don’t know which alternative will be.

Answer 5

You can fill the array with the following type:

 #!/usr/bin/python class filler: def __init__(self, srcarray): self.size = len(srcarray) self.array = [[None for y in range(self.size)] for y in range(self.size)] self.xpos, self.ypos = 0, 0 self.directions = [self.down, self.right, self.up, self.left] self.direction = 0 self.fill(srcarray) def fill(self, srcarray): for row in reversed(srcarray): for elem in reversed(row): self.array[self.xpos][self.ypos] = elem self.go_to_next() def check_next_pos(self): np = self.get_next_pos() if np[1] in range(self.size) and np[0] in range(self.size): return self.array[np[0]][np[1]] == None return False def go_to_next(self): i = 0 while not self.check_next_pos() and i < 4: self.direction = (self.direction + 1) % 4 i += 4 self.xpos, self.ypos = self.get_next_pos() def get_next_pos(self): return self.directions[self.direction](self.xpos, self.ypos) def down(self, x, y): return x + 1, y def right(self, x, y): return x, y + 1 def up(self, x, y): return x - 1, y def left(self, x, y): return x, y - 1 def print_grid(self): for row in self.array: print(row) f = filler([[x+y*5 for x in range(5)] for y in range(5)]) f.print_grid() 

The result of this will be:

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

Answer 6

 def counter(n): for i in range(1,n*n): yield i+1 n = 11 a = [[1 for x in range(n)] for y in range(n)] x = y = n//2 val = counter(n) for i in range(2, n, 2): y += 1 x -= 1 for k in range(i): x += 1 a[x][y] = next(val) for k in range(i): y -= 1 a[x][y] = next(val) for k in range(i): x -= 1 a[x][y] = next(val) for k in range(i): y += 1 a[x][y] = next(val) for i in range(n): for j in range(n): print (a[i][j] , end="") print (" " , end="") print("\n")