Recursive Arrays

Foreword

I feel a certain level of confidence declaring that every programmer has been in the situation where he/she has 10+ tabs open trying troubleshooting a problem and finally concludes, “There must be an easier way.” Or, if you’ve been ‘in the zone’ for long enough, you might start wondering what exactly got you in this troubleshooting hell to begin with.

In this post, I will share what I learned from one such experience.

Context and Problem

I was writing an automatic schedule-maker in Ruby. create_groups is a method that, takes an array of student names and returns an array of the students in a specified group sizes. The create_groups method also takes a parameter that allows you to specify a number of groups. The student groups should be randomized.

First, I defined the method create_groups, set up an array of grouped students that I can push groups into, and returned the value.

1
2
3
4
5
6
7
def create_groups(students, group_size, number_of_groups)
  groups = []  #=> store the groups of students in this array
  # Implement magic.
  groups  #=> Return groups
end
create_groups(students, 4, 20)
students = [.......] #=> This array contains 41 student names. Check my Github Gist linked below for the array I used in the completed program.

After considering several strategies, I decided that it would make the most sense sort the 40 students using what I dubbed the “card dealing method” — The first student goes to group 1, the second to group 2, the third to group 3, and so forth.

1
2
3
4
5
6
7
8
def create_groups(students, group_size, number_of_groups)
  groups = []
  normalized_list = normalize(students, group_size, number_of_groups)
  normalized_list.each_with_index do |name, i|
    # This part will sort students using the "card-dealing method"
  end
  groups
end

Since there are 20 groups of 4, I needed 80 students. On an abstract level, the number of students I need in order to sort (the “desired length”) is “# of groups” x “# of students per group”.

I decided to create another method which would normalize my list to this set amount.

The #normalize method will return an array of desired length by replicating the students a number of times, and then slicing out the desired number of students from the replicated array.

Here’s what I came up with at first:

1
2
3
4
5
6
7
8
9
10
11
12
def create_groups(students, group_size, number_of_groups)
  #...folded this code for now...
end

def normalize(list_to_norm, group_size, number_of_groups)
  desired_length = group_size*number_of_groups
  new_list = list_to_norm
  while new_list.length < desired_length
    new_list << list_to_norm
    new_list = new_list.flatten
  end
end

When I ran this given a student array though, I received the following error:

1
rb24:`flatten': tried to flatten recursive array (ArgumentError)

WAT? After many attempts at troubleshooting and searching the web for an answer, I decided to inspect what exactly I was trying to flatten.

1
2
3
4
5
6
def normalize(list_to_norm, group_size, number_of_groups)
  desired_length = group_size*number_of_groups
  new_list = list_to_norm
  new_list << list_to_norm
  puts new_list
end

The output was VERY telling. The ... line below is just a placeholder for names 4 through 40.

1
2
3
4
5
6
Name1
Name2
Name3
...
Name41
[...]

The clue was in the [...].

I then tried running new_list.object_id and list_to_norm.object_id and they turned out to be the same.

A-ha!

The [...] indicated that new_list is now a recursive array. More on recurive arrays here.

As it turns out, my problem was in the 2nd line of my normalize method.

1
new_list = list_to_norm

This line of code sets the new_list variable to point at the exact same object as the list_to_norm method. So later, when I called new_list << list_to_norm, I ended up pushing an Array object into itself. The image below

However, Ruby clearly didn’t like this, and I suspect that it has to do with the way Array.flatten works. At the very least, we can conclude that .flatten can only flatten two different Array objects.

So that’s what I learned in 40 minutes of head-banging against a figurative brick wall. I hope you learned something as well from this post!

Also, as promised, here is a link to my full gist.

Comments