CtCI - Snail Sort

CtCI - Snail Sort

Snails are members of the molluscan class Gastropoda, these animals have a coiled shell that is large enough for them to retract completely into. The shell displays a pattern that follows a spiral from around the center to the outermost part usually in a clock-wise manner.

Snail Sort is an algorithm that takes a multi-dimensional array and flattens it to create a new array with all the elements from the matrix but in the same order as a snail shell. This is, starting from the top-left side of the matrix and ending on the center as pictured below.

@ @ @ @ @ @ @  ->  ────────────┐
@ @ @ @ @ @ @  ->  ┌─────────┐ │
@ @ @ @ @ @ @  ->  │ ┌─────┐ │ │
@ @ @ @ @ @ @  ->  │ │ ┌── │ │ │
@ @ @ @ @ @ @  ->  │ │ └───┘ │ │
@ @ @ @ @ @ @  ->  │ └───────┘ │
@ @ @ @ @ @ @  ->  └───────────┘

For a multi-dimensional array like this:

var arr = [][]int{
  []int{ 1,  2,  3,  4,  5,  6,  7},
  []int{ 8,  9, 10, 11, 12, 13, 14},
  []int{15, 16, 17, 18, 19, 20, 21},
  []int{22, 23, 24, 25, 26, 27, 28},
  []int{29, 30, 31, 32, 33, 34, 35},
  []int{36, 37, 38, 39, 40, 41, 42},
  []int{43, 44, 45, 46, 47, 48, 49},
}

We want to generate a flatten array like this:

var res []int{
    01, 02, 03, 04, 05, 06, 07,
    14, 21, 28, 35, 42, 49, 48,
    47, 46, 45, 44, 43, 36, 29,
    22, 15, 08, 09, 10, 11, 12,
    13, 20, 27, 34, 41, 40, 39,
    38, 37, 30, 23, 16, 17, 18,
    19, 26, 33, 32, 31, 24, 25,
}

There are multiple algorithms on the Internet that can be used to flatten this array, here I will explain one that I call “The Recursive Box” in which each call of a function we extract the outermost part of the matrix that I refer to as box, then we reduce the size of the box and call the function recursively until no more items are left, ultimately the function will merge all boxes and end up with the flatten array.

Let’s visualize the algorithm first.

/* 1st OUT */    /* 2nd OUT */    /* 3rd OUT */    /* 4rd OUT */
@ @ @ @ @ @ @    . . . . . . .    . . . . . . .    . . . . . . .
@ . . . . . @    . @ @ @ @ @ .    . . . . . . .    . . . . . . .
@ . . . . . @    . @ . . . @ .    . . @ @ @ . .    . . . . . . .
@ . . . . . @ -> . @ . . . @ . -> . . @ . @ . . -> . . . @ . . .
@ . . . . . @    . @ . . . @ .    . . @ @ @ . .    . . . . . . .
@ . . . . . @    . @ @ @ @ @ .    . . . . . . .    . . . . . . .
@ @ @ @ @ @ @    . . . . . . .    . . . . . . .    . . . . . . .

Each time we call the function we process a matrix with N-2 where N is the original size both in width and height. But notice that in the first iteration we have that the number of items at the top and bottom is different than the number of items on the sides, lets visualize this to have a clear idea:

@ @ @ @ @ @ @
# . . . . . #  (@) Top:     7
# . . . . . #  (#) Left:    5
# . . . . . #  (@) Bottom:  7
# . . . . . #  (#) Right:   5
# . . . . . #      Total:  24
@ @ @ @ @ @ @

We need more stability to reduce the ambiguity and errors in the algorithm.

@ @ @ @ @ @ #
& . . . . . #  (@) Top:     6
& . . . . . #  (&) Left:    6
& . . . . . #  (%) Bottom:  6
& . . . . . #  (#) Right:   6
& . . . . . #      Total:  24
& % % % % % %

The number of items that we will read per side will be equal to W-1 and H-1 where W is the width of the matrix and H is the height, respectively. In this example the matrix is symmetric, both the width and height are the same, but the same calculus can be applied to a non-symmetric matrix where the width is bigger than the height or vice-versa.

Getting the top part is easy because it is composed by a consecutive list of items from the first array in the matrix. An array slice from index zero to index W-1 will be enough. Here M is the rightmost index in any of the Y axis, it is basically the length of any of the sub-arrays minus one.

var m int = len(matrix) - 1
var out []int = matrix[0][0:m]

This will select the relevant items from the top side of the box:

@ @ @ @ @ @ .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .

Now for the right side, we have to select the last element of each sub-array, we can do this by iterating through each line and selecting W-1 where W is the width of the matrix. Remember that M is the last index on each sub-array, we could use W-1 but we defined M in the previous code and is better to recycle.

for y := 0; y < m; y++ {
    out = append(out, matrix[y][m])
}

This will select the relevant items from the right side of the box:

. . . . . . @
. . . . . . @
. . . . . . @
. . . . . . @
. . . . . . @
. . . . . . @
. . . . . . .

The bottom side of the box is similar to the top part, except that the order of the items is inverted, the first item on the left becomes the last item on the right. This part of the algorithm might differ depending on which language you are using to implement it, for Python for example we could simply select A[1::-1] but in this case I prefer to be more explicit and let the syntax sugar to you.

for x := m; x > 0; x-- {
    out = append(out, matrix[m][x])
}

This will select the relevant items from the bottom side of the box:

. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. @ @ @ @ @ @

The left side is selected using the same code as the right side, except that we start the iteration from index W-1 — or M in this case — the selector will always be position zero as the first element of each line, and end up at index one. We cannot go up to zero because that item was already added to the flatten array as the first element of the with coordinates 0,0.

for y := m; y > 0; y-- {
    out = append(out, matrix[y][0])
}

This will select the relevant items from the left side of the box:

. . . . . . .
@ . . . . . .
@ . . . . . .
@ . . . . . .
@ . . . . . .
@ . . . . . .
@ . . . . . .

At this point we had collected the four sides of the box. Here is where most algorithms differ, the one explained below will have a higher time and space complexity because of the recursive call and the assignment of the remaining items from the inner box. An optimized version of the same algorithm would remove the recursion and instead execute the four steps explained above in a loop reducing the size of M.

I will let you decide which approach to use.

Let’s now select the inner box, we will create a new matrix with the elements from each line from index one to index W-1, the first and last lines will be skipped as they were already processed. We will then pass this new matrix to the same function and merge its result with the flatten array that we generated above.

Notice that we do not need to merge if there are no remains.

var remaining [][]int

for y := 1; y < m; y++ {
    remaining = append(remaining, matrix[y][1:m])
}

if remaining != nil {
    out = append(out, SnailSort(remaining)...)
}

This will select the following items:

. . . . . . .
. @ @ @ @ @ .
. @ @ @ @ @ .
. @ @ @ @ @ .
. @ @ @ @ @ .
. @ @ @ @ @ .
. . . . . . .

How do we know when to stop the recursion? We know from the beginning the size of the matrix, and after the selection of the top, right, bottom and left sides of the box we end up with a flatten array with size X where X is either lower than or equal to the size of the matrix, if they are different we can assume that there are remaining items at the center of the box, otherwise we stop the recursion.

if len(out) < len(matrix)*len(matrix) {
    var remaining [][]int
    [...]
}

Here is the full implementation. Notice how we are also returning an empty array if the matrix is empty. And returning the unique element in a matrix of 1x1 which is usually the remaining item in an odd matrix where either W%2==1 or H%2==1.

func SnailSort(matrix [][]int) []int {
    if len(matrix) == 0 {
        return []int{}
    }

    if len(matrix) == 1 {
        return matrix[0]
    }

    var m int = len(matrix) - 1
    var out []int = matrix[0][0:m]

    for y := 0; y < m; y++ {
        out = append(out, matrix[y][m])
    }

    for x := m; x > 0; x-- {
        out = append(out, matrix[m][x])
    }

    for y := m; y > 0; y-- {
        out = append(out, matrix[y][0])
    }

    if len(out) < len(matrix)*len(matrix) {
        var remaining [][]int

        for y := 1; y < m; y++ {
            remaining = append(remaining, matrix[y][1:m])
        }

        if remaining != nil {
            out = append(out, SnailSort(remaining)...)
        }
    }

    return out
}
Do you have a project idea? Let's make it together!