蜗牛算法——控制遍历的最大/最小位置

5

我正在为了娱乐而解决CodeWars中的一个问题,但遇到了一些困难:

  1. 不理解在哪里需要修改代码,以便正确控制m和n的“转折点”,使其开始下降而不是上升。

  2. 适当地重构这个代码。

该算法的目的是像“蜗牛”一样遍历一个二维列表,例如:

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

应该返回

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

对于任何大小为n*n的列表

虽然我并不是数学或计算机科学背景很强的人,但我非常喜欢这两个领域,并尝试深入理解这些问题。

例如,如果n表示2D列表的行,m表示列,那么对于每个蜗牛的“电路”,我需要将最小的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 的二维列表上的输出是 [1, 2, 3, 6, 9, 8, 7, 4, 5, 4],意味着我到达末尾后会向后移动。
在一个更大的 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],所以我在第一行来回移动。

谢谢您的关注,希望这符合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
5个回答

3

我只提供一个想法,代码需要由你自己编写。

蜗牛前进有四个方向,依次为:右(j += 1)、下(i += 1)、左(j -= 1)、上(i -= 1)。

蜗牛会按照这四个方向沿着圆形走(右、下、左、上、右、下、左...),直到到达边界或者已经访问过的数字。并且在达到边界或访问过的数字后,将转向下一个方向。当蜗牛无法走到任何一个格子时,结束运动。

无法走到任何一个格子 的定义:在蜗牛的当前方向和转向后的下一个方向中,都无法走到下一个格子。

带有注释的示例代码


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)


在4x4矩阵中,一旦到达数字4,向右转(在向上方向后,在圆圈中),然后继续前进。 - HolaYang
在原始矩阵中,到达一个数字后,将其更改为0(标记为已访问)。要检查我们是否在矩阵内(不超过边界),则应满足0<=i,j<=n。首先检查我们是否在矩阵内,其次再检查是否已访问。你可以做到的。 - HolaYang
@QuincyTennyson 如果你已经完成了你的代码,我提供了我的实现作为参考。 - HolaYang
请注意,“fence”在教育目的的玩具项目中效果很好,但在真实世界的生产代码中会被视为“异端邪说”。通常情况下,检查边界是正确的方法,而不是修改我们只应该观察的对象。 - m.raynal
嗨@HolaYang。你的解决方案看起来非常有趣,但是在codewars中实现完全相同的代码后,我可以通过测试,但它会出现超时错误。是否有其他人使用此代码提交答案? - mitra mirshafiee
显示剩余4条评论

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是1”(实际上,m = 0 +1,但结果相同),然后说“如果M不等于0(else情况),m = m-1”。
因此,在j + = 1之后的第一次迭代中,m为1,并进入第二种情况,使其向后移动。
您可以将“m> 0”重写为“m> j”,因为您在每个循环中都会增加J。
编辑: 您条件的第一部分也应重写为“m == j and n == j”,而不是0。否则,在第一次迭代后它将始终进入第二种情况。

1
这里有一个可能的方法,考虑到你提到了重构代码。因此,有几个要点可以帮助你从不同角度看待这个问题。
首先,我们设置一些东西:方向和蜗牛下一步要走的方向。由于方向是循环的(右,下,左,上,右,下...),我们可以用一个函数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

然后是从数组中获取值和将值设置为“visited”的函数。

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) == '*'

还有 'main' 函数。我在评论中使用了您的想法,用 '*' 替换了已访问数组中的位置。由于我们这样做,而不是检查边界,我们可以用 '*' 包围整个矩阵。

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]

编辑:
如果要使用数组边界进行操作,您可以添加一个新函数进行检查:

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)


