1

I'm looking for a better way to do this:

I have a map array of locations, e.g.

location = [1,1,1]
@map[location] = Tile.new

I want to find the surrounding tiles. Right now I've made the following function:

def get_surroundings(location, surroundings)
  range = (-1..1).to_a
  range.product(range, range) do |offset|
    surroundings.push(@map[location.map.with_index do |coord, index|
      coord + offset[index]
    end]).compact!
  end
end

It works just fine, but:

  • I can barely figure out what it does and I wrote it.
  • I especially don't like offset[index].

I figure there most be something like location.offset(other_array). I could make it, but it would be slow.

4
  • 1
    Too many things are unexplained. What is a map array? What is @map? What is a tile? What does get_surroundings do? Commented May 3, 2014 at 20:36
  • map array is an array of "tiles". tiles is an object, doesnt matter for this purpose. what does matter is location which holds the x, y, and z coordinates of a location in a "map". get_surroundings gets the surrounding tiles. Commented May 3, 2014 at 20:44
  • 1
    @sawa think on that as a chess board. A tile have the value white or black, and the map is all positions. But this is a 3D chessboard. Commented May 3, 2014 at 20:46
  • @JackG I updated my question, I found a bug on the - coord to eliminate the self place. I was subtracting it on the wrong place. I think. Please take a look now if you want. Commented May 3, 2014 at 23:10

3 Answers 3

3

For one, don’t pass in an array to add the elements to, instead just return the correct one. Mutating your arguments just makes everything harder to reason about later. Things also get much easier to read if we separate each step into smaller, named methods so we can put a semantic name to each part:

def offset_location location, offset
  location.zip(offset).map { |a, b| a + b }
end

def surrounding_coordinates location
  offset_values = [-1, 0, 1]
  offsets = offset_values.product(offset_values, offset_values)
  offsets.map do |offset|
    offset_location(location, offset)
  end
end

def surrounding_tiles location
  @map.values_at(surrounding_coordinates(location)).compact
end
Sign up to request clarification or add additional context in comments.

2 Comments

why does surround_coordinates return 504 arrays?
@JackG Whoops. Those are mostly duplicates, and it was otherwise the correct list. I’ve updated my answer.
2

We define a Location class, which is simply a Struct with a coord member and a surroundings method. The surroundings method will return all fields adjacent to coord (either orthogonally or diagonally).

# Structs are simply collections of member fields in an object.
class Location < Struct.new(:coord)

  def surroundings

    range = (-1..1).to_a  # This is the same as [-1, 0, 1].

    # By combining the above 'range' with itself three times, we get all
    # possible 3-tuples of -1, 0 and 1 (i.e. the 3-power set of 'range').
    # We then iterate over all these 3-tuples, producing a new array of
    # 3-tuples (which are the neighbours to our 'coord').

    range.product(range, range).map do |offset|
      # One example of offset here is "[-1, 0, 1]".

      # 'transpose' operates on an array of arrays (which can be seen as
      # a two-dimensional matrix of values), and flips rows by columns.
      # For example, this turns [ [-1,1,-1], [0,0,1] ] into [ [-1,0], [1,0], [-1,1] ]
      # In this case, it will pair every coordinate of this location with the
      # corresponding coordinate of the target location (the 'offset').
      #
      # The 'reduce' call simply adds up both values in 'x'.

      [coord, offset].transpose.map {|x| x.reduce(:+)}

      # Effectively, we just did a vector addition of 'coord' and 'offset'.

    end - coord  # We do not include 'coord' in the result.

    # By not including 'coord', we assume that a given location does not 'surround'
    # itself.  This is a matter of definition.

  end
end

>  Location.new([5,5,5]).surroundings
 => [[4, 4, 4], [4, 4, 5], [4, 4, 6], [4, 5, 4], [4, 5, 5], [4, 5, 6], [4, 6, 4], [4, 6, 5], [4, 6, 6], [5, 4, 4], [5, 4, 5], [5, 4, 6], [5, 5, 4], [5, 5, 5], [5, 5, 6], [5, 6, 4], [5, 6, 5], [5, 6, 6], [6, 4, 4], [6, 4, 5], [6, 4, 6], [6, 5, 4], [6, 5, 5], [6, 5, 6], [6, 6, 4], [6, 6, 5], [6, 6, 6]] 

I took care to remove the coord itself from the surroundings. If this is not what you want, simply leave out the - coord statement.

Then, if you need all objects from your map, you can simply index @map with the positions this method gives you:

@map.find_all {|coord| location.surroundings}

5 Comments

i like this answer, because it works well, and well with the code i currently i have, but it doesn't really make anything clearer.
@Sigi there is it, please let me know if is not clear
@fotanus I took the liberty to rewrite it for clarity. I hope you like it that way.
@JackG See if the annotations help you better understand this solution. Basically it's a vector addition of the location and all the 26 target locations around it.
@Sigi Yes, I like it, thank you very much. You express yourself way better than I do, I need to learn that.
0

