[PYTHON] How to get a quadratic array of squares in a spiral!

1.First of all

Nice to meet everyone! I'm Monabo, who is majoring in software engineering at university.

Before reading, we want our readers to read ideas rather than code.

Suddenly, have you ever been confused by the flow of arrays? I understand that much! You may be confused, but please read a little more.

So, do you know how to move an array of squares in a spiral with a pointer?

I will explain in detail.

Main subject

Now, let's get down to the main topic.

Suppose you have a quadratic array of squares. Example.)

array_traversal.py



array = [
    [1, 2, 3, 4]
    [12, 13, 14, 5]
    [11, 16, 15, 6]
    [10, 9, 8, 7]
]

Get the primary array by crossing each element in a spiral of this vertical x horizontal quadratic array. (Time complexity is O (n))

Output example


[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

Way of thinking

First of all, from the way of thinking.

1. Let's change the viewpoint a little

First image: Screen Shot 2021-01-20 at 17.56.17.png

It may be easier to understand if you look at 1st image. Although it is acquired in a spiral shape, if you try to tackle the problem from a slightly different perspective there It can be divided into an outer square and an inner square.

Looking at it that way, the complexity has disappeared a little. Right?

Next, to bypass this square, think of it as having two pointers (for rows and columns) . Think of the pointer here as simply telling the computer "Do this process here!" To direct the process.

There is one point to consider in order to get these two pointers in a spiral. It is control of double counting .


Supplement: Here, row refers to rows and columns refer to columns. To put it simply, double counting is the same factor in processing.


2. Control of double counting

Please see the following image.

Second: Screen Shot 2021-01-20 at 18.18.11.png

By doing this, you can create boundaries between each other and prevent double counting , so I think it will be an efficient solution.



3. A series of processing flow (outside)

Now, let's explain the flow when we are finally ready.

3.1 Get the top row ([1, 2, 3, 4]) with the pointer for the column

![Screen Shot 2021-01-20 at 20.30.51.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/920249/46b91a04-8673-b212-a847-1231841533bc.png)

You can do this with the usual for loop method.

Sample code:

python


   for col in range(sc, ec + 1):
       result.append(array[sr][col])

3.2 Get the column pointed to by EC with the pointer for row to ER. (Here, [5, 6, 7].)

Screen Shot 2021-01-20 at 20.35.16.png

Sample code:

python


   for row in range(sr + 1, er + 1):
       result.append(array[row][ec])

3.3 Get the bottom row ([10, 9, 8]) in the opposite direction with the pointer for the column.

Here we implement a reverse for loop using a built-in function called reverse. ![Screen Shot 2021-01-20 at 20.37.16.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/920249/9a91c637-4ab1-0fda-f29f-2419633b0c1c.png)

Sample code:

python


   for col in reversed(range(sc, ec)):
       result.append(array[er][col])

3.4 Finally, I want to get [12] on the 2nd line and [11] on the 3rd line, so I get them with the pointer for row in the opposite direction in the SR + 1 ~ ER section.

Again, use reverse. ![Screen Shot 2021-01-20 at 20.39.20.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/920249/4b2b81a7-44b6-b66f-f7a5-6ea81d4688a4.png)

Sample code:

python


   for row in reversed(range(sr + 1, er)):
       result.append(array[row][sr])

With this, I finally got all the elements of the outer square in a spiral shape.


4. A series of processing flow (inside)

Next is the inner square. Screen Shot 2021-01-20 at 17.56.17.png However, if you continue to process in the same way, it will become hard coding, right?

So, add one SR and SC and move them inward. Also, by adding one EC and one ER and moving them inward, you can reuse the ones made in 1-5! It's ECO ~ lol

python


#Processing of inner squares
sr += 1 
er -= 1
sc += 1
ec -= 1		

From the following, the explanation with images and codes will be omitted.

  1. Get the top row ([13, ​​14]) with the pointer for the column This can also be done with the usual for loop method.

  2. Get the column pointed to by EC with the pointer for row to ER. (Here, [15].)

  3. Get the bottom row ([16]) in the opposite direction with the pointer for the column. Here we implement a reverse for loop using a built-in function called reverse.

  4. Finally, since SR is equal to ER, range becomes 0 and nothing can be acquired.

Completion code

array_traversal.py




def spiralTraverse(array):
	result = []
	sr, er = 0, len(array) - 1
	sc, ec = 0, len(array[0]) - 1
	
	while sr <= er and sc <= ec:
		for col in range(sc, ec + 1):
			result.append(array[sr][col])
			
		for row in range(sr + 1, er + 1):
			result.append(array[row][ec])
			
		for col in reversed(range(sc, ec)):
			result.append(array[er][col])
			
		for row in reversed(range(sr + 1, er)):
			result.append(array[row][sr])
			
		sr += 1 
		er -= 1
		sc += 1
		ec -= 1
		
	return result 
	

At the end

It's just one way of thinking, so there are many other ways to answer. For example, processing using the recursive method. Please note that the edge case is not considered here, so please handle it according to the problem.

It's been long, but that's it! Thank you for your hard work!

LGTM Thank you!

Recommended Posts

How to get a quadratic array of squares in a spiral!
How to get a list of built-in exceptions in python
How to get a stacktrace in python
How to get the vertex coordinates of a feature in ArcPy
How to get the number of digits in Python
How to get a list of files in the same directory with python
How to get rid of server custom emoji in message.content
How to slice a block multiple array from a multiple array in Python
I tried "How to get a method decorated in Python"
How to develop in a virtual environment of Python [Memo]
How to get the last (last) value in a list in Python
How to get an overview of your data in Pandas
How to display a specified column of files in Linux (awk)
Try to get a list of breaking news threads in Python.
How to get all the possible values in a regular expression
How to make a string into an array or an array into a string in Python
How to check the memory size of a variable in Python
How to get a string from a command line argument in python
Here's a brief summary of how to get started with Django
How to check the memory size of a dictionary in Python
Create a function to get the contents of the database in Go
How to get rid of long comprehensions
How to get rid of the "Tags must be an array of hashes." Error in the qiita api
How to get a specific column name and index name in pandas DataFrame
How to send a visualization image of data created in Python to Typetalk
[Linux] Command to get a list of commands executed in the past
How to get a value from a parameter store in lambda (using python)
How to get a namespaced view name from a URL (path_info) in Django
How to format a list of dictionaries (or instances) well in Python
How to sort by specifying a column in the Python Numpy array.
How to calculate the volatility of a brand
Draw a graph of a quadratic function in Python
A simple example of how to use ArgumentParser
How to clear tuples in a list (Python)
How to keep track of work in Powershell
How to embed a variable in a python string
Summary of how to import files in Python 3
Get the caller of a function in Python
How to get results from id in Celery
How to create a JSON file in Python
How to implement a gradient picker in Houdini
How to notify a Discord channel in Python
How to get dictionary type elements of Python 2.7
How to get the files in the [Python] folder
Output in the form of a python array
Get a glimpse of machine learning in Python
[Python] How to draw a histogram in Matplotlib
How to create a Rest Api in Django
How to write a named tuple document in 2020
How to count numbers in a specific range
How to read a file in a different directory
How to Mock a Public function in Pytest
How to pass the execution result of a shell command in a list in Python
How to mention a user group in slack notification, how to check the id of the user group
How to achieve something like a list of void * (or variant) in Go?
Set the number of elements in a NumPy one-dimensional array to a power of 2 (0 padded)
[NNabla] How to get the output (variable) of the middle layer of a pre-built network
[python] How to sort by the Nth Mth element of a multidimensional array
A memorandum of how to execute the! Sudo magic command in Jupyter Notebook
How to use loc / iloc / ix to get by specifying a column in CASTable
[Introduction to Python] How to get the index of data with a for statement