我非常接近了,但是我不想使用列表边界来完成我的任务,因为我感觉这是窃取你解决方案的关键部分。如果加上边界会怎么样?以下是我目前完成的代码... https://gist.github.com/qetennyson/fb2862aee5b01d2074f5fd61f2467bd5 - Quincy Tennyson
谢谢!当我将它拆分成函数时,终于让它正常工作了(有趣的是,我在编写应用程序时会这样做,但当我解决这些问题时,我仍然处于脚本模式:D) - Quincy Tennyson
实际上,将代码分解为函数可以帮助很多,并且通常被认为是一种良好的实践(在一定程度上)。我写的整个东西可以轻松缩短3倍,仍然能够计算出正确的结果,但有时更长、更好组织的代码可以节省时间(调试、维护、修改等)。 - m.raynal
当然,也许我表达不太清楚。我的意思是,构建程序的行为使我的思维变得更好。我有一个习惯,即对于我真正需要编写的程序,我会进行适当的结构化。然而,对于这些小挑战问题,我的头脑回到了我第一次学习Python/编程时,只是写一堆丑陋的代码 :) - Quincy Tennyson

0
public class Snails {

    public static int getLoopFactor(int n) {
        return (int) (Math.log(n) / Math.log(2));
    }

    public static List<Integer> MatrixCorner(int[][] matrix, int startPosition) {
        int verify = 0;
        var result = new ArrayList<Integer>();
        var reverse = new ArrayList<Integer>();
        // first row
        for (int i = startPosition; i < matrix.length - startPosition; i++) {
            for (int j = startPosition; j < matrix.length - startPosition; j++) {
                result.add(matrix[i][j]);
                verify++;
            }
            break;
        }
        // last column
        for (int i = startPosition + 1; i < matrix.length - startPosition - 1; i++) {
            result.add(matrix[i][matrix.length - startPosition - 1]);
        }

        if (verify > 1) {
            // last row reversed
            for (int i = matrix.length - 1 - startPosition; i < matrix.length - startPosition; i++) {
                for (int j = startPosition; j < matrix.length - startPosition; j++) {
                    reverse.add(matrix[i][j]);
                }
                Collections.reverse(reverse);
                result.addAll(reverse);
                reverse.clear();
                break;
            }
        }
        //first column  reversed
        for (int i = startPosition + 1; i < matrix.length - startPosition - 1; i++) {
            reverse.add(matrix[i][startPosition]);
        }
        Collections.reverse(reverse);
        result.addAll(reverse);
        reverse.clear();
        return result;
    }

    public static int[] snail(int[][] array) {
        if (array.length == 0 || array[0].length == 0) return new int[]{};
        List<Integer> finalResult = new ArrayList<>();
        int k = getLoopFactor(array.length);
        int check = 0;
        while (check <= k) {
            finalResult.addAll(MatrixCorner(array, check));
            check++;
        }
        return finalResult.stream().mapToInt(Integer::intValue).toArray();
    }
}

虽然这段代码可能回答了问题,但提供有关它如何以及/或为什么解决问题的附加上下文将改善答案的长期价值。 - blazej

0
这是螺旋矩阵遍历-使用方向来高效遍历矩阵的方法=
vector<int> Solution::spiralOrder(const vector<vector<int>> &arr) {

int r = arr.size();
int c = arr[0].size();

int left = 0;
int right = c-1;

int top = 0;
int bottom = r-1;
int dir = 0;
vector<int> ans;

while(left <= right && top <= bottom){
      
    if(dir == 0){
        for(int i = left; i<=right; i++){
            ans.push_back(arr[top][i]);
        }
        top++;
        dir = 1;
    }
    else if(dir == 1){
        for(int i = top; i<=bottom; i++){
            ans.push_back(arr[i][right]);
        }
        right--;
        dir = 2;
    }
    else if(dir == 2){
        for(int i = right; i>=left; i--){
            ans.push_back(arr[bottom][i]);
        }
        bottom--;
        dir = 3;
    }
    else if(dir == 3){
        for(int i = bottom; i>=top; i--){
            ans.push_back(arr[i][left]);
        }
        left++;;
        dir = 0;
    }
}

return ans;

}


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接