[Edit: I see I misunderstood the question. I answered the question: "given a set integer-valued coordinates in 3-dimensional space, find all integer-valued coordinates that are each a neighbor of at least one coordinate in the set" (with "neighbor" suitably defined). My solution still works (by setting my_map => [location]), but it could be simplified to:

def neighbors(location)
  locs = location.map { |x| [*(x-1..x+1)] }
  locs.shift.product(*locs) - [location]
end  

I will leave my answer as is, should any reader be interested in the more general question.]

This is how I would do it.

Code

def neighbors(my_map)
  my_map.map do |l,_|
    locs = location.map { |x| [*(x-1..x+1)] }
    locs.shift.product(*locs)
  end.reduce(:|) - my_map.keys
end

Example

my_map = { [1,2,3]=>"123", [2,3,2]=>"232", [1,1,2]=>"112" }
neighbors(my_map)
  #=> [[0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2, 2], [0, 2, 3], [0, 2, 4],
  #    [0, 3, 2], [0, 3, 3], [0, 3, 4], [1, 1, 3], [1, 1, 4], [1, 2, 2],
  #    [1, 2, 4], [1, 3, 2], [1, 3, 3], [1, 3, 4], [2, 1, 2], [2, 1, 3],
  #    [2, 1, 4], [2, 2, 2], [2, 2, 3], [2, 2, 4], [2, 3, 3], [2, 3, 4],
  #    [1, 2, 1], [1, 3, 1], [1, 4, 1], [1, 4, 2], [1, 4, 3], [2, 2, 1],
  #    [2, 3, 1], [2, 4, 1], [2, 4, 2], [2, 4, 3], [3, 2, 1], [3, 2, 2],
  #    [3, 2, 3], [3, 3, 1], [3, 3, 2], [3, 3, 3], [3, 4, 1], [3, 4, 2],
  #    [3, 4, 3], [0, 0, 1], [0, 0, 2], [0, 0, 3], [0, 1, 1], [0, 2, 1],
  #    [1, 0, 1], [1, 0, 2], [1, 0, 3], [1, 1, 1], [2, 0, 1], [2, 0, 2],
  #    [2, 0, 3], [2, 1, 1]]

The three keys of my_map arr found to have a total of 56 unique neighbors (out of a possible total of 3**3 - 3 = 78, the '-3' to avoid counting the elements of my_map).

Explanation

Assume that my_map is as in the example above. (The hash values I gave are arbitrary.)

We will map each of the three key/value pairs of my_map into an array of neighboring cells, take the union of those arrays and lastly remove the hash keys from the union.

The first value map passes into its block is:

[[1,2,3], "123"]

Normally each element of this array (corresponding to the key and value of the hash element) would be represented by a block variable, but as we will not be using the value ("123"), I've replaced its variable with an underscore. The key, [1,2,3], is assigned to the block variable l.

Next we have

locs = location.map { |x| [*(x-1..x+1)] }
  #=> [1,2,3].map { |x| [*(x-1..x+1)] }
  #=> [[0, 1, 2], [1, 2, 3], [2, 3, 4]] 

then

a = locs.shift #=> [0, 1, 2]

so now

locs #=> [[1, 2, 3], [2, 3, 4]]

meaning that [1,2,3]'s neighbors are:

b = a.product(*locs)
  #=>  [0, 1, 2].product([1, 2, 3], [2, 3, 4])
  #=> [[0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2, 2], [0, 2, 3], [0, 2, 4],
  #    [0, 3, 2], [0, 3, 3], [0, 3, 4], [1, 1, 2], [1, 1, 3], [1, 1, 4],
  #    [1, 2, 2], [1, 2, 3], [1, 2, 4], [1, 3, 2], [1, 3, 3], [1, 3, 4],
  #    [2, 1, 2], [2, 1, 3], [2, 1, 4], [2, 2, 2], [2, 2, 3], [2, 2, 4],
  #    [2, 3, 2], [2, 3, 3], [2, 3, 4]]

Notice that [1,2,3] is in this array, though is not a neighbor of itself. I'll remove it at the end. (The other two elements of my_map are also in this array, and therefore need to be remove, but there's no point doing that now, because both of the other elements of my_map will also have all there elements in their corresponding arrays.)

We repeat this for each of the other two elements of my_map, obtaining arrays that I'll denote c and d.

We want the union of these three arrays:

(b | c | d)

which will eliminate duplicates (and preserve order). We do this using Enumerable#reduce and Array#|:

e = [b,c,d].reduce(:|)

Lastly, we remove the elements in my_map using Array#-.

e - my_map.keys

Efficiency

If my_map were large, it probably would be more efficient to convert each array of 27 neighboring elements to a set before taking their union.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.