DEV Community

Daily Challenge #59 - Snail Sort

dev.to staff on September 06, 2019

array = [[1,2,3], [4,5,6], [7,8,9]] snail(array) #=> [1,2,3,6,9,8,7,4,5] Given an array of n * x, return the array elements...

Read full post

La blatte • Sep 6 '19

Here it is!

snail = arr =>
    arr.length > 1
      ? [
          ...arr.shift(),
          ...arr.map(e => e.pop()),
          ...arr.pop().reverse(),
          ...arr.reverse().map(e => e.shift())
        ].concat(arr.length ? snail(arr.reverse()) : [])
      : arr[0];

It works kinda litterally:

Take the first line of the array
Add every remaining last element
Add the last line, reversed
Reverse the array, and return every first element
Restart, with the remaining elements

And the results:

snail([[]])
[]
snail([[1]])
[1]
snail([[1, 2, 3], 
        [4, 5, 6], 
        [7, 8, 9]]);
(9) [1, 2, 3, 6, 9, 8, 7, 4, 5]
snail([[1, 2, 3, 4, 5], 
        [6, 7, 8, 9, 10], 
        [11, 12, 13, 14, 15], 
        [16, 17, 18, 19, 20], 
        [21, 22, 23, 24, 25]]);
(25) [1, 2, 3, 4, 5, 10, 15, 20, 25, 24, 23, 22, 21, 16, 11, 6, 7, 8, 9, 14, 19, 18, 17, 12, 13]
snail([[1, 2, 3, 4, 5, 6],
        [20, 21, 22, 23, 24, 7], 
        [19, 32, 33, 34, 25, 8], 
        [18, 31, 36, 35, 26, 9], 
        [17, 30, 29, 28, 27, 10], 
        [16, 15, 14, 13, 12, 11]])
(36) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36]

Melvin Yeo • Sep 7 '19

Solution in Python based on La blatte's wonderful implementation if anyone is interested!

def snail(arr):
    return arr[0] if len(arr) == 1 else [*arr.pop(0), *[elem.pop() for elem in arr], *arr.pop()[::-1], *[elem.pop(0) for elem in arr[::-1]]] + snail(arr) if len(arr) else []

Chris Achard • Sep 6 '19

Much cleaner than mine! Nicely done 🎉

Cagatay Kaya • Sep 6 '19

I did the same thing with nearly 10x more code. Great work!

Craig McIlwrath • Sep 6 '19

Haskell:

middle :: [a] -> [a]
middle [] = []
middle [_] = []
middle [_,_] = []
middle xs = init $ tail xs

snail :: [[a]] -> [a]
snail [] = []
snail [x] = x
snail (x:xs) = let middleRows = init xs
               in x ++
                  map last xs ++
                  reverse (init (last xs)) ++
                  reverse (map head middleRows) ++
                  snail (map middle middleRows)

Mat-R-Such • Aug 25 '20

Python

def remove (a):
    # remove first row 
    a = a[1:]  
    return a
def reversedMy (a):
    # reverse array 
    a= list(reversed(a))
    # reverse any row in array
    return [list(reversed(a[i])) for i in range(len(a))]
def snail (a):
    if len(a[0]) == 0:      return [[]]
    maks = len(a)*len(a[0])
    tab= []
    while len(tab) < maks:

        for i in range(len(a[0])):
            tab.append(a[0][i])

        a = remove(a)
        m = len(a)

        for i in range(0,m):
            tab.append(a[i][m])
            a[i].pop(m)

        a = reversedMy(a)

    return tab

Chris Achard • Sep 6 '19

Tricky! Not sure I found the most efficient way to do it - but it works, and I think it's relatively clean(ish) :)

Watch me solve it too: youtu.be/h-OzkY1_8mU

const snail = array => {
  const middle = array.slice(1, array.length - 1).map(row => 
    row.slice(1, row.length - 1)  
  )

  return [
    array[0],
    array.slice(1, array.length - 1).map(row => 
      row[row.length - 1]
    ),
    array.length > 1 ? array[array.length - 1].reverse() : [],
    array.slice(1, array.length - 1).reverse().map(row => 
      row[0]
    ),
    middle.length > 0 ? snail(middle) : []
  ].flat()
}

