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
}
7 months ago
  • 8da57acFix minor bugs found by the code static ana…
7 months ago
  • caa417fAdd option to configure the malware scanner…
7 months ago
  • 9c86744Modify default value for some of the alert …
7 months ago
  • 84dd39dAdd option to stop sending the failed login…
7 months ago
  • eb05935Add pre-checks for every plugin page for si…
7 months ago
  • d21a062Modify mechanism to ignore files from integ…
7 months ago
  • b1a9169Add developer option to disable failed pass…
7 months ago
  • 4e3ef13Add support for other English and Spanish b…
7 months ago
  • 2d07b4eFix error interception for Firewall API err…
7 months ago
pushed to master at cixtor/slackapi
  • 4a2c1c8Modify data type for methods related to cha…
  • 6716199Add CLI handler for the users.identity API …
  • f9c448dAdd CLI handler for the mpim.open API endpo…
  • 305d1c4Add CLI handler for the mpim.mark API endpo…
  • 8bb89afAdd CLI handler for the mpim.close API endp…
  • 202a017Add CLI handler for the dnd.teamInfo API en…
  • 68819e9Add CLI handler for the dnd.info API endpoi…
  • 9a2b29aAdd CLI handler for the dnd.endSnooze API e…
  • e7dc86aAdd CLI handler for the dnd.setSnooze API e…
  • 111c53fAdd CLI handler for the dnd.endDnd API endp…
  • cdb620dFix token usage when there are no extra par…
  • View comparison for these 11 commits
7 months ago
pushed to master at cixtor/slackapi
7 months ago
  • 6497e80Remove unnecessary automatic blacklisting o…
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#40
Fix multiple bugs with the API calls and queue system
18 commit with 793 additions and 293 deletion
7 months ago
7 months ago
7 months ago
  • 38cc02aModify timing for the dashboard alerts afte…
7 months ago
  • 350c074Fix infinite loop with email alerts and SMT…
7 months ago
  • acff4aaFix detection of base URL with built-in fun…
7 months ago
7 months ago
7 months ago
7 months ago
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#39
Add queue system for the security logs and cache improvement
5 commit with 517 additions and 541 deletion
7 months ago
7 months ago
  • 4c51445Fix static function call of non-static Site…
7 months ago
7 months ago
  • af47581Add changelog to release version 1.8.6
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#38
Add changelog to release version 1.8.5
6 commit with 4062 additions and 1841 deletion
7 months ago
  • dc1a05aAdd changelog to release version 1.8.5
7 months ago
Do you have a project idea? Let's make it together!