Overwriting one Ruby array or arrays with another

Ruby
1

Hi

Hoping someone can give me some direction with regards to overwriting
one Ruby array of arrays with the contents of another.

As an example I have an array of arrays …

[[1, 1, “X”], [1, 2, “X”], [1, 3, “X”], [2, 1, “X”], [2, 2, “X”], [2, 3,
“X”], [3, 1, “X”], [3, 2, “X”], [3, 3, “X”]]

The first two values of the array represent x, y coordinates to build a
3 x 3 grid.

I have another array of arrays …

[[1, 1, “O”], [2, 1, “O”], [2, 2, “O”], [2, 3, “O”], [3, 3, “O”]]

… which I’d like to merge/overwrite/whatever based ONLY on the x, y
coordinates which will produce the final array (still a 3 x 3 grid) …

[[1, 1, “O”], [1, 2, “X”], [1, 3, “X”], [2, 1, “O”], [2, 2, “O”], [2, 3,
“O”], [3, 1, “X”], [3, 2, “X”], [3, 3, “O”]]

This is just an example and my project will be working with grids that
may be as large as 50 x 100 and the array of arrays that will overwrite
might have 1000+ items.

Can anyone point me in the right direction as to what would be the most
efficient way of achieving this?

Many thanks

Craig

2

Can you change your underlying data structure? Most efficient would be
to let the data be indexed by the (x,y) coordinates (either using a
two dimensional array, or a hash of {[x, y] => value}). If you have to
keep the list of [[x, y, value]] representation, you could run a merge
sort on the two lists, and apply the overlay if you hit cells with
equal x and y values. This assumes that both lists are sorted, of
course.

martin

3

Thanks for the reply

I gave a fairly basic example so that I could explain my needs. Perhaps
a little too basic. I’m also very new to Ruby.

Going forward the array of arrays may hold information such as …

[1, 1, “X”, “20120502”]

… so that I have a grid that will display an “X” at x,y coordinates
1,1 and also hold some metadata such as “20120502” which in this case
would be a date.

Ultimately I will be creating an HTML grid of variable size that will
house an “X” or “O”. The date would be metadata that I’m hoping to
display when you hover over a box when viewing the grid/graph in a
browser.

If I can produce a hash of {[x, y] => xxxxx } which holds the values “X”
and “20120501” that would be OK with me.

Would the code for such a hash be something like this …

{[1, 1] => [“X”, “20120501”]}
{[1, 2] => [“O”, “20120502”]}

… and if so how would I overwrite one hash with the other?

Thanks again

Craig

4

On Tue, May 1, 2012 at 8:27 PM, Craig L. [email protected] wrote:

If I can produce a hash of {[x, y] => xxxxx } which holds the values “X”
and “20120501” that would be OK with me.

Would the code for such a hash be something like this …

{[1, 1] => [“X”, “20120501”]}
{[1, 2] => [“O”, “20120502”]}

… and if so how would I overwrite one hash with the other?

The built-in hash.update method will do this:

ruby-1.9.2-p0 > a = {[1, 1] => “x”, [1, 2] => “x”, [1, 3] => “x”, [2,
1] => “x”, [2, 3] => “x”, [3, 3] => “x”}
=> {[1, 1]=>“x”, [1, 2]=>“x”, [1, 3]=>“x”, [2, 1]=>“x”, [2, 3]=>“x”,
[3, 3]=>“x”}

ruby-1.9.2-p0 > b = {[1, 1] => “o”, [2, 2] => “o”, [3, 3] => “o”}
=> {[1, 1]=>“o”, [2, 2]=>“o”, [3, 3]=>“o”}

ruby-1.9.2-p0 > a.update(b)
=> {[1, 1]=>“o”, [1, 2]=>“x”, [1, 3]=>“x”, [2, 1]=>“x”, [2, 3]=>“x”,
[3, 3]=>“o”, [2, 2]=>“o”}

ruby-1.9.2-p0 > a
=> {[1, 1]=>“o”, [1, 2]=>“x”, [1, 3]=>“x”, [2, 1]=>“x”, [2, 3]=>“x”,
[3, 3]=>“o”, [2, 2]=>“o”}

Note that this will also fill in "o"s in cells that did not have an “x”
in them.

martin

5

Perfect …

