Techioz Blog

二次元配列で隣接するものを見つける (マインスイーパーのような行列)

概要

このような2次元配列があります。

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

そして、下の画像に示すように、各「*」の近くにある爆弾の数を見つける必要があります。

インデックスを取得するためにこれを行っていますが、隣接するものを取得する方法がわかりません。

@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

解決策

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 }

ディスプレイ

["+", "-", "-", "-", "-", "-", "-", "-"]
["|", "*", "*", "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"]

「配列#製品」を参照してください。 adj_cols は、各列インデックスの隣接する位置を識別するための列インデックスの配列を与えるハッシュです。地雷原の各要素 (行) に対して計算を繰り返すのではなく、これを最初に 1 回実行する方が合理的です。

返される配列は次のように初期化されます。

minefield.dup.map(&:dup)  

地雷原が突然変異（変更）されないようにします。

以下に計算例を示します。

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

b には [3, 4] が含まれており、これは ’ ’ に等しいことがわかっていることに注意してください。ただし、minefield[r][c] == ’*’ #=> false) のように、これをカウント操作に残しても問題はありません。あるいは、次のように書くこともできます。

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

2 番目の例を次に示します (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]] 

質問で指定された地雷原配列の場合、戻り値は次のようになります。

["+", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "+"]
["|", "*", "*", "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", "*", "|"]
["+", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "-", "+"]