Recursively Replicating Ruby's Flatten Method

You can view the full .flatten method challenge here.

Flatten Challenge

The flatten method is a handy tool to compress nested arrays into one, flat array without losing any of the data. It works like this:

> [[1, 3], [5, [7, 9]]].flatten
=> [1, 3, 5, 7, 9]

Instead of relying on the .flatten method in Ruby, we'll build our own recursively. 

TDD

I'll start by building a test.

require 'minitest'
require 'minitest/autorun'
require 'minitest/pride'
require '../flatten'

class FlattenTest < Minitest::Test

  def test_combine_nested_arrays
    all = [1, 1, 2, 3, 4, 5]
    start_array = [1, [1,2],[3,[4,5]]]

    assert_equal all, CustomArray.new.combine_nested_arrays(start_array)
  end

I'm always skeptical of tests that run correctly the first time, so I prefer to run each test, expecting it to fail, before I proceed. 

Now it's time to start building the method. 

My first thought is that I'll need to iterate through each nested array and flatten it before proceeding to the next nested array.

Let's set up the class file.

  require 'pry'

  class CustomFlattenMethod
    def need_a_method
    end
  end

The most efficient way I can think to do this would be to pull the data out of the nested array and shovel it into another array. 

I'll call the flatten method `combine_nested_arrays`.

The Method

I'll walk through it step-by-step below. 

  attr_reader :all

  def combine_nested_arrays(arr, all=[])
    arr.each do |item|
      if item.class != Array
        all << item
      else
        combine_nested_arrays(item, all)
      end
    end
    all
  end

I set the variable `all` to default to an empty array. That way the method will be able to receive one or two variables, both arrays. One to flatten and another (the default `all`) to push our data into. 

  def combine_nested_arrays(arr, all=[])

Then we want to iterate through the array containing the nested arrays and pull out the data from each nested array.

  arr.each do |item|

However, what happens if one of the items in the array isn't an array?

For example, what if our array looked like this:

> [2, [1, 3], [5, [7, 9]]]

The first number, 2, isn't an array, it's just an integer. I'll set up an if/then statement to manage this situation. 

  arr.each do |item|
    if item.class != Array
      all << item
    else
      combine_nested_arrays(item, all)
    end
  end

Now if the item being altered within our iteration isn't an array, it will automatically be shoveled into our new array, `all`. It doesn't matter if it's an integer, symbol or string.

Recursive Magic

If the item is an array, magic happens. 

Not really, but we do recursively solve the problem. An array is sent back into our method, `combine_nested_arrays`. 

A nested array will be sent back through the method until the item being item in the iteration is no longer an array. 

If the first item in the original array was an array, the parameter `all` will continue to be it's default `all = []` when it's sent through the method again.

However, if the first item is not an array, and `all` is no longer an empty array, that array will be passed into the method along with `arr`.

More Tests

Because I'm a fan of tests, I wrote some more, along with a few edge cases, to confirm my assumptions were correct. 

Below is my full test suite. 

  require 'minitest'
  require 'minitest/autorun'
  require 'minitest/pride'
  require '../flatten'

  class FlattenTest < Minitest::Test

    def test_combine_nested_arrays
      all = [1, 1, 2, 3, 4, 5]
      start_array = [1, [1,2],[3,[4,5]]]

      assert_equal all, CustomArray.new.combine_nested_arrays(start_array)
    end

    def test_combine_nested_arrays_start_with_array
      all = [1, 2, 3, 4, 5]
      start_array = [[1,2],[3,[4,5]]]

      assert_equal all, CustomArray.new.combine_nested_arrays(start_array)
    end

    def test_combine_nested_arrays_start_with_array_nested_nested
      all = [1, 2, 3, 4, 3, 4, 5]
      start_array = [[1, 2, [3, 4]],[3,[4,5]]]

      assert_equal all, CustomArray.new.combine_nested_arrays(start_array)
    end

    def test_combine_nested_arrays_differet_type_data
      all = [1, "2", 3, 4, 3, 4, 5]
      start_array = [[1, "2", [3, 4]],[3,[4,5]]]

      assert_equal all, CustomArray.new.combine_nested_arrays(start_array)
    end

  end

