Flatten an array of arbitrarily nested arrays of integers into a flat array of integers. e.g. [[1,2,[3]],4] -> [1,2,3,4].
require 'minitest/autorun' | |
# This is not a production ready solution. Code doesn't explains itself it takes some time for the | |
# reader to reason about its execution under different cases. | |
# For a production ready solution I would think of using a stack and switch to an iterative solution | |
# rather than recursive.' | |
def flatten_array(arry) | |
return arry if arry.empty? | |
head, *tail = arry | |
if head.is_a?(Array) | |
flatten_array(head) + flatten_array(tail) | |
else | |
flatten_array(tail).prepend(head) | |
end | |
end | |
class FlattenTest < Minitest::Test | |
def test_flatten | |
assert_equal [], flatten_array([]) | |
assert_equal [1], flatten_array([1]) | |
assert_equal [1, 2], flatten_array([1, [2]]) | |
assert_equal [1, 2, 3], flatten_array([1, [2], [3]]) | |
assert_equal [1, 2, 3], flatten_array([1, [2, [3]]]) | |
assert_equal [1, 2, 3], flatten_array([[1], [2, [3]]]) | |
assert_equal [1, 2, 3], flatten_array([[[1]], [2, [3]]]) | |
assert_equal [1, 2, 3, 4, 5, 6, 7, 8, 9, 0], flatten_array([[[1, 2, 3]], [4, [5, 6]], 7, [[[[8]], 9]], 0]) | |
end | |
end |
# flatten an array of arbitrarily nested arrays of integers into a flat array of integers. e.g. [[1,2,[3]],4] -> [1,2,3,4]. | |
require 'minitest/autorun' | |
# This solution assumes thes existence of a collaborator | |
# which will parse the composite array and will return the values | |
def parse(array_tree) | |
multiple_levels = array_tree.any?{|x| x.is_a?(Array)} | |
if multiple_levels | |
Node.new(array_tree) | |
else | |
Leaf.new(array_tree) | |
end | |
end | |
class Node | |
attr_reader :children | |
def initialize(array_tree) | |
@values = array_tree.select {|x| x.is_a?(Integer)} | |
@children = array_tree.select {|x| x.is_a?(Array)}.map {|x| parse(x)} | |
end | |
def values | |
children.reduce(@values) { |acum, child| acum + child.values } | |
end | |
end | |
class Leaf | |
attr_reader :values | |
def initialize(values) | |
@values = values | |
end | |
end | |
class FlattenTest < Minitest::Test | |
def assert_same_elements(array1, array2) | |
assert array1 - array2 == [] | |
end | |
def test_parsing_array | |
assert_equal [], parse([]).values | |
assert_equal [1], parse([1]).values | |
assert_equal [1, 2], parse([1, 2]).values | |
assert_equal [], parse([[]]).values | |
assert_equal [1], parse([1, []]).values | |
assert_equal [1, 2, 3], parse([1, 2, [3]]).values | |
assert_equal [1, 2, 3, 4], parse([1, 2, [3, 4]]).values | |
assert_equal [1, 2, 3, 4, 5], parse([1, 2, [3, 4, [5]]]).values | |
assert_equal [1, 2, 3, 4, 5, 6], parse([1, 2, [3, 4], [5, 6]]).values | |
assert_equal [1, 2, 3, 4, 5, 6], parse([1, 2, [3, [4]], [5, 6]]).values | |
end | |
def test_flatten | |
assert_equal [], parse([]).values | |
assert_equal [1], parse([1]).values | |
assert_equal [1, 2], parse([1, 2]).values | |
assert_equal [], parse([[]]).values | |
assert_equal [], parse([[[]]]).values | |
assert_equal [1], parse([1]).values | |
assert_equal [1], parse([[1]]).values | |
assert_equal [1], parse([[[1]]]).values | |
assert_equal [1], parse([[[[1]]]]).values | |
assert_equal [1], parse([[[[[1]]]]]).values | |
assert_equal [1], parse([[[[[[1]]]]]]).values | |
assert_equal [1, 2], parse([1, 2]).values | |
assert_equal [1, 2], parse([[1, 2]]).values | |
assert_equal [1, 2], parse([[[1, 2]]]).values | |
assert_equal [1, 2], parse([[[[[[[1, 2]]]]]]]).values | |
# results return different order | |
assert_same_elements [1, 2], parse([1, [2]]).values | |
assert_same_elements [1, 2], parse([[1], 2]).values | |
assert_same_elements [1, 2], parse([[[1]], 2]).values | |
assert_same_elements [1, 2], parse([1, [2]]).values | |
assert_same_elements [1, 2, 3], parse([1, [2], [3]]).values | |
assert_same_elements [1, 2, 3], parse([1, [2, [3]]]).values | |
assert_same_elements [1, 2, 3], parse([[1], [2, [3]]]).values | |
assert_same_elements [1, 2, 3], parse([[[1]], [2, [3]]]).values | |
assert_same_elements [1, 2, 3, 4, 5, 6, 7, 8, 9, 0], parse([[[1, 2, 3]], [4, [5, 6]], 7, [[[[8]], 9]], 0]).values | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment