Алгоритм Улитки - управление максимальной / минимальной позицией для обхода

Question

Я работаю над проблемой в CodeWars для развлечения, и у меня возникают проблемы с парой вещей:

1. Понимание того, где мне нужно изменить код для того, чтобыправильно управляйте «точкой поворота» m и n, чтобы они начинали уменьшаться, а не увеличиваться.

2. Рефакторинг этого кода соответствующим образом.

Целью алгоритма является обход 2D-списка, подобного «улитке», например,

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

должен возвращать

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

для любого списка размером n * n

У меня нет сильного опыта в математике или CS, но я действительно люблю оба и пытаюсь понять эти проблемы с глубиной.

Я знаю, например, что если n представляет строки, а m представляет столбцы 2D-списка, мне нужно увеличить минимум n на 1 для каждой "цепи"Улитка, и уменьшите максимум m для каждого контура, но у меня возникают проблемы с пониманием, где это должно произойти.

Я кратко рассмотрел некоторые рекурсивные решения, но прежде чем я начал углубляться в них, янадеялся, что кто-нибудь сможет взглянуть на это и помочь мне понять, где мое мышление полностью неправильно .

def snail(array):

    new_snail = []
    n,m = 0,0
    j = 1



    while j <= len(array):
        print(n,m)
        if n == 0 and m == 0:

            while m < len(array)-j:
                new_snail.append(array[n][m])
                m += 1

            while n < len(array)-j:
                new_snail.append(array[n][m])
                n += 1

        else:

            while m > 0:
                new_snail.append(array[n][m])
                m -= 1

            while n > 0:
                new_snail.append(array[n][m])
                n -= 1
            m += 1
            n += 1
        j+=1
    return new_snail

Результат этого алгоритма в списке 3x3 2D в настоящее время [1, 2, 3, 6, 9, 8, 7, 4, 5, 4]Это означает, что я двигаюсь назад после достижения конца.

В большом 2-мерном списке 4x4

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

вывод равен [1, 2, 3, 4, 7, 11, 15, 14, 13, 12, 8, 4, 5, 4, 5, 4], поэтому я возвращаюсь назад и вперед по1-й ряд.

Спасибо, что заглянули, и я надеюсь, что это соответствует рекомендациям для SO вопроса.Меня меньше заботит получение баллов за упражнение / правильное понимание, а также понимание того, почему мой код неправильный / плохая практика.

Обновление

Я понимаюЯ считаю, что проблема лучше, и я добился определенного прогресса, но то, что убивает меня, все еще остается в списке.Я чувствую, что я действительно слаб в этом.В конечном итоге я зашёл слишком далеко в одном направлении, и все мои решения для этого действительно сложны.

def snail(array):
    new_snail = []
    visited = "*"
    i,j = 0,0

    current_dir = "right"

    def change_dir(direction):
        if direction == "right":
            return "down"
        elif direction == "down":
            return "left"
        elif direction == "left":
            return "up"
        elif direction == "up":
            return "right"

    def move(ipos,jpos,direction):
        i,j = ipos,jpos
        if i == -1:
            i += 1
        elif i == len(array):
            i -= 1
        elif j == -1:
            j +=1
        elif j == len(array):
            j -= 1

        if direction == "right":
            return i, j+1
        elif direction == "down":
            return i+1, j
        elif direction == "left":
            return i, j-1
        elif direction == "up":
            return i-1, j    


    new_snail.append(array[0][0])
    array[0][0] = "*"

    while len(new_snail) < len(array)**2:
        i,j = move(i,j,current_dir)

        if 0 <= i <= len(array)-1 and 0 <= j <= len(array)-1:
            if array[i][j] != visited:
                new_snail.append(array[i][j])
                array[i][j] = "*"
            else:
                current_dir = change_dir(current_dir)                
        else:
            current_dir = change_dir(current_dir)

    return new_snail

Answer 1

Отвечая на ваш вопрос о "что не так":

        else:

            while m > 0:
                new_snail.append(array[n][m])
                m -= 1

            while n > 0:
                new_snail.append(array[n][m])
                n -= 1
            m += 1
            n += 1
        j+=1

В этой части вы говорите интерпретатору "M is 1" (на самом деле, m = 0 +1, но это тот же результат) И тогда вы говорите: «Если M не == 0 (в другом случае), m = m -1"

Итак, на первой итерации после j + = 1 m равно 1 и переходит ко второму случаю, возвращая его назад.

Вместо этого вы могли бы переписать это «m> 0» как «m> j», поскольку вы увеличиваете J на ​​1 в каждом цикле.

