蜗牛算法——控制Max/Min位置进行遍历
Snail Algorithm - controlling Max/Min position for traversal
为了好玩，我正在 CodeWars 中解决一个问题，但我遇到了一些问题：
了解我需要在哪里修改代码以正确控制 m 和 n 的 "turning point"，以便它们开始减少而不是增加。
适当重构此代码。
算法的目的是像"snail"一样遍历二维列表，例如
[[1,2,3],
[4,5,6],
[7,8,9]]
应该return
[1,2,3,6,9,8,7,4,5]
对于任何大小为 n*n 的列表
我没有很强的数学或 CS 背景，但我真的很喜欢这两者，并尝试深入理解这些问题。
我知道，例如，如果 n 表示行，m 表示二维列表的列，我需要将每个的最小值 n 增加 1 "circuit" 的蜗牛，并减少每个电路的最大值 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]，意思是我走到尽头后退
在更大的 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 问题的指导方针。我不太关心为 exercise/getting 正确获得分数，而更关心理解为什么我的代码是 wrong/poor 实践。
更新
我相信我对这个问题的理解更好了，并且取得了一些进展，但让我失望的仍然是列表的范围。我觉得我在这方面真的很弱。我最终在一个方向上走得太远了，我所有的解决方案都非常笨拙。
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
我只是提供一个思路，代码还是自己写吧
蜗牛的头有四个方向，依次为右(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)
正在回答您关于 "what is wrong" 的问题：
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，但结果相同）
然后你说 "if M is not == 0 (the else case), m = m -1"
因此，在 j+=1 之后的第一次迭代中，m 为 1，然后转到第二种情况，使其倒退。
您可以 re-write 将 "m > 0" 改为 "m > j"，因为您在每个循环中将 J 增加 1。
编辑：
你的条件的第一部分也应该是 re-written 作为 "m == j and n == j"，而不是 0。否则，它总是会在第一次迭代后转到第二种情况。
考虑到您谈到重构代码，这是一种可行的方法。所以有几点可以帮助你换个角度看这个问题。
首先，我们设置一些东西：方向，以及蜗牛的下一个方向。由于方向是循环的（右、下、左、上、右、下……），我们可以用函数 next_direction 来表示。
另外，创建一个简单的 'updates' 位置的函数可以使代码更易于阅读。
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)
这是螺旋阶矩阵遍历-使用方向遍历矩阵的高效方法=
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;
}
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();
}
}
为了好玩，我正在 CodeWars 中解决一个问题，但我遇到了一些问题：
了解我需要在哪里修改代码以正确控制 m 和 n 的 "turning point"，以便它们开始减少而不是增加。
适当重构此代码。
算法的目的是像"snail"一样遍历二维列表，例如
[[1,2,3],
[4,5,6],
[7,8,9]]
应该return
[1,2,3,6,9,8,7,4,5]
对于任何大小为 n*n 的列表
我没有很强的数学或 CS 背景，但我真的很喜欢这两者，并尝试深入理解这些问题。
我知道，例如，如果 n 表示行，m 表示二维列表的列，我需要将每个的最小值 n 增加 1 "circuit" 的蜗牛，并减少每个电路的最大值 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]，意思是我走到尽头后退
在更大的 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 问题的指导方针。我不太关心为 exercise/getting 正确获得分数，而更关心理解为什么我的代码是 wrong/poor 实践。
更新
我相信我对这个问题的理解更好了，并且取得了一些进展，但让我失望的仍然是列表的范围。我觉得我在这方面真的很弱。我最终在一个方向上走得太远了，我所有的解决方案都非常笨拙。
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
我只是提供一个思路，代码还是自己写吧
蜗牛的头有四个方向，依次为右(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)
正在回答您关于 "what is wrong" 的问题：
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，但结果相同） 然后你说 "if M is not == 0 (the else case), m = m -1"
因此，在 j+=1 之后的第一次迭代中，m 为 1，然后转到第二种情况，使其倒退。
您可以 re-write 将 "m > 0" 改为 "m > j"，因为您在每个循环中将 J 增加 1。
编辑： 你的条件的第一部分也应该是 re-written 作为 "m == j and n == j"，而不是 0。否则，它总是会在第一次迭代后转到第二种情况。
考虑到您谈到重构代码，这是一种可行的方法。所以有几点可以帮助你换个角度看这个问题。
首先，我们设置一些东西：方向，以及蜗牛的下一个方向。由于方向是循环的（右、下、左、上、右、下……），我们可以用函数 next_direction 来表示。
另外，创建一个简单的 'updates' 位置的函数可以使代码更易于阅读。
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)
这是螺旋阶矩阵遍历-使用方向遍历矩阵的高效方法=
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;
}
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();
}
}