Prosper Opara

Posted on May 17, 2019

Reinventing ruby flatten method

Introduction

I actively started re-learning ruby by solving challenge exercise from exercism and I thought I should write about the challenges I found a bit difficult and overcame. You can check out my profile on exercsim to see my progress.

Problem statement

The Ruby Array flatten method takes any deeply nested array (Multi-dimensional) and returns a non nested array using recursion. For example (open IRB[Interactive Ruby] in your terminal and run):

[1,[[3,4,6],3,7],5,1,[1,2,3],5].flatten
# => [1, 3, 4, 6, 3, 7, 5, 1, 1, 2, 3, 5]

This challenge exercise requires that I write my personal implementation of the method, without using the method.

My Implementation

My algorithm for solving this problem looked like:

Create a FlattenArray class with a flatten class method
The class method accepts a single array parameter arr
Create an emepty array flattened to hold the elements of the new array.
Loop through the array argument arr
Push each elements into flattened
Recursively push deeply nested array into flattened
Return the one-dimensional flattened array

Classes in Ruby are created by using the class keyword, a meaningful class name and the end keyword.

class FlattenArray
end

From my algorithm, the class has a class method flattenedand accepts a single parameter/argument. In Ruby, the self keyword is used for creating class methods (class methods are methods that belong to the class it was created in and not instances (objects) of the class).

class FlattenArray
  def self.flatten(array)
  end
end

The next steps include;

Creating the flattened array
Loop through the arr parameter
Push arr elements into flattened array

For looping through the array parameter, we'd utilize the each iterator (this loops through all the elements within an array, and allows you do manipulate the elements within a code block, and it additionally returns the original Enumerator without mutating it). Pushing the elements of arr into the flattened array possible with the use of << or .push method, but I'd be sticking with << (personal preference).

class FlattenArray
  def self.flatten(arr)
    flattened = []
    arr.each do |element|
      flattened << element
    end
  end
end

The next step involves adding a call to the flatten method within itself(this is called recursion) tp keep us from unnecessary nested iterations in cases of multi-dimensional array arguments.

class FlattenArray
  def self.flatten(arr)
    flattened = []
    arr.each do |element|
      if element.is_a? Array
        flattened.concat(flatten(element))
      else
        flattened << element
      end
    end
    flattened
  end
end

My initial challenge was using << to push into the flattened array, which actually push an array object into flattened. Using .concat method on the other hand appends each element from the iteration into flattened instead of pushing an array object. Testing manually to check if this implemetatio works

print FlattenArray::flatten [1,2,3,[[3,4],6,6]]

Omitting the parenthesis in a method call is allowable in ruby and correct ruby syntax. Also, I personally enjoy calling functions without parenthesis :)

Testing

Another feature I love about learning on exercism is that you'd solve the exercises using Test Driven Development(TDD) methodology and it's really cool I must say. Writing Test Suites in ruby requires that you have minitest gem installed, you can install minitest using the gem install command:

$ gem install minitest

Create a flatten_test.rb file in the same directory with flatten.rb (File for our flatten implementation code), in the newly created file require the minitest gem, require flatten.rb (using require_relative) and copy the following Test Suite:

require 'minitest/autorun'
require 'minitest/pride'
require_relative 'flatten_array'

# Common test data version: 1.2.0 0290376
class FlattenArrayTest < Minitest::Test
  def test_no_nesting
    # skip
    flat_array = FlattenArray.flatten([0, 1, 2])
    assert_equal [0, 1, 2], flat_array
  end

  def test_flattens_array_with_just_integers_present
    # skip
    flat_array = FlattenArray.flatten([1, [2, 3, 4, 5, 6, 7], 8])
    assert_equal [1, 2, 3, 4, 5, 6, 7, 8], flat_array
  end

  def test_5_level_nesting
    # skip
    flat_array = FlattenArray.flatten([0, 2, [[2, 3], 8, 100, 4, [[[50]]]], -2])
    assert_equal [0, 2, 2, 3, 8, 100, 4, 50, -2], flat_array
  end

  def test_6_level_nesting
    # skip
    flat_array = FlattenArray.flatten([1, [2, [[3]], [4, [[5]]], 6, 7], 8])
    assert_equal [1, 2, 3, 4, 5, 6, 7, 8], flat_array
  end

Make sure to un-comment the skip keyword within each test to enable the test code run and avoid skipping that test case. You can now run the command below in terminal:

$ ruby flatten_test.rb

To learn more about writing test in ruby, read intro to TDD

Wrap up

Exercism is an amazing tool for learning any programming language of your choice and also get mentorship while working on your solution. Exercism mentors don't hand you the fish, rather they give you the fish hook and tell you the coordinates of the fish, this totally makes fishing fun, research oriented and fast.

If you followed the code implementation from beginning to end, you must have discovered how awesome the Ruby programming language is and how lienient the syntax is, Ruby is one language i really enjoy writing and has an amazing ecosystem

Top comments (9)

jmc • May 18 '19 • Edited

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 reviewers won't help you if you're on independent mode (which makes sense, but the site claims that you can have up to one solution reviewed in that mode, even though in practice the reviewers seem to ignore them).

I like your concat solution, and obviously it's better not to mutate the input array. But FYI if you ever want to push one array onto another, you can use the splat operator:

> a = []; b = [1, 2]
> a.push(*b)
=> [1, 2]

My solution for flatten-array on the Clojure track used reduce for the outer loop and into (which is like a.push(*b) in Ruby except that it doesn't modify the original). But otherwise it's similar to what you have.

I was thinking that one could also write something iterative that uses a stack (perhaps of array indices), but didn't bother to try it on this one.

Also, if you're interested, out of curiosity I looked up what they do in Rubinius. It's a mostly-complete Ruby implementation written in Ruby itself and when writing Ruby I occasionally found their code useful to glance at. Theirs appears to also be recursive, and besides handling a max_depth argument, they also mention "checking for recursive structures" which I assume is for cycle detection, but I'm not 100% certain.

github.com/rubinius/rubinius/blob/...

Prosper Opara • May 18 '19

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

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.

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?