irb(main):001:0> a = { [1, 1] => [“X”, “20120501”], [1, 2] => [“X”,
“20120502”>
=> {[1, 1]=>[“X”, “20120501”], [1, 2]=>[“X”, “20120502”]}
irb(main):002:0> b = { [1, 2] => [“O”, “20120403”] }
=> {[1, 2]=>[“O”, “20120403”]}
irb(main):003:0> a.update(b)
=> {[1, 1]=>[“X”, “20120501”], [1, 2]=>[“O”, “20120403”]}
irb(main):004:0> a
=> {[1, 1]=>[“X”, “20120501”], [1, 2]=>[“O”, “20120403”]}
irb(main):005:0>

Thanks for your help Martin - much appreciated and so easy in the end. I
guess that’s why people love Ruby.

Cheers

Craig

6

Martin

Just as a matter of interest if I was forced to continue using an array
of arrays such as [1, 1, “X”, “20120502”] what would be the most
efficient way of overwriting the array with another array as described
in my second post (the only reason I ask is that my code at the moment
is spitting out an array of arrays and I’m going to have to work out how
to spit out the hashes in an ordered manner to use the more efficient
has method you’ve described). Can I use a similar update method as
you’ve done with hashes?

Thanks

Craig

7

On Tue, May 1, 2012 at 9:14 PM, Craig L. [email protected] wrote:

Martin

Just as a matter of interest if I was forced to continue using an array
of arrays such as [1, 1, “X”, “20120502”] what would be the most
efficient way of overwriting the array with another array as described
in my second post (the only reason I ask is that my code at the moment
is spitting out an array of arrays and I’m going to have to work out how
to spit out the hashes in an ordered manner to use the more efficient
has method you’ve described). Can I use a similar update method as
you’ve done with hashes?

No, it’s a bit more work if you want to use arrays that way, since you
don’t have a trivial “find the cell with coordinates x, y” method.
Assuming that arrays a and b are sorted first by x and then by y, you
could write a helper method that did a binary search on array a (as a
side note, ruby does implement < and > for arrays, and the elements
are compared pairwise starting from the first one), and then say

def find_in_grid(array, x, y)

return the index of the cell starting [x, y, …] if it is found,

otherwise nil
end

b.each do |cell|
index = find_in_grid(a, cell[0], cell[1])
if index
a[index] = cell
end
end

find_in_grid can be implemented using a binary search, or you could
maintain some sort of (e.g. pointers to the start of each grid row) if
you want to update it frequently. Also, note that if there is an (x,
y) in b that is not in a, inserting it will be an additional problem
since you have to maintain the sorted order and inserting into the
middle of an array is relatively expensive. Of course, all this might
just be premature optimisation - if the grid update is not slowing
your code down, do the simplest thing that could work, which is
convert a and b into hashes, update, and then convert back into an
array. (It might even be the fastest thing to do, if you have a dense
grid and a lot of updates).

To convert an array to a hash:

hash = {}
a.each do |cell|
x, y, *rest = cell
hash[[x, y]] = rest
end

and back:

hash.keys.sort.map {|k| [k] + hash[k]}

Where sorting the keys of the hash ensures that your array is spat out
in the proper order.

martin

8

Can anyone help me with ordering a hash that’s being converted to an
array.

As above I’ve followed Martin’s suggestion and converted two array’s
into hashes, merged the hashes and I’m attempting to convert them back
into an array. Current hash looks like this …

[[1, 3]=>[“X”,“20120609”], [3, 3]=>[“X”,“20120610”], [2,
1]=>[“X”,“20120611”], [1, 2]=>[“X”,“20120612”], [3,
2]=>[“X”,“20120613”], [3, 1]=>[“X”,“20120614”], [1,
3]=>[“X”,“20120615”], [2, 1]=>[“X”,“20120616”], [2,
2]=>[“X”,“20120617”]]

As you can see the x, y coordinates are in a random order and I need to
convert the above hash back into an array that looks like this …

[[1, 3, “X”,“20120609”], [2, 3, “X”,“20120610”], [3, 3, “X”,“20120611”],
[1, 2, “X”,“20120612”], [2, 2, “X”,“20120613”], [3, 2, “X”,“20120614”],
[1, 1, “X”,“20120615”], [2, 1, “X”,“20120616”], [3, 1, “X”,“20120617”]]

Basically I need to order the x coordinate first in ascending order and
the y coordinate second in descending order.

The command I’ve mucked around with that Martin posted above is …

c = hash1.keys.sort.map {|k| [k[0],k[1]] + hash1[k]}

… but that’s giving me y coordinates ordered first in ascending order
and x coordinates ordered second in ascending order like this …

[[1, 1, “X”,“20120609”], [1, 2, “X”,“20120610”], [1, 3, “X”,“20120611”],
[2, 1, “X”,“20120612”], [2, 2, “X”,“20120613”], [2, 3, “X”,“20120614”],
[3, 1, “X”,“20120615”], [3, 2, “X”,“20120616”], [3, 3, “X”,“20120617”]]

Has anyone got any suggestions on how I can achieve an ordered array
that looks like this …

[[1, 3, “X”,“20120609”], [2, 3, “X”,“20120610”], [3, 3, “X”,“20120611”],
[1, 2, “X”,“20120612”], [2, 2, “X”,“20120613”], [3, 2, “X”,“20120614”],
[1, 1, “X”,“20120615”], [2, 1, “X”,“20120616”], [3, 1, “X”,“20120617”]]

Many thanks

Craig

9

Thanks for the detailed response Martin. Really appreciated.

I’ll see what I can do to change my code to create hashes. I think it
may be the smarter and more efficient way to go.

Cheers

Craig

10

Thanks Jan

Will start new post next time.

I had to modify your code a bit to get what I wanted …

sorted_keys = hash1.keys.sort do |(x1, y1), (x2, y2)|
y_comparison = y2 <=> y1
if y_comparison != 0
y_comparison
else
x1 <=> x2
end
end

pp sorted_keys

… and it produces an array in the order that I want it but it only
contains the keys (i.e. [1,1]). How do I include the [“X”,“20120617”] so
that I get [1, 1, “X”, “20120617”] in the array? I just can’t figure out
how to tack on the values associated with the keys.

Thanks

Craig

11

Hi,

I think it’s generally better to open a new thread if you’ve got a new
question. Then we don’t have to sort out the old postings.

Craig L. wrote in post #1064927:

Has anyone got any suggestions on how I can achieve an ordered array
that looks like this …

[[1, 3, “X”,“20120609”], [2, 3, “X”,“20120610”], [3, 3, “X”,“20120611”],
[1, 2, “X”,“20120612”], [2, 2, “X”,“20120613”], [3, 2, “X”,“20120614”],
[1, 1, “X”,“20120615”], [2, 1, “X”,“20120616”], [3, 1, “X”,“20120617”]]

Many thanks

Craig

The “sort” method lets you supply a block. The elements will be passed
to the block two at a time and compared according to the return value
(which is supposed to be either -1, 0 or 1, following the logic of the
<=> method).

If this case, you first compare the x coordinates. If they’re different,
then the result of the comparison is the overall result. If they’re the
same, you compare the values by the y coordinates (in reverse order):

#---------------

hash1 = {
[1, 3] => [“X”,“20120609”],
[3, 3] => [“X”,“20120610”],
[2, 1] => [“X”,“20120611”],
[1, 2] => [“X”,“20120612”],
[3, 2] => [“X”,“20120613”],
[3, 1] => [“X”,“20120614”],
[1, 3] => [“X”,“20120615”],
[2, 1] => [“X”,“20120616”],
[2, 2] => [“X”,“20120617”]
}
sorted_keys = hash1.keys.sort do |(x1, y1), (x2, y2)|
x_comparison = x1 <=> x2
if x_comparison != 0
x_comparison
else
y2 <=> y1 # note the reverse order
end
end

p sorted_keys

#---------------

You may also shorten the block content to

[x1 <=> x2, y2 <=> y1].find 0, &:nonzero?

This will select the first of the two comparisons which is not 0. Or it
returns 0, if there isn’t any.

12

Craig L. wrote in post #1064944:

… and it produces an array in the order that I want it but it only
contains the keys (i.e. [1,1]). How do I include the [“X”,“20120617”] so
that I get [1, 1, “X”, “20120617”] in the array? I just can’t figure out
how to tack on the values associated with the keys.

Well, you’ve already done this with Martin’s approach. The only
difference is that “sort” has a block now, so you should probably do the
key sorting and the mapping separately:

#------------------------------
sorted_keys = hash1.keys.sort do |(x1, y1), (x2, y2)|
y_comparison = y2 <=> y1
if y_comparison != 0
y_comparison
else
x1 <=> x2
end
end
result = sorted_keys.map {|key| key + hash1[key]}
#------------------------------

But I agree with Robert that you should use specific objects instead of
hashes. The problem with your hashes is that their structure is neither
documented (unless you write a comment) nor enforced. You may accidently
put wrong values into the hashes and won’t even notice.

13

On Wed, May 2, 2012 at 5:27 AM, Craig L. [email protected] wrote:

1,1 and also hold some metadata such as “20120502” which in this case
Would the code for such a hash be something like this …

{[1, 1] => [“X”, “20120501”]}
{[1, 2] => [“O”, “20120502”]}

… and if so how would I overwrite one hash with the other?

Frankly, I’d take a different approach: from what we have seen you
have a grid, coordinates and node data. I’d rather model these as
separate classes, e.g.

Now you can do

g = Grid.new 10, 500
g[Coord(1,3)] = NodeData.new “foo”

g.replace(
Coord(1,2) => NodeData.new(“hello”),
Coord(2,34) => nil,
)

etc.

Then, if you find you need to change the internal representation to be
more efficient your algorithms are not affected since they just use
the same API of Grid.

Kind regards

robert

14

Thanks Robert and Jan - appreciate the help.

I’ll have a look at the grid option. Looks like it might serve my
purposes better than hashes.

Cheers

Craig