Splitting an array into quads and putting them back together again.

C

CBlair1986

Hi all, I've got a question. A really quick, easy-to-answer question,
if I'm lucky ;)

I have an array of arrays:

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

I've already borrowed code from the Matrix class to select sub-arrays
of this array:

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

and I can easily rotate those, but now I'm not sure on how to put them
back together like so:

[a1][b1]
[a2][b2]

If anyone knows a good way to do this, it would be greatly appreciated.

Thanks again!
 
M

Martin DeMello

and I can easily rotate those, but now I'm not sure on how to put them
back together like so:

[a1][b1]
[a2][b2]

If anyone knows a good way to do this, it would be greatly appreciated.

require 'enumerator'

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

def /(other)
self + other
end
end

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

p (a1|b1)/(a2|b2)

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

p [a1, b1, a2, b2].shape(2)
 
C

Chris Blair

I don't mean to reply to myself, but I just realized that the way I
was rotating the array wasn't correct. But, I got it figured out, so
here it is:

class Array
# Returns a rotated( once, clockwise ) array derived from self
def rotate()
self.transpose.map{ |a| a.reverse }
end
end

I know, it's simple, but it might be useful.
 
M

Martin DeMello

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
 
C

CBlair1986

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:
<snip/>
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

Thank you for the in-depth explanation. It really helped me grasp what
you did. Honestly, I would never have thought about the problem as you
did, so I see I've got a lot more to learn. Thank you again!
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,900
Latest member
Nell636132

Latest Threads

Top