Find adjacents in bidimensional array

Question

I have a 2d array like this.

[
  ["+", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "+"], 
  ["|", "*", "*", " ", " ", "*", " ", " ", " ", " ", "*", "*", "*", "*", "*", "*", "*", "*", " ", "*", " ", "|"], 
  ["|", " ", "*", "*", "*", "*", " ", " ", " ", " ", "*", "*", " ", " ", "*", "*", " ", "*", " ", "*", " ", "|"], 
  ["|", "*", " ", "*", " ", " ", " ", " ", "*", " ", "*", " ", "*", "*", "*", " ", "*", "*", "*", " ", "*", "|"], 
  ["|", "*", "*", " ", " ", "*", " ", " ", "*", "*", "*", " ", "*", " ", "*", "*", " ", "*", "*", " ", " ", "|"], 
  ["|", "*", " ", " ", " ", "*", " ", "*", " ", " ", " ", "*", "*", "*", "*", "*", " ", " ", " ", "*", "*", "|"], 
  ["|", " ", " ", " ", " ", " ", "*", " ", "*", " ", " ", " ", "*", " ", " ", " ", " ", " ", "*", " ", " ", "|"], 
  ["|", "*", "*", " ", "*", "*", "*", " ", "*", " ", " ", "*", "*", "*", "*", " ", "*", " ", " ", "*", " ", "|"], 
  ["|", " ", "*", " ", "*", "*", "*", "*", " ", " ", " ", "*", "*", " ", " ", " ", " ", "*", " ", "*", "*", "|"], 
  ["|", " ", "*", " ", " ", "*", " ", " ", "*", " ", "*", "*", "*", " ", "*", " ", "*", " ", " ", " ", "*", "|"], 
  ["|", " ", "*", "*", "*", "*", " ", " ", " ", " ", "*", "*", " ", "*", "*", "*", " ", " ", " ", "*", "*", "|"], 
  ["|", " ", " ", "*", "*", " ", "*", "*", "*", " ", " ", " ", " ", " ", " ", "*", "*", " ", " ", " ", " ", "|"], 
  ["|", "*", " ", "*", "*", " ", "*", " ", "*", "*", " ", " ", " ", "*", " ", "*", "*", "*", " ", " ", " ", "|"], 
  ["|", " ", " ", " ", "*", " ", "*", " ", "*", " ", "*", " ", " ", " ", " ", " ", " ", "*", "*", " ", " ", "|"], 
  ["|", "*", " ", "*", " ", "*", " ", "*", " ", " ", " ", "*", " ", "*", "*", " ", "*", "*", "*", "*", "*", "|"], 
  ["|", " ", " ", " ", "*", " ", "*", "*", "*", "*", "*", "*", " ", " ", "*", " ", " ", "*", "*", " ", "*", "|"], 
  ["|", "*", "*", "*", "*", "*", " ", " ", " ", "*", " ", "*", " ", "*", "*", " ", "*", "*", " ", " ", "*", "|"], 
  ["|", "*", " ", " ", " ", "*", "*", "*", "*", " ", " ", "*", " ", "*", " ", "*", " ", "*", " ", "*", "*", "|"], 
  ["|", "*", " ", "*", "*", "*", "*", "*", "*", " ", "*", "*", "*", "*", " ", " ", " ", "*", " ", " ", " ", "|"], 
  ["|", " ", " ", "*", " ", " ", "*", "*", " ", " ", " ", "*", " ", "*", "*", " ", " ", " ", " ", " ", "*", "|"], 
  ["|", " ", "*", " ", " ", " ", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", " ", " ", " ", "*", "|"], 
  ["+", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "+"]
]

and i need to find the number of bombs that are near each "*" as shown in the image below.

Im doing this to get indexes but i dont know how to get the adjacents.

@array_map.each_index do |i|
subarray = @array_map[i]
 subarray.each_index do |x|
    puts String(i) << " " << String(x) << "... " << @array_map[i][x]
 end
end

user_256970 · Answer

minefield = [
  ["+", "-", "-", "-", "-", "-", "-", "-"],
  ["|", "*", "*", " ", " ", "*", " ", " "],
  ["|", " ", "*", "*", "*", "*", " ", " "],
  ["|", "*", " ", "*", " ", " ", " ", " "],
  ["|", "*", "*", " ", " ", "*", " ", " "],
  ["|", "*", " ", " ", " ", "*", " ", "*"],
  ["|", " ", " ", " ", " ", " ", "*", " "]
]

last_row = minefield.size-1
  #=> 6
last_col = minefield.first.size-1
  #=> 7
adj_cols = (0..last_col).each_with_object({}) do |j,h|
  h[j] = ([j-1, 0].max..[j+1, last_col].min).to_a
end
  #=> {0=>[0, 1], 1=>[0, 1, 2], 2=>[1, 2, 3], 3=>[2, 3, 4], 4=>[3, 4, 5],
  #    5=>[4, 5, 6], 6=>[5, 6, 7], 7=>[6, 7]}

arr = (0..last_row).each_with_object(minefield.dup.map(&:dup)) do |i,a|
  adj_rows = ([i-1, 0].max..[i+1, last_row].min).to_a
  (0..last_col).each do |j|
    next unless a[i][j] == ' '
    a[i][j] = adj_rows.product(adj_cols[j]).count do |r,c|
      minefield[r][c] == '*'
    end.to_s
  end
end

arr.each { |row| p row }

displays

["+", "-", "-", "-", "-", "-", "-", "-"]
["|", "*", "*", "4", "4", "*", "2", "0"]
["|", "4", "*", "*", "*", "*", "2", "0"]
["|", "*", "6", "*", "5", "3", "2", "0"]
["|", "*", "*", "2", "3", "*", "3", "1"]
["|", "*", "3", "1", "2", "*", "4", "*"]
["|", "1", "1", "0", "1", "2", "*", "2"]

See Array#product. adj_cols is a hash that gives an array of column indices to identify adjacent positions for each column index. It makes sense to do this once at the beginning rather than repeat the calculation for each element (row) of minefield.

The array to be returned is initialized to

minefield.dup.map(&:dup)

so that minefield will not be mutated (modified).

Here's an example calculation.

i = 3
adj_rows = ([i-1, 0].max..[i+1, last_row].min).to_a
  #=> ([2, 0].max..[4, 6].min).to_a
  #=> (2..4).to_a
  #=> [2, 3, 4]   
j = 4
a = adj_cols[j]
  #=> [3, 4, 5]
b = adj_rows.product(a)
  #=> [[2, 3], [2, 4], [2, 5],
  #    [3, 3], [3, 4], [3, 5],
  #    [4, 3], [4, 4], [4, 5]] 
b.count { |r,c| minefield[r][c] == '*' }
  #=> 5

Note that b includes [3, 4], which we know equals ' '. It does no harm to leave it in the count operation, however, as minefield[r][c] == '*' #=> false). We could alternatively write:

b = adj_rows.product(a) - [[i, j]]
  #=> [[2, 3], [2, 4], [2, 5],
  #    [3, 3],         [3, 5],
  #    [4, 3], [4, 4], [4, 5]]

Here's a second example (that would apply if minefield[0][4] #=> ' ').

i = 0
j = 4
adj_rows = ([i-1, 0].max..[i+1, last_row].min).to_a
  #=> [0, 1]   
j = 4
a = adj_cols[j]
  #=> [3, 4, 5]
b = adj_rows.product(a)
  #=> [[0, 3], [0, 4], [0, 5],
  #    [1, 3], [1, 4], [1, 5]]

For the minefield array given in the question the return value is as follows.

["+", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "+"]
["|", "*", "*", "4", "4", "*", "2", "0", "0", "2", "*", "*", "*", "*", "*", "*", "*", "*", "4", "*", "2", "|"]
["|", "4", "*", "*", "*", "*", "2", "1", "1", "4", "*", "*", "6", "7", "*", "*", "7", "*", "6", "*", "3", "|"]
["|", "*", "6", "*", "5", "3", "2", "2", "*", "6", "*", "6", "*", "*", "*", "6", "*", "*", "*", "4", "*", "|"]
["|", "*", "*", "2", "3", "*", "3", "3", "*", "*", "*", "6", "*", "8", "*", "*", "5", "*", "*", "5", "3", "|"]
["|", "*", "3", "1", "2", "*", "4", "*", "4", "4", "3", "*", "*", "*", "*", "*", "3", "3", "4", "*", "*", "|"]
["|", "3", "3", "2", "3", "5", "*", "5", "*", "2", "2", "5", "*", "7", "5", "4", "2", "2", "*", "4", "3", "|"]
["|", "*", "*", "4", "*", "*", "*", "6", "*", "2", "2", "*", "*", "*", "*", "2", "*", "3", "4", "*", "3", "|"]
["|", "4", "*", "5", "*", "*", "*", "*", "3", "3", "4", "*", "*", "6", "3", "4", "3", "*", "3", "*", "*", "|"]
["|", "3", "*", "6", "6", "*", "5", "3", "*", "3", "*", "*", "*", "5", "*", "4", "*", "2", "3", "5", "*", "|"]
["|", "2", "*", "*", "*", "*", "4", "4", "3", "4", "*", "*", "4", "*", "*", "*", "4", "2", "1", "*", "*", "|"]
["|", "2", "5", "*", "*", "6", "*", "*", "*", "4", "3", "2", "3", "3", "6", "*", "*", "3", "2", "2", "2", "|"]
["|", "*", "3", "*", "*", "6", "*", "7", "*", "*", "2", "1", "1", "*", "3", "*", "*", "*", "3", "1", "0", "|"]
["|", "2", "4", "4", "*", "5", "*", "5", "*", "4", "*", "2", "3", "3", "4", "4", "6", "*", "*", "4", "2", "|"]
["|", "*", "2", "*", "4", "*", "5", "*", "5", "5", "5", "*", "3", "*", "*", "3", "*", "*", "*", "*", "*", "|"]
["|", "3", "5", "5", "*", "5", "*", "*", "*", "*", "*", "*", "5", "5", "*", "5", "5", "*", "*", "6", "*", "|"]
["|", "*", "*", "*", "*", "*", "6", "6", "6", "*", "6", "*", "5", "*", "*", "4", "*", "*", "5", "5", "*", "|"]
["|", "*", "6", "5", "7", "*", "*", "*", "*", "4", "5", "*", "7", "*", "5", "*", "5", "*", "4", "*", "*", "|"]
["|", "*", "4", "*", "*", "*", "*", "*", "*", "3", "*", "*", "*", "*", "5", "2", "3", "*", "3", "3", "3", "|"]
["|", "2", "4", "*", "4", "5", "*", "*", "6", "5", "6", "*", "8", "*", "*", "4", "3", "2", "1", "2", "*", "|"]
["|", "1", "*", "2", "1", "2", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "*", "1", "0", "2", "*", "|"]
["+", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "+"]

user_477037 · Answer

This would work:

minefield = [
  ["+", "-", "-", "-", "-", "-", "+"],
  ["|", "*", "*", "*", "*", "*", "|"],
  ["|", "*", " ", "*", "*", " ", "|"],
  ["|", " ", " ", " ", "*", " ", "|"],
  ["|", "*", " ", "*", "*", "*", "|"],
  ["|", "*", "*", "*", " ", " ", "|"],
  ["+", "-", "-", "-", "-", "-", "+"]
]

minefield.each_with_index do |row, y|
  row.each_with_index do |item, x|
    next unless item == '*'

    (y - 1).upto(y + 1) do |j|
      (x - 1).upto(x + 1) do |i|
        next if minefield[j][i] =~ /[*|+-]/

        minefield[j][i] = minefield[j][i].to_i.succ.to_s
      end
    end
  end
end

It traverses the minefield array, skipping everything but bombs (next unless item == '*'). Once we encounter a bomb, we traverse its surroundings, skipping any special fields like *, |, +, or -. (this will also skip the bomb itself)

And since bombs don't occur on the minefield's border, we can omit bounds checking.

For the remaining surrounding fields (i.e. blanks and numeric strings), we convert that field to integer (so " " becomes 0), add 1 (via succ), convert it back to string and re-assign it to the field: (succ also works on strings, but we have to handle " " anyway)

                   #  blank  # numeric
minefield[j][i]    #=> " "   #   "1"
  .to_i            #=> 0     #   1
  .succ            #=> 1     #   2
  .to_s            #=> "1"   #   "2"

In the end, the blank fields have been replaced by the bomb counts:

[
  ["+", "-", "-", "-", "-", "-", "+"],
  ["|", "*", "*", "*", "*", "*", "|"],
  ["|", "*", "5", "*", "*", "4", "|"],
  ["|", "2", "4", "5", "*", "4", "|"],
  ["|", "*", "5", "*", "*", "*", "|"],
  ["|", "*", "*", "*", "4", "2", "|"],
  ["+", "-", "-", "-", "-", "-", "+"]
]

Find adjacents in bidimensional array

2 Answers