The Crystal Programming Language Forum

Flattened array to multidimensional array

hi everyone !! i hope you are doing well …

so i have a problem i am trying to solve … i have a flattened array i am trying to turn into a non-flattened array and am having a hard time declaring the type for the array and returning a legitimate value …

so let’s imagine i have a flattened array like this ::

[“1”, “2”, “(”, “3”, “4”, “)”, “5”]

what i am hoping to return is an array that looks like this ::

[“1”, “2”, [ “3”, “4”], “5”]

it may honestly be just a brain problem, but i am having the hardest time “pushing” to the new array that is multidimensional – i keep getting type errors … for example ::

Error: no overload matches ‘Array(Array(Array(Int32) | Int32) | Array(Int32) | Int32)#push’ with type Array(Array(Array(Int32) | Int32) | Array(Int32) | Int32)

to back up a little, i create a temporary array and store the new values in there … when i get to the point of trying to push to the new array – i always get the above overload error …

what confuses me more is i when i peek at the object values and type right before the array.push, it sure seems legitimate to me, but i honestly do not know as this is day 10 for me with crystal …

current list: [1, 2] : Array(Array(Array(Int32) | Int32) | Array(Int32) | Int32)
nested list: [3, 4] : Array(Array(Array(Int32) | Int32) | Array(Int32) | Int32)

again, the goal at this phase is to push “nested” onto “current”, so the result would look like ::

[1, 2, [3, 4]]

any ideas on what i am doing wrong ?? any help you all can offer would be greatly appreciated … this isn’t my 1st strongly typed language, but my 1st go with crystal for sure and i feel like i am so close to making it work …

thanks so much for any help you can give me … it is greatly appreciated … again, my just be my brain and i am approaching it wrong … but i can’t get past this point for the life of me …

thanks !!

What’s the expected output of this input:

["1", "(", "2", "(", "3", "4", ")", "5", ")"]

In any case, you need to define a recursive type. Here’s one solution:

alias RecArray = String | Array(RecArray)

def unflatten(array)
  result = [] of RecArray
  stack = [result]
  array.each do |element|
    case element
    when "("
      stack << [] of RecArray
    when ")"
      new_array = stack.pop
      stack.last << new_array
    else
      stack.last << element
    end
  end
  result
end

input = ["1", "(", "2", "(", "3", "4", ")", "5", ")"]
p unflatten(input)
1 Like

this is exactly what i was looking for … i had no idea an alias could reference itself … thanks for the help !!

Cool!

Just note that such recursive types have some bugs and I’d personally like to remove them from the language.

However, you can also do it like this:

struct Group
  def initialize
    @members = [] of String | Group
  end

  def <<(element : String | Group)
    @members << element
  end
end

def unflatten(array)
  result = Group.new
  stack = [result]
  array.each do |element|
    case element
    when "("
      stack << Group.new
    when ")"
      new_array = stack.pop
      stack.last << new_array
    else
      stack.last << element
    end
  end
  result
end

input = ["1", "(", "2", "(", "3", "4", ")", "5", ")"]
p unflatten(input)
2 Likes

thanks again @asterite

i am still trying to wrap my head around how is it the code appears to be only initializing the result var, but that same result var is returned with desired values, but yet with no obvious direct assignment statements (i.e. result = <some-value>) …

i get that the stack var is initialized with the result var – but since it appears the stack var is the one with all the assignment/append statements – i just would have assumed that would be the var that was returned …

anyway – maybe a few more hours of looking at the code will help :slight_smile:

on a side note :: without starting any flame wars – why do you prefer not having recursive types ?? they seem quite handy – but i can see where the struct is a more straight forward impl …

thanks again

i think i finally got it !!

result is the last element in the stack array … you use the same stack var as a “temp var” for new () combinations, and when you see a closing ) – you pop that “temp var” and then << to the last (result) element …

that means all that << assignment is in fact being applied to the result var …