Edit: Первая часть вашего условия также должна быть переписана как «m == j and n == j» вместо 0. В противном случае, она ВСЕГДА перейдет во второй случай после первой итерации.

Answer 2

Вот один из возможных способов сделать это, учитывая, что вы говорили о рефакторинге кода. Итак, есть несколько моментов, которые могут помочь вам увидеть эту проблему в другом свете.
Сначала мы устанавливаем несколько вещей: направления и следующее направление для улитки. Поскольку направления идут в цикле (вправо, вниз, влево, вверх, вправо, вниз ...), мы можем представить это с помощью функции next_direction. Кроме того, создание функции, которая просто «обновляет» позицию, может облегчить чтение кода.

RIGHT = 0
DOWN = 1
LEFT = 2
UP = 3
NB_DIRECTIONS = 4


def next_direction(direction):
    return (direction + 1) % NB_DIRECTIONS


def update_position(position, direction):
    x, y = position
    if direction == RIGHT:
        return x + 1, y
    elif direction == DOWN:
        return x, y + 1
    elif direction == LEFT:
        return x - 1, y
    elif direction == UP:
        return x, y - 1

Затем функции для получения значения из массива и установки значения в массиве как «посещенного».

def get_value(array, position):
    x, y = position
    return array[y][x]


def set_as_visited(array, position):
    x, y = position
    array[y][x] = '*'


def is_visited(array, position):
    return get_value(array, position) == '*'

И «главная» функция. Я использовал вашу идею в комментарии, чтобы заменить на '*' места, которые посетили в массиве. Поскольку мы делаем это, вместо проверки границ, мы можем окружить всю матрицу '*'.

def snail_arr(array):
    # compute the array size
    array_size = len(array) * len(array[0])

    # surround the array of '*'
    array = [['*' for _ in range(len(array[0]) + 2)]] + [
        ['*'] + array[i] + ['*']
        for i in range(len(array))
    ] + [['*' for _ in range(len(array[0]) + 2)]]

    # initialize position and direction
    position = 1, 1
    direction = RIGHT

    result = [get_value(array, position)]
    set_as_visited(array, position)
    nb_visited = 1

    while nb_visited < array_size:
        new_position = update_position(position, direction)
        if not is_visited(array, new_position):
            result += [get_value(array, new_position)]
            set_as_visited(array, new_position)
            position = new_position
            nb_visited += 1
        else:
            direction = next_direction(direction)
    return result

Вы можете проверить это:

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

Edit:
Чтобы сделать это с помощью границ массива, вы можете добавить новую функцию для проверки:

def is_in_bounds(array, position):  # valid only for square array
    x, y = position
    array_size = len(array)
    return (0 <= x < array_size) and (0 <= y < array_size)

Тогда условие if not is_visited(array, new_position): можно заменить на if is_in_bounds(array, new_position) в коде.

Answer 3

Я приведу только идею, и код должен быть написан вами самостоятельно.

Есть четыре направления, по которым улитка направляется по порядку вправо (j + = 1), вниз (i + = 1)), влево (j - = 1), вверх (i - = 1).

Улитка пойдет по этим четырем направлениям по кругу (вправо, вниз, влево, вверх, вправо, вниз, влево ...), поверните в следующем направлении до границы или числа посещенных мест.И заканчивается, когда улитка не может пройти к какой-либо сетке.

Определение can not walk to any grid: не может перейти в следующую сетку в направлении и в следующем направлении.

Пример кода с комментарием

directions = [
    lambda i, j: (i, j + 1),
    lambda i, j: (i + 1, j),
    lambda i, j: (i, j - 1),
    lambda i, j: (i - 1, j),
]

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

def in_matrix(i, j):
    return 0 <= i < len(array) and 0 <= j < len(array)

def is_visited(i, j):
    return array[i][j] == 0


def snail(array):
    direction_cnt = 0
    i, j = 0, 0
    ret = []
    ret.append(array[i][j])
    array[i][j] = 0  # mark as visited
    while True:
        direction_func = directions[direction_cnt % 4]  # turning directions in circle
        tmp_i, tmp_j = direction_func(i, j)  # attempt to head one step
        if (not in_matrix(tmp_i, tmp_j)) or is_visited(tmp_i, tmp_j):  # over border or visted
            direction_cnt += 1  # change direction
        else:
            i, j = tmp_i, tmp_j  # confirm this step
            ret.append(array[i][j])
            array[i][j] = 0  # mark as visited
            if len(ret) == len(array)**2:  # simple terminal criteria
                return ret


if __name__ == '__main__':
    print snail(array)