Creating A Spiral Array In Python?


Answer :

You can build a spiral by starting near the center of the matrix and always turning right unless the element has been visited already:



#!/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


Introductory remarks



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



There is a multitude of resources on how to produce a spiral matrix or how to loop or print an array in spiral order. Even so, I decided to write my own version, using numpy arrays. The idea is not original but use of numpy makes the code more concise.



The other reason is that most of examples of producing a spiral matrix I found (including the code in the question and in the other answers) deal only with square matrices of size n x n for odd n. Finding the start (or end) point in matrices of other sizes may be tricky. For example, for a 3x5 matrix it can't be the middle cell. The code below is general and the position of the starting (ending) point depends on the choice of the function spiral_xxx.



Code



The first function unwraps an array in spiral order clockwise:



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 on eight different ways depending on where we start and how we rotate the matrix. I'll give another one, which is consistent (it will be evident later) with the matrix transformation in the image in the question. So, further on, I will be using 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 type of matrices but we will need a helper 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 come the two main functions. One transforms a matrix to a spiral form of the same dimensions, the other reverts 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



Matrix 3 x 5:



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]]


Matrix from the question:



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]]


Remark



If you are going to work only with fixed size matrices, for example 5x5, then it's worth replacing base_spiral(*A.shape) in definitions of the functions with a fixed matrix of indices, say Ind (where Ind = base_spiral(5,5)).



Here's a solution using itertools and virtually no maths, just observations about what the spiral looks like. I think it's elegant and pretty 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


Usage:



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's the same solution shortened:



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've ignored the fact that you want the input to be a 2D array since it makes much more sense for it to be any 1D iterable. You can easily flatten the input 2D array if you want. I've also assumed the output should be a square since I can't think what you'd sensibly want otherwise. It may go over the edge and raise an error if the square has even length and the input is too long: again, I don't know what the alternative would be.



Comments

Post a Comment

Popular posts from this blog

Converting A String To Int In Groovy

Answer : Use the toInteger() method to convert a String to an Integer , e.g. int value = "99".toInteger() An alternative, which avoids using a deprecated method (see below) is int value = "66" as Integer If you need to check whether the String can be converted before performing the conversion, use String number = "66" if (number.isInteger()) { int value = number as Integer } Deprecation Update In recent versions of Groovy one of the toInteger() methods has been deprecated. The following is taken from org.codehaus.groovy.runtime.StringGroovyMethods in Groovy 2.4.4 /** * Parse a CharSequence into an Integer * * @param self a CharSequence * @return an Integer * @since 1.8.2 */ public static Integer toInteger(CharSequence self) { return Integer.valueOf(self.toString().trim()); } /** * @deprecated Use the CharSequence version * @see #toInteger(CharSequence) */ @Deprecated public static Integer toInteger(String self) { return toInteg
Read more

"Cannot Create Cache Directory /home//.composer/cache/repo/https---packagist.org/, Or Directory Is Not Writable. Proceeding Without Cache"

Answer : if anyone pass through here, this is shorter solution: sudo chown -R $USER $HOME/.composer it seems to me the group information is missing in your command sudo chown -R <user> /home/<user>/.composer/cache/repo/https---packagist.org Shoud be sudo chown -R <user>:<group> /home/<user>/.composer/cache/repo/https---packagist.org But to avoid other permission issues, I would rather advise: sudo chown -R <user>:<group> /home/<user>/.composer/cache (you'll need access to other folders in there) and sudo chown <user>:<group> /home/<user>/.composer To make sure your user has permissions enough on the global composer folder. Mind the missing recursion so the user don't own keys created by root. If you need to find out the group: groups <user>
Read more

Android How Can I Convert A String To A Editable

Answer : As you probably found out, Editable is an interface so you cannot call new Editable() . However an Editable is nothing more than a String with Spannables, so use SpannableStringBuilder: Editable editable = new SpannableStringBuilder("Pass a string here"); If you only want to change the Spannables, never the text itself, you can use a basic SpannableString. Use Editable.Factory.getInstance().newEditable(str) From the android documentation: Returns a new SpannedStringBuilder from the specified CharSequence. You can override this to provide a different kind of Spanned.
Read more