Recursion problem on Codewars Kata - Snail Trail

Question

Very new to coding so please bear with me. I am attempting to solve this Kata on Codewars: https://www.codewars.com/kata/snail/train/javascript

Basically given an array like

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

It would return [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16].

A snail trail spiraling around the outside of the matrix and inwards.

I am just solving for the case where the matrix is n x n where n is > 1 and an even number for now.

I got it working by declaring outputarray outside the function but I want that array to be declared within the function, hence the inclusion of this line: var outputarray = outputarray || [];

Not sure where I am going wrong.

snail = function(array) {
  if (array.length == 0) {
    return outputarray
  }
  var n = array[0].length - 1;
  var outputarray = outputarray || [];
  for (var i = 0; i <= n; i++) {
    outputarray.push(array[0].splice(0, 1));
  }
  for (var i = 1; i <= n; i++) {
    outputarray.push(array[i].splice(n, 1));
  }
  for (var i = n - 1; i >= 0; i--) {
    outputarray.push(array[n].splice(i, 1));
  }
  for (var i = n - 1; i > 0; i--) {
    outputarray.push(array[i].splice(0, 1));
  }
  array.pop();
  array.shift();
  snail(array);
}

Another [Q](https://stackoverflow.com/q/57946428) & [A](https://stackoverflow.com/a/57949870) gives some good approaches. (I like my solutions involving a slice-and-transpose recursion.) And there are many other approaches in many languages in https://stackoverflow.com/questions/726756 — Scott Sauyet, Dec 02 '19 at 16:22

score 2 · Answer 1 · answered Nov 27 '19 at 21:57

Here's a non-recursive approach that doesn't mutate the input array. It works by keeping track of the top-left coordinate x, y and the size n of the spiral.

snail = function(array) {
  const { length } = array;
  const result = [];
  let x = 0;
  let y = 0;
  let n = length;

  while (n > 0) {
    // travel right from top-left of spiral
    for (let i = x; i < x + n; ++i) result.push(array[y][i]);

    // shrink spiral and move top of spiral down
    n--; y++;

    // travel down from top-right of spiral
    for (let i = y; i < y + n; ++i) result.push(array[i][x + n]);

    // travel left from bottom-right of spiral
    for (let i = x + n - 1; i >= x; --i) result.push(array[y + n - 1][i]);

    // shrink spiral
    n--;

    // travel up from bottom-left of spiral
    for (let i = y + n - 1; i >= y; --i) result.push(array[i][x]);

    // move left of spiral right
    x++;
  }

  return result;
}

console.log(snail([[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]));

score 1 · Answer 2 · answered Nov 27 '19 at 21:21

One option is to define another function inside snail, which calls itself recursively, while also defining the outputarray inside snail. That way, outputarray isn't exposed to the outer scope, but the recursive function can still see it.

Also note that splice returns an array, so right now, your outputarray gets composed of an array of arrays. Spread into push instead to fix it, so that the outputarray becomes an array of numbers:

const input = [
  [1, 2, 3, 4],
  [12, 13, 14, 5],
  [11, 16, 15, 6],
  [10, 9, 8, 7]
];

const snail = (array) => {
  const outputarray = [];
  const iter = () => {
    if (array.length == 0) {
      return
    }
    var n = array[0].length - 1;
    for (var i = 0; i <= n; i++) {
      outputarray.push(...array[0].splice(0, 1));
    }
    for (var i = 1; i <= n; i++) {
      outputarray.push(...array[i].splice(n, 1));
    }
    for (var i = n - 1; i >= 0; i--) {
      outputarray.push(...array[n].splice(i, 1));
    }
    for (var i = n - 1; i > 0; i--) {
      outputarray.push(...array[i].splice(0, 1));
    }
    array.pop();
    array.shift();
    iter(array);
  };
  iter(array);
  return outputarray;
}

console.log(snail(input));

This seems like the only answer that actually attempts to answer the OP's question :) — גלעד ברקן, Nov 28 '19 at 07:56

score 0 · Answer 3 · answered Nov 27 '19 at 22:08

You could take some borders for the left, right, upper and lower indices and loop until no more indices are available.

function snail(array) {
    var upper = 0,
        lower = array.length - 1,
        left = 0,
        right = array[0].length - 1,
        i = upper,
        j = left,
        result = [];

    while (true) {
        if (upper++ > lower) break;

        for (; j < right; j++) result.push(array[i][j]);
        if (right-- < left) break;

        for (; i < lower; i++) result.push(array[i][j]);
        if (lower-- < upper) break;

        for (; j > left; j--) result.push(array[i][j]);
        if (left++ > right) break;

        for (; i > upper; i--) result.push(array[i][j]);
    }

    result.push(array[i][j]);
    return result;
}

console.log(...snail([[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]));

Fabien · Answer 4 · 2019-11-27T22:42:42.463

Try this:

const input = [
  [1, 2, 3, 4],
  [12, 13, 14, 5],
  [11, 16, 15, 6],
  [10, 9, 8, 7]
];

function snail(array) {
  var res = [];
  
  if (!array.length) return res;
  var next = array.shift();
  if (next) res = res.concat(next);
  for (var i = 0; i < array.length; i++) {
    res.push(array[i].pop());
  }
  next = array.pop()
  if (next) res = res.concat(next.reverse());
  for (var i = array.length - 1; i >= 0; i--) {
    res.push(array[i].shift());
  }

  return res.concat(snail(array));
}
console.log(snail(input));

score 0 · Answer 5 · answered Nov 27 '19 at 22:32

This may not be according to the rules (or spirit?) of the kata, however, you can just glue it all together and sort.

function snail(trail) {
  const numeric = (a, b) => a - b
  const gather = (items, item) => items.push(parseInt(item, 10)) && items
  const inline = (route, points) => points.reduce(gather, route) && route
  const order = paths => paths.reduce(inline, []).sort(numeric)

  return order(trail)
}

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

console.log(JSON.stringify(snail(trail)))

I think the point was to traverse in a path of a spiral, not return a sorted list of values (e.g., switching 4 and 3 should result in [1, 2, 4, 3...etc.). — גלעד ברקן, Nov 28 '19 at 03:38

גלעד ברקן · Answer 6 · 2019-11-28T06:47:01.327

0

Here's my two cents, using the customary recursion:

function f(A){
  return A.length > 1 ? A.splice(0,1)[0].concat(
    f(A[0].map((c, i) => A.map(r => r[i])).reverse())) : A[0]
}

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

console.log(JSON.stringify(f(A)))

edited Nov 28 '19 at 06:47

answered Nov 28 '19 at 06:41

גלעד ברקן

23,602
3
25
61

It should be noted, though, that this solution mutates the original. To my mind, that's disqualifying. (And yes, I know that this is easy to fix.) – Scott Sauyet Dec 02 '19 at 16:28
@ScottSauyet mine isn't the only answer here that mutates the original, is it? – גלעד ברקן Dec 02 '19 at 16:30
@ScottSauyet this is for demonstration only. I would prefer a more efficient solution in practice without transposition :) – גלעד ברקן Dec 02 '19 at 16:34
No, just the first one I read. And I recall you [answering](https://stackoverflow.com/a/57949438/1243641) an earlier version of this question in a non-mutating manner. And as this is mostly a puzzle, I imagine, and not likely to run out of stack space or other resources, I'd usually prefer the cleanest solution unless it proves impractically slow. – Scott Sauyet Dec 02 '19 at 16:44
@ScottSauyet how do you define "clean?" – גלעד ברקן Dec 02 '19 at 16:55
@ScottSauyet that earlier answer looks like making the turns was more of a puzzle than the puzzle itself :) – גלעד ברקן Dec 02 '19 at 16:58
I don't try to define "clean". Like [Judge Potter Stewart](https://en.wikipedia.org/wiki/Jacobellis_v._Ohio#Supreme_Court) said, I know it when I see it. I really like code that is simple in the [Rich Hickey](https://www.infoq.com/presentations/Simple-Made-Easy/) sense. For instance here, I would prefer to define and use a rotation function and build this atop that, rather than merge its implementation into the function. (And of course `rotate` can be built atop `transpose` and `reverse`...) – Scott Sauyet Dec 02 '19 at 17:05
@ScottSauyet that's fair. And I like to go against the grain. Where someone champions clean I sometimes like to throw in dirty and vice versa. – גלעד ברקן Dec 02 '19 at 17:11

Recursion problem on Codewars Kata - Snail Trail

6 Answers6