Antonio Turner • Sep 28 '21

Hey Chris, I made a replica of your solution translated to Python3.5 or greater.

from itertools import chain

def snail(arr):
    mid = list(map(lambda row : row[slice(1, len(row)-1)], arr[slice(1,len(arr)-1)]))


    return list(chain.from_iterable([
        arr[0],
        list(map(lambda row: row[len(row)-1], arr[slice(1,len(arr)-1)])),
        list(reversed(arr[len(arr)-1])) if len(arr) > 1 else [],
        list(map(lambda row: row[0],list(reversed(arr[slice(1,len(arr)-1)])))),
        snail(mid) if len(mid) > 0 else []

     ]))if len(arr) >= 1 else [[]]

Cagatay Kaya • Sep 6 '19

It only works where both of the lengths of the arrays are equal. Otherwise, it adds cute 'undefined' in the end. Also, these if checks are there for safety. They may be ugly and repetitive but I did not want the calculate every other case.

const snail = input => {
  let finalResult = [];
  while (
    typeof input != "undefined" &&
    input != null &&
    input.length != null &&
    input.length > 0
  ) {
    const a = input.length;
    //take first line in whole
    if (
      typeof input != "undefined" &&
      input != null &&
      input.length != null &&
      input.length > 0
    ) {
      result = [...input.shift()];
    }

    //take end of each line
    if (
      typeof input != "undefined" &&
      input != null &&
      input.length != null &&
      input.length > 0
    ) {
      for (let index = 0; index < a - 1; index++) {
        const element = input[index].pop();
        result.push(element);
      }
    }
    //take last line in reverse
    if (
      typeof input != "undefined" &&
      input != null &&
      input.length != null &&
      input.length > 0
    ) {
      result = [...result, ...input.pop().reverse()];
    }

    //take start of each middle line
    if (
      typeof input != "undefined" &&
      input != null &&
      input.length != null &&
      input.length > 0
    ) {
      for (let index = a - 3; index > -1; index--) {
        const element = input[index].shift();
        result.push(element);
      }
    }
    //add this loop's result to finalResult
    finalResult = [...finalResult, ...result];
  }
  console.log(finalResult);
};

Anders • Sep 6 '19 • Edited

A different take, this one might not appear as elegant, but it is quite a lot faster than the previous variants:

function snail(m) {

if (m.length <= 1) { return m; }

var max = { x: m.length - 1, y: m.length - 1 };
var min = { x: 0, y: 0 };
var current = { x: 0, y: 0 };
var direction = { x: 1, y: 0 };
var output = [];
var resultSize = m.length * m.length;

while (output.length != resultSize) {

    output.push(m[current.y][current.x]);

    current.x += direction.x;
    current.y += direction.y;

    if (current.x > max.x) { 

        direction.x = 0; direction.y = 1; min.y += 1; current.x = max.x; current.y += 1;

    } else if (current.x < min.x) { 

        direction.x = 0; direction.y = -1; max.y -= 1; current.x = min.x; current.y -= 1;

    } else if (current.y > max.y) { 

        direction.x = -1; direction.y = 0; max.x -= 1; current.y = max.y; current.x -= 1;

    } else if (current.y < min.y) { 

        direction.x = 1; direction.y = 0; min.x += 1; current.y = min.y; current.x += 1;
    }
}

return output;
}

Anders • Sep 6 '19 • Edited

So there was supposed to be an image attached, but it doesn't seem to work, anyhow, for those curious JSBench.me gives the following results:

Above one
2,508,265 ops/s ±0.46%

Chris Achards
411,247 ops/s ±1.04%

La blattes
364,899 ops/s ±3.35%

(Firefox, Windows)

snail([[1, 2, 3, 4, 5, 6],
[20, 21, 22, 23, 24, 7],
[19, 32, 33, 34, 25, 8],
[18, 31, 36, 35, 26, 9],
[17, 30, 29, 28, 27, 10],
[16, 15, 14, 13, 12, 11]]);

Oleksii Filonenko • Sep 6 '19

Reminds me of this task on Exercism :)

Olek Ria • Sep 6 '19

Cool task from hackerrank :)