Snail Algorithm – controlling Max/Min position for traversal

I’m working on a problem in CodeWars for fun, and I’m having trouble with a couple of things:

1. Understanding where I need to modify the code in order to properly control the “turning point” of m and n so that they begin decreasing rather than increasing.

2. Refactoring this code appropriately.

The purpose of the algorithm is to traverse a 2D list like a “snail”, e.g.

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

should return

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

for any list of size n*n

I don’t have a strong background in math or CS, but I really love both and try to understand these problems with depth.

I know, for example, that if n represents the rows and m represents the columns of the 2D list, I need to increase the minimum n by 1 for each “circuit” of the snail, and decrease the maximum m for each circuit, but I’m having trouble understanding where that needs to happen.

I have looked at some recursive solutions briefly, but before I started delving into those, I was hoping someone could take a look at this and help me understand where my thinking is totally wrong.

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

The output of this algorithm on a 3×3 2D list is presently [1, 2, 3, 6, 9, 8, 7, 4, 5, 4], meaning I am moving backwards after reaching the end.

On a larger 2D list of 4×4,

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

the output is [1, 2, 3, 4, 7, 11, 15, 14, 13, 12, 8, 4, 5, 4, 5, 4], so I am going back and forth on the 1st row.

Thanks for taking a look, and I hope this falls within the guidelines for a SO question. I care less about getting points for the exercise/getting it right and more about understanding why my code is wrong/poor practice.

Update

I’m understanding the problem better, I believe, and have made some progress, but what is killing me is still the bounds of the list. I feel like I’m really weak on that. I end up going too far in one direction, and all of my solutions for that are really hamfisted.

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

I’ll only provide an idea and code should be written by yourself.

There are four directions the snail heads to, in order, right(j += 1), down(i += 1), left(j -= 1), up(i -= 1).

Snail will go by these four directions on circle(right, down, left, up, right, down, left…) , turn into next direction util reach the border or the number visited. And ends when the snail can not walk to any grid.

The definition of can not walk to any grid: can not step into next grid in the direction and in next direction.

Sample code with comment

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)