DEV Community

Discussion on: Reinventing ruby flatten method

 
kodekage profile image
Prosper Opara

I honestly don't understand this yet.

Thread Thread
 
johncip profile image
jmc • 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.