Skip to content

Instantly share code, notes, and snippets.

@Aerlinger
Last active January 25, 2017 20:53
Show Gist options
  • Save Aerlinger/d3859ebda4542239b6332d8cc21ef43c to your computer and use it in GitHub Desktop.
Save Aerlinger/d3859ebda4542239b6332d8cc21ef43c to your computer and use it in GitHub Desktop.
require "rspec"
##
# Recursively flattens a nested array by performing a in-order depth first traversal and reducing the found items into a single, flat
# array within the tail call.
def flatten(arr)
return [arr] unless arr.is_a? Array
# Note that the return value of `reduce` is the last call in the our recursive `flatten` function, so nested items are concatenated
# in order as they return up the call stack.
arr.reduce([]) { |concat, item| concat + flatten(item) }
end
RSpec.describe "Flattening a nested array" do
it "is valid for simple array" do
expect(flatten([[1]])).to eq([1])
end
it "is valid for empty array" do
expect(flatten([[]])).to eq([])
end
it "is valid for partitioned array" do
expect(flatten([[1], [2], [3], [4], [5]])).to eq([1, 2, 3, 4, 5])
end
it "is valid for array wrapped in array" do
expect(flatten([[1, 2, 3, 4, 5]])).to eq([1, 2, 3, 4, 5])
end
it "is valid for deeply nested empty array" do
expect(flatten([[[], [], [], [nil]]])).to eq([nil])
end
it "is valid for deeply nested inhomogeneous array" do
expect(flatten([[[], [{a: [1, [2]]}], ['a'], [nil]]])).to eq([{a: [1, [2]]}, 'a', nil])
end
it "is valid for a flat array" do
expect(flatten([1, 2, 3, 4])).to eq([1, 2, 3, 4])
end
end
## To run:
# `rspec flatten.rb`
## RSpec Output:
# .......
#
# Finished in 0.00317 seconds (files took 0.18773 seconds to load)
# 7 examples, 0 failures
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment