Discussion on: Reinventing ruby flatten method

View post

Replies for: I've been enjoying Exercism too, and am getting close to done with the Clojure track. My one gripe is that I've unfortunately noticed that the rev...

When you say Independent Mode do you mean the Personal Edition mode?

From my experience, i mostly come up with my own solution to the task, and the reviewers mostly point me tho new methods that can make my solution cleaner.

I totally appreciate your pointing out splat operator, using it with push() makes push work like concat

I was thinking that one could also write something iterative that uses an explicit stack (perhaps of array indices) if you absolutely had to avoid recursion, but I've never bothered to try.

I did this in one of my solutions, but you'd be doing a lot of deeply nested iterations, because the array you want to flatten might for example be 5 dimension while you might have catered for only 3-4 dimensions.

jmc • May 18 '19 • Edited

Also I don't remember seeing a "Personal Edition" specifically but I know that when I picked a track on Exercism I was asked to choose between mentored or independent. Maybe it's the same thing?

Prosper Opara • May 29 '19

I checked out the modes for using exercism:

Mentors not helping out in the Independent mode is just what it's intended for.

But opting for the mentored mode is really the best way to get maximum benefit from the platform (at least for a beginner)

jmc • May 18 '19 • Edited

I did this in one of my solutions, but you'd be doing a lot of deeply nested iterations, because the array you want to flatten might for example be 5 dimension while you might have catered for only 3-4 dimensions.

Very true, the problem with explicit nested loops is that you can run out of loops :P

That's where a stack helps: I was specifically picturing a stack of indices, for instance [1, 5, 3], which means you'd next read the element at arr[1][5][3].

If index 3 of the grandchild holds the final element, then after reading it, you'd pop the 3 off the stack, and increment the new tail: the stack becomes [1, 6] and you next read arr[1][6].

And if that element happens to be an array, then you push a new index onto the stack: [1, 6, 0] (it grows on the tail end).

Hopefully I'm explaining myself well. In general, walking a nested thing requires "bookmarking" your place in the outer structures, in order to return to them when an inner structure is done. And for that you need a data structure that grows and shrinks as the nesting level changes. In recursive code, the call stack does it for you.

Prosper Opara • May 29 '19

I honestly don't understand this yet.

jmc • May 30 '19 • Edited

Hey, thanks for letting me know. Here's a code example in JS, hopefully some code will be clearer than a description of code:

// think of each element in the nested structure as having a list
// of indices. (sort of like "street, city, state, country" in
// a real address.)

// given arr = [["a", ["b"]], "c"]:
//   "a" is at [0, 0]
//   "b" is at [0, 1, 0]
//   "c" is at [1]
//
// note that the numbers correspond to how you'd access them:
// [0, 1, 0] -> arr[0][1][0] -> "b"

// we're going to create these lists, using an array that we'll modify
// as we go. it will grow or shrink as we enter or exit subarrays.
// we'll increment the last number to move forward in the input.

function flatten (arr) {
  const result = []
  const stack = [0]

  while (stack.length) {
    // get the current value
    let el = arr; stack.forEach(i => el = el[i])

    // new subarray; grow stack
    if (el instanceof Array) {
      stack.push(0)

    // subarray ended; shrink stack
    } else if (el === undefined) {
      stack.pop()
      stack[stack.length - 1]++

    // non-array; add to result
    } else {
      result.push(el)
      stack[stack.length - 1]++
    }
  }

  return result
}

console.log(flatten([[1, 2], 3, [[4, [5]]]])) // [1, 2, 3, 4, 5]

The recursive solution is cleaner, of course. And this will skip items if the input contains undefined as an element anywhere, but you could avoid that by checking the subarray lengths.