Want to play with the code? View this repository on Github.

Recursion + Factorials

Quick shoutout to Natasha the Robot for her excellent writeup.

“Recursion is one of the most elegant things I don’t fully understand.
”

Recursion is beautiful. It's a bit like the movie Inception, in which everyone is in a dream within a dream.

In other words, a recursive method calls itself with new variables and continues to do so until the problem is solved, the method is told to break or your computer crashes. 

It's important to note that while a loop also continues to do something until it's forced to stop, loops are iterators and are not recursive in nature. 

Factorials

One of the problems best solved through a recursive method is finding the factorial of a number, which is denoted as the number, followed by an exclamation point (e.g. 5!). 

Factorial Iteration vs. Recursion

When I first approached the problem, I kept fighting the urge to iterate over the numbers. I blame Ruby's excellent flexibility. 

While you can find the factorial of a number, it's more elegantly coded as a recursive method. 

Nevertheless, here's an example of how you could iterate to find the factorial of a number:

You can read more about the #inject method in the Ruby docs.

 

Potential Problems

Negative numbers

Factorials of negative numbers are undefined. (I'm not a mathematician, but you can read more about there here.)

When I create a recursive method that takes input from the user, I'll have to make sure they submit a positive integer or natural number (in this case, I'm including zero as a natural number). 

The iteration currently doesn't account for this. It simply returns nil.

ZERO

The factorial of zero is one (0! = 1). If that's confusing to you, as it was to me, here's a brief explanation. 

1! = 1

2! = 2

3! = 6

4! = 24

If you're thinking, "Well, duh, get to the point," bear with me. 

Let's take a different approach. 

3! = 4!/4

In other words, 3! = 24/4, which can be further simplified to 3! = 6. 

OK, awesome. Let's do the rest.

2! = 3!/3 = 2

1! = 2!/2 = 1

Here's the kicker:

0! = 1!/1 = 1

Neat, huh? So, if the user inputs zero, I'll have to ensure the method returns one. The iteration below doesn't account for this.

Getting Started

I wrote some pseudocode of what I wanted to accomplish before I started coding. 

START program

GET input from user, convert string to integer

IF input == 0, RETURN 1

LOOP

IF input < 0, ask user for another input

END LOOP

RETURN factorial of input

END program

User prompt method

I created a simple method to add "=> " in front of any message. It will allow the user to more easily see messages and prevent me from having a hundred `puts` in my program. 

Welcome to Factorial!

I started the program off with a simple welcome message and asked the user to input a positive integer. 

User Input + Verification

I had to define the variable outside of the loop, so I set `user_input` to zero. 

When the user inputs a number, I convert it to an integer and check if it's a number greater than zero using the `is_valid?` method. 

If the number is negative, `is_valid?` returns a false and the loop tells the user it's not a valid number. 

stack level too deep

If you allowed the user to input a negative number using this recursive method, it wouldn't return nil. 

Instead, it would return an error: stack level too deep (SystemStackError). 

Though it returns the error within a second, the computer can't process the amount of information you've put on top of the memory stack.

Basically, you've asked it to compute too much information and it's politely saying no. 

Recursive Method

And now the fun part. First, the `factorial` method determines if `user_input` is equal to zero. If it is, it returns a one. 

If it's not, it begins recursively problem-solving. 

As you can see above, the recursive method takes a number and multiplies it by the recursive method minus one. 

Visualizing Recursion

Returning the factorial

The final step is to let the user know the factorial of the value they inputed. 

The Full Program

See room for improvement? You can grab this factorial program on GitHub.

Or, shoot me an email. I'd love your feedback!