From: Martin DeMello <martindemello@...>
Date: 2006-11-16T21:37:57+09:00
Subject: Re: Splitting an array into quads and putting them back together again.

On 11/16/06, Chris Blair <cblair1986@gmail.com> wrote:
> >
> >
> Thanks! I don't quite understand the code, right now, but it does work
> exactly how I wanted it. Sorry for the delay in responding, I haven't had
> access to the internet for a little while.

Here's a quick explanation of how the code works:

Ruby's multidimensional arrays are actually arrays of arrays. So if you have

a1 = [[1,2],[5,6]]
b1 = [[3,4],[7,8]]
a2 = [[9,10],[13,14]]
b2 = [[11,12],[15,16]]

and you want

a = [[1,2,5,6],  [3,4,7,8], [9,10,13,14], [11,12,15,16]]

you need (i) a way to combine two submatrices side by side and (ii) a
way to combine them one on top of the other.

Let's start with side by side, defining the | operator so that

[[1, 2],
 [5, 6]] |
[[3, 4],
 [7, 8]] =

[[1, 2, 3, 4],
 [5, 6, 7, 8]]

To do that we need to walk over each row of both arrays, in parallel,
and combine the rows into one big row. The #zip method steps over two
enumerables in parallel, returning pairs of elements, so that

[a, b].zip([c,d]) #=>  [[a, c], [b, d]]

Let's take that for a spin:

irb(main):006:0> a = [[1, 2], [5, 6]].zip [[3, 4], [7, 8]]
=> [[[1, 2], [3, 4]], [[5, 6], [7, 8]]]

or, pretty-printing the result a bit:

irb(main):017:0> puts "[\n" + a.map {|i| i.inspect}.join("\n") + "\n]"
[
[[1, 2], [3, 4]]
[[5, 6], [7, 8]]
]

That's not bad - now all we need is a way to turn [[1,2], [3,4]] into
[[1, 2, 3, 4]], and repeat that for each row. #map is a method that
steps over an enumerable, applying its block to each element and
collecting the results in an array:

irb(main):018:0> [1,2,3,4].map {|i| 2**i}
=> [2, 4, 8, 16]

and Array#+ simply concatenates two arrays, so we can say

irb(main):019:0> a.map {|i| i[0] + i[1]}
=> [[1, 2, 3, 4], [5, 6, 7, 8]]

and there we are. One further refinement is that ruby supports a
certain amount of pattern matching, so since we know that the elements
of the array are themselves arrays containing a pair of elements, we
can take them apart in the block argument:

irb(main):020:0> a.map {|i, j| i + j }
=> [[1, 2, 3, 4], [5, 6, 7, 8]]

And there we have our | method:

class Array
   def |(other)
     self.zip(other).map {|a,b| a+b}
   end
end

The / method is even more trivial - to stack two arrays one on top of
the other, simply add them (in other words, we don't even need a /
method - it just looks cuter than + when used alongside | )

class Array
   def /(other)
     self + other
   end
end

This does indeed work as desired

 p (a1|b1)/(a2|b2) #=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12],
[13, 14, 15, 16]]

but it's a little tedious to have to combine things by hand. What we
want is an array of the four sub arrays, that we can group into twos
and fold into shape. This splits into three problems: group the
subarrays into pairs, combine each pair using |, and then combine the
2x4 arrays using /.

To solve the first, we make use of the enumerator library:

irb(main):021:0> require 'enumerator'
=> true
irb(main):022:0> (1..10).enum_slice(2)
=> #<Enumerable::Enumerator:0xb7cf3494>

The Enumerable::Enumerator object will yield up consecutive pairs when
you call an Enumerable method on it. To see exactly what it will
yield:

irb(main):024:0>  (1..10).enum_slice(2).to_a
=> [[1, 2], [3, 4], [5, 6], [7, 8], [9, 10]]

irb(main):078:0> a = [a1, b1, a2, b2]
=> [[[1, 2], [5, 6]], [[3, 4], [7, 8]], [[9, 10], [13, 14]], [[11,
12], [15, 16]]]

irb(main):079:0> pp a.enum_slice(2).to_a
[[[[1, 2], [5, 6]], [[3, 4], [7, 8]]],
 [[[9, 10], [13, 14]], [[11, 12], [15, 16]]]]

That's off to a good start - let's capture the enumerator in its own variable:

irb(main):080:0> b =  a.enum_slice(2)
=> #<Enumerable::Enumerator:0xb7ce5b78>

irb(main):081:0> b.to_a[0]
=> [[[1, 2], [5, 6]], [[3, 4], [7, 8]]]
irb(main):082:0> b.to_a[1]
=> [[[9, 10], [13, 14]], [[11, 12], [15, 16]]]

b thus consists of two elements, each in turn consisting of two
elements which are themselves 2x2 arrays (by way of illustration:

irb(main):039:0> %w(a1 b1 a2 b2).enum_slice(2).to_a
=> [["a1", "b1"], ["a2", "b2"]]
)

We want to change that to (a1|b1) / (a2|b2). As a first step, let's
aim for the intermediate result [(a1|b1), (a2|b2)]. This is simply a
mapping over b:

irb(main):086:0> c =  b.map {|i, j| i | j}
=> [[[1, 2, 3, 4], [5, 6, 7, 8]], [[9, 10, 11, 12], [13, 14, 15, 16]]]

and for the final step:

irb(main):087:0> c[0] / c[1]
=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]

Now what if we had a 3x3 matrix of 9 arrays? We'd have to say

c =  b.map {|i, j, k| i | j | k}
c[0] / c[1] / c[2]

And so on - what we need is a way to generalise the pattern

a[0] o a[1] o a[2] .. a[n], where o is any operator. Ruby calls this
"inject" (after Smalltalk):

irb(main):090:0> (1..10).inject {|accumulator, element|
"(#{accumulator} + #{element})"}
=> "(((((((((1 + 2) + 3) + 4) + 5) + 6) + 7) + 8) + 9) + 10)"

So:

irb(main):092:0> c = b.map {|row| row.inject {|a, e| a | e}}
=> [[[1, 2, 3, 4], [5, 6, 7, 8]], [[9, 10, 11, 12], [13, 14, 15, 16]]]

and

irb(main):093:0> d = c.inject {|a, e| a/e}
=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]

or, putting it all together:

 class Array
   def shape(cols)
     enum_slice(cols).map {|i| i.inject {|j, k| j|k}}.inject {|a, i| a/i}
   end
 end

irb(main):099:0> [a1, b1, a2, b2].shape(2)
=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]

and there we are.

martin