Monday, April 16, 2007

Code quickie: How to interlace two arrays in ruby

Hrm, I'm not sure whether it's worth posting or not, but I was looking for a way to interlace two arrays in ruby. This is what I came up with originally, and it worked fine for a bit:
class Array
def interlace(other_array)
interlaced_array = []
self.each_with_index { |x,i| interlaced_array << x << other_array[i]}
return interlaced_array
end
end
This code has the problem that on arrays of different sizes, it'll either leave off the longer array's remaining elements or insert nils for the shorter array. This isn't a good default behavior. What we'd like is for the longer array, whichever one it is, to get its remaining elements tacked on the end of the interlaced array after the elements in the shorter array have run out.

I decided to do it recursively. I haven't written anything recursive since that post on Erlang.
class Array
# interlaces an array with another array. It dovetails the two arrays together.
#
# [1,2,3,4,5,6].interlace([7,8,9]) # => [1, 7, 2, 8, 3, 9, 4, 5, 6]
#
# [1,2,3].interlace([1,2,3,4,5]) # => [1, 1, 2, 2, 3, 3, 4, 5]
def interlace(other_array)
return other_array if self.empty?
return [self[0]] + other_array.interlace(self[1..-1])
end
end
Great, now it works on different sized arrays! What you'll notice is that unlike most recursions, this one "switch places" with the other array on every recursion with the call, other_array.interlace(self[1..-1]). It's the first time I've seen a recursion like this. It certainly simplifies the code immensely, since you don't have to check for which array is bigger or smaller. Note, however, that this only works because the method is public. The technique doesn't work for private recursion helpers.

While you don't get to use recursion all that often, I find that its solution is often pretty elegant compared to iteration. I think that it will be useful when we start to use more data structures that are more fractal in nature. Currently, we have lists and trees. Hrm, there might be some possibilities here. For now, we'll keep this short, and if I come up with anything on this front, I'll let ya'll know! Tip!

2 comments:

  1. ianxm9:39 AM

    that is damn sexy

    ReplyDelete
  2. Like ianxm wrote, that is damned sexy. Unfortunately, if you ever had to use it with large arrays, it will slow down quite a bit. I ended up writing this as a result:

    def interlace(other_array)
    if empty?
    other_array
    elsif length == other_array.length
    zip(other_array).flatten
    else
    l = [length, other_array.length].min
    (take(l).zip(other_array.take(l)) + drop(l) + other_array.drop(l)).flatten
    end
    end

    ReplyDelete