Skip to content

Instantly share code, notes, and snippets.

@delbetu

delbetu/flatten_array.rb

Last active Jun 24, 2019
Embed
What would you like to do?
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