Codewars Kyu 4 Python 3


Snail

Describe -

Snail Sort
Given an n x n array, return the array elements arranged from outermost elements to the middle element, traveling clockwise.

array = [[1,2,3],
         [4,5,6],
         [7,8,9]]
snail(array) #=> [1,2,3,6,9,8,7,4,5]

For better understanding, please follow the numbers of the next array consecutively:

array = [[1,2,3],
         [8,9,4],
         [7,6,5]]
snail(array) #=> [1,2,3,4,5,6,7,8,9]

NOTE: The idea is not sort the elements from the lowest value to the highest; the idea is to traverse the 2-d array in a clockwise snailshell pattern.

NOTE 2: The 0x0 (empty matrix) is represented as en empty array inside an array [[]].

Answer -

import math
def snail(array):
    if array == [[]]:return []
    if len(array) == 1:return [array[0][0]]
    start = [(i,i)for i in range(math.ceil(len(array)/2))]
    count = 0
    times = 0
    trace = []
    while len(array)//2 - times > 0:
        for i,j in [(0,1),(1,0),(0,-1),(-1,0)]:
            if count % 4 == 0:
                a,b = start[count//4]
                trace += [array[a][b]]
            for _ in range(len(array)-1-2*times):
                a,b = a+i,b+j
                trace.append(array[a][b])
            count += 1
        times += 1
        trace.pop()
    if len(array)&1 == 1:
        a,b = start[len(array)//2]
        return trace+[array[a][b]]
    return trace

#

if判斷是否為空矩陣 , 空的返回 []
判斷長度是否為1多餘 , 刪掉

逆時針往內走,初始值都是0,0 走完第一圈後,起跑位置隨矩陣大小做變化
33和44矩陣是1,1
55和66矩陣還會多一次2,2 .....依此類推
先判斷矩陣大小算出之後的起始位置放入start list
使用math.ceil無條件進位,或可改寫成
start = [(i,i)for i in range((len(array)+1)//2)]

while len(array)//2 - times > 0
利用矩陣長度算出走的圈數,僅剩1步的不算
ex: 33 , 55 , 77 , 99..... 最後都會剩1格中間
for i,j in [(0,1),(1,0),(0,-1),(-1,0)]:
依序往右,下,左,上走

使用if判斷改變起跑位置, 走往一圈起始位置改變 , 可改至上方while迴圈內
,可少加if判斷 count//4 也拿掉改成times, 寫得太複雜了 , count 可全刪改

if count % 4 == 0:
    a,b = start[count//4]
    trace += [array[a][b]]

用矩陣長度算要走的步數,起始不算 -1 , 33 第一圈各走2步, 44 走3步 依此類推
,44第二圈走1步 , 55第二圈2步......

for _ in range(len(array)-1-2*times):
    a,b = a+i,b+j
    trace.append(array[a][b])

最後會多算一格 , 去掉
最後判斷長度除2是否餘1 , 是1要多加1格起始值
因為33 , 55 等奇數長度會少算到中間1格

改進後如下

def snail(array):
    if array == [[]]:return []
    start = [(i,i)for i in range((len(array)+1)//2)]
    times = 0
    trace = []
    while len(array)//2 - times > 0:
        a,b = start[times]
        trace += [array[a][b]]
        for i,j in [(0,1),(1,0),(0,-1),(-1,0)]:
            for _ in range(int(len(array))-1-2*times):
                a,b = a+i,b+j
                trace.append(array[a][b])
        times += 1
        trace.pop()
    if len(array)&1 == 1:
        a,b = start[len(array)//2]
        return trace+[array[a][b]]
    return trace
其他答案多為旋轉矩陣處理

1.

#my implementation/explanation of the solution by foxxyz
def snail(array):
  if array:
#force to list because zip returns a list of tuples
    top_row = list(array[0])

#rotate the array by switching remaining rows & columns with zip
#the * expands the remaining rows so they can be matched by column
    rotated_array = zip(*array[1:])

#then reverse rows to make the formerly last column the next top row

rotated_array = rotated_array[::-1]
    return top_row + snail(rotated_array)
  else:
    return []

2.

def snail(array: list) -> list:
    return arrays[0] + snail(list(map(list, zip(*arrays[1:])))[::-1]) if arrays else []

3.

def snail(array):
    out = []
    while len(array):
        out += array.pop(0)
        array = list(zip(*array))[::-1] # Rotate
    return out

4.

import numpy as np
def snail(array):
    m = []
    array = np.array(array)
    while len(array) > 0:
        m += array[0].tolist()
        array = np.rot90(array[1:])
    return m

5.

def snail(array):
    next_dir = {"right": "down", "down":"left", "left":"up", "up":"right"}
    dir = "right"
    snail = []
    while array:
        if dir == "right":
            snail.extend(array.pop(0))
        elif dir == "down":
            snail.extend([x.pop(-1) for x in array])
        elif dir == "left":
            snail.extend(list(reversed(array.pop(-1))))
        elif dir == "up":
            snail.extend([x.pop(0) for x in reversed(array)])    
        dir = next_dir[dir]
    return snail
##Codewars






你可能感興趣的文章

ASP.NET Core Web API 入門教學 - 使用AutoMapper自動對應Dto欄位

ASP.NET Core Web API 入門教學 - 使用AutoMapper自動對應Dto欄位

圖論(Graph Theory)

圖論(Graph Theory)

 Day 37 - requests & Habit Tracker

Day 37 - requests & Habit Tracker






留言討論